Stacks and Queues

Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

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.

input stack Enqueue pushes new values onto the input stack.
output stack When the output stack is empty, transferring all input values reverses them into dequeue order.

Visual walkthrough

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

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 in_stack = Vec::new();
    let mut out_stack = Vec::new();
    for value in [10, 20, 30] { in_stack.push(value); }
    while let Some(value) = in_stack.pop() { out_stack.push(value); }
    let mut removed = Vec::new();
    while let Some(value) = out_stack.pop() { removed.push(value); }
    println!("{}", render(&removed));
}

Complexity

  • Time: O(1) amortized per operation
  • Space: O(n)

Implementation notes

  • The checked source imports VecDeque, but the actual queue uses two mutable Vec<i32> stacks: in_stack for enqueues and out_stack for dequeues.
  • Enqueue pushes owned i32 values from [10, 20, 30] with in_stack.push(value), producing [10, 20, 30].
  • Transfer uses while let Some(value) = in_stack.pop() { out_stack.push(value); }. Vec::pop returns Option<i32>; Some(value) moves the integer from the input stack to the output stack, and None ends the loop.
  • Because stack pop removes from the end, the transfer reverses order into out_stack=[30, 20, 10], putting 10 at the output stack's top.
  • Dequeue drains out_stack with another while let Some(value) = out_stack.pop() loop and pushes into removed, yielding [10, 20, 30].
  • The trace records empty stacks, enqueue to in=[10, 20, 30], transfer to out=[30, 20, 10], then FIFO removal with out=[].
  • render(&removed) borrows the result slice, converts each value with to_string(), joins with " -> ", and println!("{}", ...) prints 10 -> 20 -> 30.