Stack and Queue Patterns

Explicit stacks (Vec<T>) and queues (VecDeque<T>) are essential algorithmic building blocks for simulating recursion without overflowing the call stack, evaluating nested expressions, and processing multi-source wave-fronts level by level.

1. Explicit Stack (`Vec<Frame>`) Replaces Deep Recursion:
   Avoids OS 2 MiB thread stack overflow when tree/graph depth reaches $10^5 - 10^6$!

2. Multi-Source Level Queue (`VecDeque<(usize, usize)>`):
   Push all initial sources at distance 0, then process wave-front layer by layer!

1. Converting Deep Recursion into an Explicit Vec Stack

In competitive programming and production graph/AST analyzers, a skewed tree or chain graph of $N = 200,000$ vertices recurses $200,000$ stack frames deep—which overflows the standard 2 MiB–8 MiB OS call stack!

Replacing recursive function calls with an explicit heap-allocated Vec stack stores the pending work on the process heap (which can grow to gigabytes) in $O(1)$ call-stack space:

/// Evaluates a Reverse Polish Notation (RPN / Postfix) expression using a `Vec<i64>` stack.
pub fn eval_rpn(tokens: &[&str]) -> i64 {
    let mut stack: Vec<i64> = Vec::with_capacity(tokens.len());

    for &tok in tokens {
        match tok {
            "+" | "-" | "*" | "/" => {
                let right = stack.pop().expect("missing right operand");
                let left = stack.pop().expect("missing left operand");
                let res = match tok {
                    "+" => left + right,
                    "-" => left - right,
                    "*" => left * right,
                    "/" => left / right,
                    _ => unreachable!(),
                };
                stack.push(res);
            }
            num => stack.push(num.parse::<i64>().expect("invalid integer")),
        }
    }

    stack.pop().unwrap_or(0)
}

2. Multi-Source Wave-Front Propagation with VecDeque

When computing the minimum distance from every grid cell to the nearest source (such as nearest exit, nearest 0, or fire/water spread across a 2D grid), running a separate BFS from every cell takes $O((R \cdot C)^2)$ time.

Instead, push all source coordinates into a single VecDeque upfront at distance 0 and run one single multi-source BFS in $O(R \cdot C)$ linear time:

use std::collections::VecDeque;

/// Computes the Manhattan distance from every cell in an `R x C` grid to the nearest `0` cell
/// in O(R * C) time using a multi-source `VecDeque` wave-front.
pub fn distance_to_nearest_zero(grid: &[Vec<u8>]) -> Vec<Vec<u32>> {
    let rows = grid.len();
    let cols = grid[0].len();
    let mut dist = vec![vec![u32::MAX; cols]; rows];
    let mut queue = VecDeque::new();

    // 1. Seed the queue with ALL source cells (`0`) at distance 0 simultaneously:
    for r in 0..rows {
        for c in 0..cols {
            if grid[r][c] == 0 {
                dist[r][c] = 0;
                queue.push_back((r, c));
            }
        }
    }

    // Safe unsigned 4-directional grid neighbor offsets using `wrapping_add`:
    const DIRS: [(usize, usize); 4] = [(!0, 0), (1, 0), (0, !0), (0, 1)];

    // 2. Propagate wave-front outward layer by layer:
    while let Some((r, c)) = queue.pop_front() {
        let next_d = dist[r][c] + 1;
        for (dr, dc) in DIRS {
            let nr = r.wrapping_add(dr);
            let nc = c.wrapping_add(dc);
            if nr < rows && nc < cols && dist[nr][nc] > next_d {
                dist[nr][nc] = next_d;
                queue.push_back((nr, nc));
            }
        }
    }

    dist
}

fn main() {
    // (2 + 1) * 3 = 9
    let rpn_val = eval_rpn(&["2", "1", "+", "3", "*"]);
    assert_eq!(rpn_val, 9);

    let grid = vec![
        vec![0, 1, 1],
        vec![1, 1, 1],
        vec![1, 1, 0],
    ];
    let dists = distance_to_nearest_zero(&grid);
    assert_eq!(
        dists,
        vec![
            vec![0, 1, 2],
            vec![1, 2, 1],
            vec![2, 1, 0],
        ]
    );

    println!("RPN result: {rpn_val}, center cell distance to nearest 0: {}", dists[1][1]);
}

RPN result: 9, center cell distance to nearest 0: 2

Notice the unsigned 2D grid neighbor idiom let nr = r.wrapping_add(dr); if nr < rows: when r == 0 and dr == !0 (usize::MAX, representing -1), 0usize.wrapping_add(usize::MAX) wraps to usize::MAX, which is caught by the single unsigned check nr < rows without needing isize casts!