Stacks and Queues

Stack Push/Pop

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

Algorithm

The replay uses the same three values in every language, so this Scala DSA implementation can be compared directly with the rest of the DSA track.

top The top is the most recently pushed value.
LIFO A stack removes values in last-in, first-out order.

Visual walkthrough

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

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))

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.