Stacks and Queues

Stacks (Last-In, First-Out / LIFO) and queues (First-In, First-Out / FIFO) are fundamental linear abstract data types. Rather than defining separate Stack<T> or Queue<T> wrapper types in the standard library, Rust maps stacks directly to Vec<T> and queues directly to std::collections::VecDeque<T>.

1. Stack (LIFO — Last-In, First-Out) backed by `Vec<T>`:
   [ 10 | 20 | 30 ]  <--- `.push(40)` / `.pop()` operate at the back in O(1) time!

2. Queue (FIFO — First-In, First-Out) backed by `VecDeque<T>`:
   `.pop_front()` <--- [ 10 | 20 | 30 ] <--- `.push_back(40)`  (Both ends O(1)!)

Mapping Stack and Queue Operations to Standard Types

Never use vec.remove(0) to implement a FIFO queue on a large collection! Calling vec.remove(0) shifts every remaining element left by 1 slot ($O(n)$ per dequeue, turning $n$ dequeues into $O(n^2)$ time), whereas VecDeque::pop_front() simply increments a ring-buffer head index in $O(1)$ time.

Practical Application: Monotonic Stack and BFS Queue

1. Stack (Vec<T>): Used for expression evaluation, bracket matching, depth-first search (DFS), undo histories, and monotonic stack algorithms.
2. Queue (VecDeque<T>): Used for breadth-first search (BFS), level-order tree traversal, task scheduling, and sliding window buffers.

use std::collections::VecDeque;

/// Uses a LIFO Stack (`Vec<char>`) to verify balanced brackets in O(n) time.
pub fn has_balanced_brackets(expr: &str) -> bool {
    let mut stack = Vec::new();
    for ch in expr.chars() {
        match ch {
            '(' => stack.push(')'),
            '[' => stack.push(']'),
            '{' => stack.push('}'),
            ')' | ']' | '}' => {
                if stack.pop() != Some(ch) {
                    return false;
                }
            }
            _ => {}
        }
    }
    stack.is_empty()
}

/// Uses a FIFO Queue (`VecDeque<(usize, u32)>`) for Breadth-First Search (BFS) shortest path.
pub fn shortest_hops(adj: &[Vec<usize>], start: usize, target: usize) -> Option<u32> {
    let mut visited = vec![false; adj.len()];
    let mut queue = VecDeque::new();

    visited[start] = true;
    queue.push_back((start, 0));

    while let Some((node, dist)) = queue.pop_front() {
        if node == target {
            return Some(dist);
        }
        for &next in &adj[node] {
            if !visited[next] {
                visited[next] = true;
                queue.push_back((next, dist + 1));
            }
        }
    }
    None
}

fn main() {
    assert!(has_balanced_brackets("fn main() { let a = [1, (2 + 3)]; }"));
    assert!(!has_balanced_brackets("([)]"));
    println!("Bracket stack check passed");

    // Graph: 0 -> 1 -> 2 -> 3, and 0 -> 4 -> 3 (shortest path 0 -> 4 -> 3 is 2 hops)
    let graph = vec![vec![1, 4], vec![2], vec![3], vec![], vec![3]];
    println!("Shortest hops from 0 to 3 via BFS queue: {:?}", shortest_hops(&graph, 0, 3));
}

Bracket stack check passed
Shortest hops from 0 to 3 via BFS queue: Some(2)