Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

Algorithm

Basic Implementation

basic.rs 
use std::collections::VecDeque;

fn render(values: &[i32]) -> String {
    values.iter().map(|v| v.to_string()).collect::<Vec<_>>().join(" -> ")
}

fn main() {
    let mut stack = Vec::new();
    for value in [10, 20, 30] { stack.push(value); }
    let mut popped = Vec::new();
    while let Some(value) = stack.pop() { popped.push(value); }
    println!("{}", render(&popped));
}

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • The checked source imports VecDeque, but the stack itself is let mut stack = Vec::new(), a mutable Vec<i32>.
  • Pushes use stack.push(value) for owned i32 values from [10, 20, 30], leaving the top of the stack at the vector's end.
  • Pops use while let Some(value) = stack.pop(). Vec::pop returns Option<i32>; Some(value) moves the integer into the loop body, and None ends the loop without a separate empty check.
  • Removed values are collected in let mut popped = Vec::new() with popped.push(value), preserving the observed pop order.
  • The trace records stack=[], push to [10, 20, 30], first pop to popped=[30] with stack=[10, 20], then draining to popped=[30, 20, 10] and stack=[].
  • render(&popped) borrows the result slice, converts each integer with to_string(), joins with " -> ", and println!("{}", ...) prints 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.