Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.rb 
in_stack = []
out_stack = []
[10, 20, 30].each { |value| in_stack.push(value) }
out_stack.push(in_stack.pop) until in_stack.empty?
removed = []
removed << out_stack.pop until out_stack.empty?
puts removed.join(" -> ")

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

  • This checked Ruby source is straight-line code, not a queue class: in_stack and out_stack are both arrays used as stacks.
  • Enqueue uses in_stack.push(value) for 10, 20, and 30, leaving the input stack as [10, 20, 30].
  • Transfer uses out_stack.push(in_stack.pop) until in_stack.empty?; each pop removes and returns the last input value.
  • That transfer reverses the stack order, producing out_stack as [30, 20, 10] in the trace.
  • Dequeue order then comes from out_stack.pop, which removes 10, then 20, then 30.
  • Both transfer and removal loops are guarded with empty?, so this lesson does not rely on Ruby Array#pop returning nil from an empty array.
  • removed << out_stack.pop records the returned values as [10, 20, 30].
  • puts removed.join(" -> ") 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.