Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.pl 
use strict;
use warnings;

sub render { return join(" -> ", @_); }

my @in_stack;
my @out_stack;
push @in_stack, $_ for (10, 20, 30);
push @out_stack, pop @in_stack while @in_stack;
my @removed;
push @removed, pop @out_stack while @out_stack;
print render(@removed), "\n";

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

  • my @in_stack and my @out_stack are the two Perl arrays used as stacks; both use the @ sigil.
  • The replay starts with both stacks empty: input [], output [].
  • Enqueue uses push @in_stack, $_ for (10, 20, 30), appending each value to the top of the input stack.
  • After enqueue, the input stack is [10, 20, 30] and the output stack is still [].
  • Transfer uses push @out_stack, pop @in_stack while @in_stack.
  • In that while @in_stack condition, @in_stack is in scalar context, so it means "while the stack has length".
  • pop @in_stack removes from the end: 30, then 20, then 10.
  • push @out_stack, ... appends those popped values, giving output stack [30, 20, 10] and emptying the input stack.
  • Dequeue then uses push @removed, pop @out_stack while @out_stack.
  • Popping the output stack returns 10, then 20, then 30, which restores FIFO order.
  • The trace ends with removed values [10, 20, 30] and output stack [].
  • render(@removed) joins the removed values with " -> ", and print render(@removed), "\n" outputs 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.