Stacks and Queues

Queue from Two Stacks

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

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

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

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.
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.