Stacks and Queues

Stack Push/Pop

Push values onto a stack and pop them back in last-in, first-out order.

Algorithm

Basic Implementation

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

The same three values from the trace are shown as stack states. The top cell is the next value a pop removes.

Step 1 - Start empty

There is no top value yet.

Empty stack before any push.top of stack(empty)

Step 2 - Push 10, then 20, then 30

Each push places the new value above the previous top.

After push 10, push 20, push 30: 30 is on top.top -> bottom302010

Step 3 - Pop removes 30 first

The top cell leaves first, so the remaining stack starts with 20.

After one pop: popped is 30; 20 is now on top.top -> bottompopped203010

Complexity

  • Time: O(1) per push/pop
  • Space: O(n)

Implementation notes

  • $stack = [] starts as an empty PHP array, and the trace records that empty stack before any pushes.
  • The push loop is foreach ([10, 20, 30] as $value) { $stack[] = $value; }, so each value appends to the top end of the array.
  • After the pushes, the replayed stack state is [10, 20, 30], with 30 at the pop end.
  • $popped = [] stores the values in removal order.
  • The pop loop runs while count($stack) > 0 and uses $popped[] = array_pop($stack).
  • array_pop($stack) removes and returns the last array value, so the first pop returns 30 and leaves [10, 20].
  • The remaining pops return 20 and then 10, ending with $popped = [30, 20, 10] and $stack = [].
  • render_values($popped) joins the LIFO order with " -> ", and echo ... . PHP_EOL prints 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.