Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.swift 
func render(_ values: [Int]) -> String {
    values.map(String.init).joined(separator: " -> ")
}

var inStack: [Int] = []
var outStack: [Int] = []
for value in [10, 20, 30] { inStack.append(value) }
while !inStack.isEmpty { outStack.append(inStack.removeLast()) }
var removed: [Int] = []
while !outStack.isEmpty { removed.append(outStack.removeLast()) }
print(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

  • var inStack: [Int] = [] and var outStack: [Int] = [] are mutable Swift arrays used as stack storage; the back of each array is the stack top.
  • Enqueue is the loop for value in [10, 20, 30] { inStack.append(value) }, which appends each Int to the input stack.
  • The transfer loop while !inStack.isEmpty guards removeLast(), so the source has no optional return or sentinel path while moving values into outStack.
  • outStack.append(inStack.removeLast()) reverses the input stack, changing [10, 20, 30] into output stack state [30, 20, 10].
  • var removed: [Int] = [] then collects dequeues with removed.append(outStack.removeLast()) while outStack is non-empty.
  • The trace records empty stacks, inStack = [10, 20, 30], transfer to inStack = [] and outStack = [30, 20, 10], then removed = [10, 20, 30] with outStack = [].
  • render(_:) maps each Int to String and joins with " -> ", so print(render(removed)) outputs 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.