Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.kt 
import java.util.ArrayDeque

fun render(values: List<Int>) = values.joinToString(" -> ")

fun main() {
    val inStack = ArrayDeque<Int>()
    val outStack = ArrayDeque<Int>()
    for (value in listOf(10, 20, 30)) inStack.addLast(value)
    while (!inStack.isEmpty()) outStack.addLast(inStack.removeLast())
    val removed = mutableListOf<Int>()
    while (!outStack.isEmpty()) removed.add(outStack.removeLast())
    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

  • Kotlin imports java.util.ArrayDeque and creates val inStack and val outStack as ArrayDeque<Int> instances. The bindings are not rebound, but both stack contents mutate.
  • Enqueue writes to the input stack with inStack.addLast(value) for listOf(10, 20, 30), producing [10, 20, 30].
  • Transfer uses while (!inStack.isEmpty()) outStack.addLast(inStack.removeLast()), moving values from the back of inStack to the back of outStack.
  • Dequeue order comes from outStack.removeLast() inside while (!outStack.isEmpty()), so the transferred stack yields 10, 20, then 30.
  • The emptiness checks avoid the exception path for removeLast() on an empty deque; values are non-null Ints throughout.
  • The trace shows in=[] and out=[], then in=[10, 20, 30], then transfer to in=[] and out=[30, 20, 10], then removed [10, 20, 30].
  • render(values: List<Int>) uses joinToString(" -> "), and println(render(removed)) prints 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.