Algorithms and Data Structures in Rust: A Practical Guide

Algorithms and Data Structures in Rust: Why It Matters

Rust is a modern systems programming language that combines the performance of C++ with memory safety provided by the ownership system. Learning algorithms and data structures in Rust allows you not only to master classic Computer Science concepts but also to deeply understand the language's unique features: borrowing, lifetimes, and zero-cost abstractions.

In this article, we will examine three fundamental data structures (stack, queue, and binary search tree) and one classic algorithm (quicksort), implemented in Rust. Each example is accompanied by code and explanations that will help you move from theory to practice.

1. Stack in Rust: Implementation via Vec

A stack is a data structure that operates on the LIFO (Last In, First Out) principle. In Rust, the easiest way to implement a stack is based on the standard Vec, which provides all the necessary methods: push for adding and pop for removing.

However, to demonstrate Rust's safety, we will create a wrapper with explicit error handling:

pub struct Stack<T> {    elements: Vec<T>,}

impl<T> Stack<T> {    pub fn new() -> Self {        Stack { elements: Vec::new() }    }

    pub fn push(&mut self, item: T) {        self.elements.push(item);    }

    pub fn pop(&mut self) -> Option<T> {        self.elements.pop()    }

    pub fn peek(&self) -> Option<&T> {        self.elements.last()    }

    pub fn is_empty(&self) -> bool {        self.elements.is_empty()    }}

fn main() {    let mut stack = Stack::new();    stack.push(10);    stack.push(20);    stack.push(30);

    println!("Top element: {:?}", stack.peek()); // Some(30)    println!("Popping: {:?}", stack.pop());         // Some(30)    println!("Popping: {:?}", stack.pop());         // Some(20)    println!("Is stack empty? {}", stack.is_empty());      // false}

The key advantage of Rust here is the type system. If you try to pop an element from an empty stack, the compiler will force you to handle the Option, which eliminates null pointer dereferencing errors typical of C/C++.

2. Queue: Manual Implementation with a Circular Buffer

A queue (FIFO) is more complex than a stack because it requires efficient removal from the front. Rust does not provide a ready-made double-ended queue with guaranteed performance, so we will implement a fixed-size circular buffer.

This is an excellent example for demonstrating unsafe code and raw pointers, but we will stay in the safe zone using Vec and indices:

pub struct Queue<T> {    buffer: Vec<Option<T>>,    head: usize,    tail: usize,    capacity: usize,}

impl<T> Queue<T> {    pub fn new(capacity: usize) -> Self {        let mut buffer = Vec::with_capacity(capacity);        buffer.resize_with(capacity, || None);        Queue {            buffer,            head: 0,            tail: 0,            capacity,        }    }

    pub fn enqueue(&mut self, item: T) -> Result<(), &str> {        if (self.tail + 1) % self.capacity == self.head {            return Err("Queue is full");        }        self.buffer[self.tail] = Some(item);        self.tail = (self.tail + 1) % self.capacity;        Ok(())    }

    pub fn dequeue(&mut self) -> Option<T> {        if self.head == self.tail {            return None;        }        let item = self.buffer[self.head].take();        self.head = (self.head + 1) % self.capacity;        item    }

    pub fn is_empty(&self) -> bool {        self.head == self.tail    }}

fn main()