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.rb 
stack = []
[10, 20, 30].each { |value| stack.push(value) }
popped = []
popped << stack.pop until stack.empty?
puts popped.join(" -> ")

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

  • The stack is a Ruby Array, starting as stack = [].
  • Push uses stack.push(value) for 10, 20, and 30, so the top is the array's last element.
  • Pop uses stack.pop, which removes and returns that last element while mutating the same array.
  • popped << stack.pop until stack.empty? records each returned value and stops before an empty pop could return nil.
  • The trace shows LIFO order directly: [10, 20, 30] pops 30 first, then 20, then 10.
  • After all pops, stack is [] and popped is [30, 20, 10].
  • puts popped.join(" -> ") prints 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.