Stacks and Queues

Stack Push/Pop

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

Algorithm

The replay uses the same three values in every language, so this Rust DSA implementation can be compared directly with the rest of the DSA track.

top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.

Visual walkthrough

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

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));
}

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.