Stacks and Queues

Recipe	Crates	Categories

While Rust's standard library doesn't have dedicated Stack and Queue types in the same way some other languages do, you can easily implement their functionality using existing data structures, primarily Vec (for stack-like behavior) and VecDeque (for queue-like behavior).

Implement a stack using Vec

A stack is a LIFO (Last-In, First-Out) data structure. You can use a Vec to mimic a stack, because Vec provides efficient push (add to the top) and pop (remove from the top) operations.

fn main() {
    let mut stack = Vec::new();

    stack.push(1); // Push 1 onto the stack
    stack.push(2); // Push 2 onto the stack
    stack.push(3); // Push 3 onto the stack

    println!("Top element: {:?}", stack.last()); // Peek at the top element

    // `pop` eemoves and returns the top element. Returns None if the stack is
    // empty.
    while let Some(top) = stack.pop() {
        // Pop elements until the stack is empty
        println!("Popped: {}", top);
    }

    println!("Stack is empty: {}", stack.is_empty());
}

Implement a queue using VecDeque

A queue is a FIFO (First-In, First-Out) data structure. VecDeque (Vector Deque) is well-suited for implementing queues because it provides efficient push_back (add to the rear) and pop_front (remove from the front) operations.

// A double-ended queue implemented with a growable ring buffer.
use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();

    queue.push_back(1); // Enqueue 1
    queue.push_back(2); // Enqueue 2
    queue.push_back(3); // Enqueue 3

    println!("Front element: {:?}", queue.front()); // Peek at the front element

    while let Some(front) = queue.pop_front() {
        // Dequeue elements until the queue is empty
        println!("Dequeued: {}", front);
    }

    println!("Queue is empty: {}", queue.is_empty());
}