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.pl 
use strict;
use warnings;

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

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

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

  • my @stack declares the stack as a Perl array with the @ sigil.
  • The replay starts with an empty stack: [].
  • Push uses push @stack, $_ for (10, 20, 30), appending each value to the end of the array.
  • After the pushes, the stack is [10, 20, 30]; the top is the rightmost value, 30.
  • my @popped records values returned by pop operations.
  • Pop uses pop @stack, which removes and returns the last array element.
  • push @popped, pop @stack while @stack repeats while the stack is non-empty; in that condition, @stack is in scalar context and means length.
  • The first pop returns 30, leaving stack [10, 20] and popped [30].
  • The remaining pops return 20 and 10, leaving stack [] and popped [30, 20, 10].
  • render(@popped) joins the popped values with " -> ".
  • print render(@popped), "\n" outputs 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.