Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.php 
<?php
function render_values(array $values): string { return implode(" -> ", $values); }
$inStack = [];
$outStack = [];
foreach ([10, 20, 30] as $value) { $inStack[] = $value; }
while (count($inStack) > 0) { $outStack[] = array_pop($inStack); }
$removed = [];
while (count($outStack) > 0) { $removed[] = array_pop($outStack); }
echo render_values($removed) . PHP_EOL;

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

  • $inStack = [] and $outStack = [] are plain PHP arrays used as stacks; the trace begins with both empty.
  • Enqueue uses foreach ([10, 20, 30] as $value) { $inStack[] = $value; }, so values append to the back of $inStack.
  • After enqueue, the replay shows $inStack as [10, 20, 30] and $outStack still empty.
  • The transfer loop runs while count($inStack) > 0 and moves values with $outStack[] = array_pop($inStack).
  • Because array_pop removes the last appended value, the transfer reverses the stack into $outStack = [30, 20, 10] and leaves $inStack = [].
  • $removed = [] records dequeued values separately.
  • The dequeue loop uses $removed[] = array_pop($outStack), so popping the output stack returns 10, then 20, then 30.
  • The trace ends with $removed = [10, 20, 30] and $outStack = [].
  • render_values($removed) joins the dequeued order with " -> ", and echo ... . PHP_EOL 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.