Stacks and Queues

Recipe	Crates	Categories
Implement a Queue Using VecDeque
Implement a Stack Using Vec

While Rust's standard library doesn't have dedicated Stack and Queue types in the same way some other languages do, you can easily use existing data structures instead - 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() {
    // Initialize a stack with a minimum capacity.
    // The stack will be able to hold at least 5 elements without reallocating:
    let mut stack = Vec::with_capacity(5);
    assert_eq!(stack.capacity(), 5);
    assert_eq!(stack.len(), 0);

    // Append elements to the back of the `Vec` / top of the stack:
    stack.push(1);
    stack.push(22);
    stack.push(333);

    // Peek at the top (last) element of the stack, or `None` if it is empty
    println!("Top element: {:?}", stack.last());
    assert_eq!(stack.last(), Some(&333));

    // Remove and return the top (last) element if the predicate returns true,
    // or `None` if the predicate returns false or the vector is empty.
    assert_eq!(stack.pop_if(|x: &mut i32| *x % 2 == 0), None);

    // `pop` removes and returns the top (last) element.
    // It 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:

use std::collections::VecDeque;

fn main() {
    let mut queue = VecDeque::new();
    // You can also use `with_capacity`.

    // Add to the queue:
    queue.push_back(1);
    queue.push_back(2);
    queue.push_back(3);

    // Initialize a queue from an array:
    let mut q2 = VecDeque::from([4, 5]);

    // Append to the first queue:
    queue.append(&mut q2);

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

    // Dequeue elements from the front, until the queue is empty.
    while let Some(front) = queue.pop_front() {
        println!("Dequeued: {front}");
    }
    // Consider using `pop_front_if` as well.

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

    // `VecDeque` is in fact a double-ended queue that offers `push_front`,
    // `back`, `back_mut`, `pop_back`, `pop_back_if` operations:
    queue.push_front(-1);
    queue.push_front(-2);
    assert_eq!(queue.back(), Some(&-1));
}

Related Topics

• Binary Heaps.
• Linked Lists.
• Vectors.