Stacks and Queues

Queue from Two Stacks

Implement queue behavior with an input stack and an output stack.

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.

input stack Enqueue pushes new values onto the input stack.
output stack When the output stack is empty, transferring all input values reverses them into dequeue order.

Visual walkthrough

The two-stack queue keeps cheap enqueues in the input stack, then reverses that stack only when dequeue needs the output stack.

Step 1 - Enqueue pushes onto the input stack

After enqueueing 10, 20, 30, the newest input value is on top of the input stack.

After enqueues: input top is 30; output is empty.input stack top -> bottomoutput stack top -> bottomremoved30(empty)(empty)2010

Step 2 - Transfer reverses into output order

Moving every input value to the output stack turns 10 into the next pop.

After transfer: output top is 10, so dequeue returns the oldest value.input stackoutput stack top -> bottomremoved(empty)10(empty)2030

Step 3 - Dequeue pops from output

The output stack pops 10 first while 20 becomes the next front.

After one dequeue: removed is 10; output top is now 20.input stackoutput stack top -> bottomremoved(empty)201030

Basic Implementation

basic.scala 
def render(values: Seq[Int]): String = values.mkString(" -> ")

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

Complexity

  • Time: O(1) amortized per operation
  • Space: O(n)

Implementation notes

  • This checked source uses top-level Scala code with List[Int] values as the two stacks, not a queue class.
  • var inStack = List[Int]() and var outStack = List[Int]() are mutable bindings; each reassignment points the variable at a new list.
  • Enqueue uses inStack = value :: inStack, so each new value is pushed onto the front of the input stack's underlying List; after enqueue, the raw Scala list head order is List(30, 20, 10).
  • The transfer loop is guarded by while (inStack.nonEmpty), then moves inStack.head to outStack with outStack = inStack.head :: outStack and advances input with inStack = inStack.tail.
  • Because head and tail are only used after nonEmpty, this source has no Option return or sentinel path for empty stacks.
  • The trace presents queued values as [10, 20, 30] and the transferred stack as outStack = [30, 20, 10]; that is a logical stack display, not Scala List iteration order.
  • After transfer, the raw Scala outStack head order is List(10, 20, 30), so removed = removed :+ outStack.head records 10, then 20, then 30 before outStack = outStack.tail drains it.
  • render(values: Seq[Int]) uses mkString(" -> "), so println(render(removed)) writes 10 -> 20 -> 30.