Module 09 · Queues, Heaps, and Streaming Frontiers

081. Queue Using Two Stacks

Foundation · Download this solution · All solutions and shared helpers

Problem

Implement a FIFO queue using two stacks, with push(value), pop(), peek() and empty(). push returns None; pop removes and returns the oldest value. pop and peek on an empty queue raise IndexError. Use only stack-end operations internally.

Examples

Example 1

run_operations(TwoStackQueue, [("push",1),("push",2),("peek",),("pop",),("push",3),("pop",),("pop",),("empty",)])
=> [None, None, 1, 1, None, 2, 3, True]

A new incoming value waits behind older outgoing values.

Example 2

run_operations(TwoStackQueue, [("empty",)])
=> [True]

Both stacks begin empty.

Example 3

run_operations(TwoStackQueue, [("push",0),("peek",),("empty",)])
=> [None, 0, False]

Zero is a stored value, not an empty marker.

Reveal the worked solution and reasoning

Why this mechanism works

The incoming stack collects new values in reverse departure order. Moving all of them to an empty outgoing stack reverses that order again, placing the oldest at its top. Never transfer into a nonempty outgoing stack, because its older values must leave first.

State and boundaries

outgoing holds the older queue segment in pop order; incoming holds the newer segment in insertion order from bottom to top.

Protocol

Push new values onto incoming.
Before pop or peek, transfer only if outgoing is empty.
Pop or inspect outgoing's top.
Report empty only when both stacks are empty.

Visualization

push 1,2,3 -> incoming [1,2,3]
transfer -> outgoing [3,2,1]
pop top -> 1, then 2, then 3

Python implementation

from structures import run_operations

class TwoStackQueue:
    def __init__(self):
        self.incoming, self.outgoing = [], []

    def push(self, value):
        self.incoming.append(value)

    def _prepare(self):
        if not self.outgoing:
            while self.incoming:
                self.outgoing.append(self.incoming.pop())

    def pop(self):
        self._prepare()
        return self.outgoing.pop()

    def peek(self):
        self._prepare()
        return self.outgoing[-1]

    def empty(self):
        return not self.incoming and not self.outgoing

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

run_operations(TwoStackQueue, [("push",1),("push",2),("peek",),("pop",),("push",3),("pop",),("pop",),("empty",)])

L5 __init__: self.incoming, self.outgoing = [], []
self=TwoStackQueue{'incoming':[], 'outgoing':[]}

L8 push: self.incoming.append(value)
self=TwoStackQueue{'incoming':[...], 'outgoing':[]}; value=1

L8 push: self.incoming.append(value)
self=TwoStackQueue{'incoming':[..., ...], 'outgoing':[]}; value=2

L11 _prepare: if not self.outgoing:
self=TwoStackQueue{'incoming':[..., ...], 'outgoing':[]}

L13 _prepare: self.outgoing.append(self.incoming.pop())
self=TwoStackQueue{'incoming':[...], 'outgoing':[...]}

L13 _prepare: self.outgoing.append(self.incoming.pop())
self=TwoStackQueue{'incoming':[], 'outgoing':[..., ...]}

L20 peek: self._prepare()
self=TwoStackQueue{'incoming':[], 'outgoing':[..., ...]}

L11 _prepare: if not self.outgoing:
self=TwoStackQueue{'incoming':[], 'outgoing':[..., ...]}

... 7 intermediate state changes omitted ...

L13 _prepare: self.outgoing.append(self.incoming.pop())
self=TwoStackQueue{'incoming':[], 'outgoing':[...]}

L16 pop: self._prepare()
self=TwoStackQueue{'incoming':[], 'outgoing':[...]}

L17 pop: return self.outgoing.pop()
self=TwoStackQueue{'incoming':[], 'outgoing':[]}

L24 empty: return not self.incoming and not self.outgoing
self=TwoStackQueue{'incoming':[], 'outgoing':[]}

Result: [None, None, 1, 1, None, 2, 3, True]. A new incoming value waits behind older outgoing values.

run_operations(TwoStackQueue, [("empty",)])

L5 __init__: self.incoming, self.outgoing = [], []
self=TwoStackQueue{'incoming':[], 'outgoing':[]}

L24 empty: return not self.incoming and not self.outgoing
self=TwoStackQueue{'incoming':[], 'outgoing':[]}

Result: [True]. Both stacks begin empty.

Why the solution is correct

A transfer reverses the entire pending incoming segment, making its oldest element accessible first. Existing outgoing values predate all incoming values, so exhausting them before another transfer preserves FIFO order across all operations.

Time and space

O(1) amortized time per operation and O(n) space. One transfer-triggering operation may take O(n), but each value transfers at most once.

Common mistakes

Transferring on every pop can reorder pending elements. Calling every operation worst-case O(1) confuses amortized and individual costs.

Reasoning card

State: outgoing holds the older queue segment in pop order; incoming holds the newer segment in insertion order from bottom to top.

Invariant: Output-stack top is the oldest queued item.

Decision to rehearse: Transfer input to output only when output is empty.

Finish: Report empty only when both stacks are empty

Transfer exercise

Prove the amortized bound with a potential proportional to the number of elements in incoming.