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.scala 
def render(values: Seq[Int]): String = values.mkString(" -> ")

var stack = List[Int]()
for (value <- List(10, 20, 30)) stack = value :: stack
var popped = List[Int]()
while (stack.nonEmpty) { popped = popped :+ stack.head; stack = stack.tail }
println(render(popped))

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

  • var stack = List[Int]() uses a Scala List[Int] as the stack storage; the var binding is reassigned as values are pushed and popped.
  • Push is stack = value :: stack, so each new value is added to the front, which acts as the raw Scala List head and stack top.
  • var popped = List[Int]() records the pop order separately from the remaining stack.
  • The loop guard while (stack.nonEmpty) prevents reading head or tail on an empty list, so this source has no Option return or sentinel path.
  • Pop reads the top with stack.head, appends it to popped with :+, then drops it with stack = stack.tail.
  • After the pushes, the raw Scala list head order is List(30, 20, 10). The trace displays the stack as [10, 20, 30], a bottom-to-top visual order.
  • The first pop reads raw stack.head as 30, records popped = [30], and the trace shows the remaining stack view as [10, 20].
  • The remaining pops leave popped = [30, 20, 10] and stack = [].
  • render(values: Seq[Int]) uses mkString(" -> "), so println(render(popped)) writes 30 -> 20 -> 10.
top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.