Stacks and Queues

Queue from Two Stacks

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

Algorithm

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

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

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