Algorithms and Data Structures in Rust: A Practical Guide

Introduction: Why Rust is Ideal for Algorithms and Data Structures

Rust combines the performance of C/C++ with memory safety, making it an excellent choice for implementing algorithms and data structures. Thanks to its ownership and borrowing system, you can create efficient and safe structures without a garbage collector. In this article, we will explore the practical implementation of key data structures and algorithms in Rust — from a stack to a binary tree and graph traversal.

We will use only the Rust standard library so you can immediately apply the code in your projects. All examples compile and work with Rust 2021 edition.

1. Stack and Queue: Classic Structures in Rust

Stack

A stack operates on the LIFO (Last In, First Out) principle. In Rust, the easiest way to implement a stack is based on Vec:

struct Stack<T> {\n    elements: Vec<T>,\n}\n\nimpl<T> Stack<T> {\n    fn new() -> Self {\n        Stack { elements: Vec::new() }\n    }\n\n    fn push(&mut self, value: T) {\n        self.elements.push(value);\n    }\n\n    fn pop(&mut self) -> Option<T> {\n        self.elements.pop()\n    }\n\n    fn peek(&self) -> Option<&T> {\n        self.elements.last()\n    }\n\n    fn is_empty(&self) -> bool {\n        self.elements.is_empty()\n    }\n}\n\nfn main() {\n    let mut stack = Stack::new();\n    stack.push(10);\n    stack.push(20);\n    stack.push(30);\n    \n    println!("Top element: {:?}", stack.peek()); // Some(30)\n    println!("Popping: {:?}", stack.pop()); // Some(30)\n    println!("Is stack empty? {}", stack.is_empty()); // false\n}

Advantage: Vec already provides amortized O(1) for push/pop, and Rust guarantees that memory will be freed when it goes out of scope.

Queue

A queue operates on the FIFO (First In, First Out) principle. For an efficient implementation, we use VecDeque from the standard library:

use std::collections::VecDeque;\n\nstruct Queue<T> {\n    elements: VecDeque<T>,\n}\n\nimpl<T> Queue<T> {\n    fn new() -> Self {\n        Queue { elements: VecDeque::new() }\n    }\n\n    fn enqueue(&mut self, value: T) {\n        self.elements.push_back(value);\n    }\n\n    fn dequeue(&mut self) -> Option<T> {\n        self.elements.pop_front()\n    }\n\n    fn front(&self) -> Option<&T> {\n        self.elements.front()\n    }\n\n    fn len(&self) -> usize {\n        self.elements.len()\n    }\n}\n\nfn main() {\n    let mut queue = Queue::new();\n    queue.enqueue("first");\n    queue.enqueue("second");\n    queue.enqueue("third");\n\n    println!("First in queue: {:?}", queue.front()); // Some("first")\n    println!("Serving: {:?}", queue.dequeue()); // Some("first")\n    println!("Queue length: {}", queue.len()); // 2\n}

Important: VecDeque uses a ring buffer, providing O(1) for insertion and removal from both ends. This is significantly faster than using Vec for a queue.

2. Binary Search Tree (BST) in Rust

A binary search tree is one of the fundamental data structures. We will implement it using Box for recursive types:

use std::cmp::Ordering;\n\n#[derive(Debug)]\nstruct Node<T: Ord> {\n    value: T,\n    left: Option<Box<Node<T>>>,\n    right: Option<Box<Node<T>>>,\n}\n\n#[derive(Debug)]\nstruct BinarySearchTree<T: Ord> {\n    root: Option<Box<Node<T>>>,\n}\n\nimpl<T: Ord> BinarySearchTree<T> {\n    fn new() -> Self {\n        BinarySearchTree { root: None }\n    }\n\n    fn insert(&mut self, value: T) {\n        let mut current = &mut se