Stacks and Queues

Queue from Two Stacks

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

Algorithm

Basic Implementation

basic.py 
in_stack = []
out_stack = []

def enqueue(value):
    in_stack.append(value)

def transfer():
    while in_stack:
        out_stack.append(in_stack.pop())

def dequeue():
    if not out_stack:
        transfer()
    return out_stack.pop()

for value in [10, 20, 30]:
    enqueue(value)
removed = [dequeue(), dequeue(), dequeue()]
print(" -> ".join(str(x) for x in 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

  • Python uses two plain lists, in_stack and out_stack, as stacks. Enqueue is in_stack.append(value), and dequeue returns out_stack.pop() from the end; no deque is used in this lesson.
  • When out_stack is empty, transfer() mutates both lists in a while in_stack loop: in_stack.pop() removes the newest input value and out_stack.append(...) reverses the order for FIFO pops. Each value moves between stacks at most once before removal, giving the amortized behavior.
  • The stack lists and removed result list are the only persistent containers; normal Python GC owns them once no references remain. The trace shows [10, 20, 30] transfer to [30, 20, 10], then pop back out as [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.