LeetCode #232 Medium

Implement Queue using Stack

Implement FIFO push/pop/peek using only stack operations.

stackqueuedesignamortized

02

Intuition

Two stacks: inbox collects pushes; outbox serves pops. Pouring inbox into outbox reverses order once — oldest lands on top. Only pour when outbox is empty, and each element makes the trip exactly once → amortized O(1).

How to spot this pattern

The mirror design problem, and the more elegant answer: pouring one stack into another reverses the order, so two stacks give FIFO. The key is pouring only when the outbox is empty — that makes the cost amortised O(1), because each element is moved across exactly once in its lifetime. Amortised analysis is the point of this question.

03

Approach

1

Two one-way stacks

push → inbox. pop/peek → outbox top. Direction of each stack never changes.

2

Lazy transfer

Only when outbox runs dry, pour all of inbox into it. Elements already in outbox stay correctly ordered.

3

Amortized analysis

Each element is pushed twice and popped twice total, ever — O(1) average per operation.

04

Solution & live demo

▶1class MyQueue:
▶2    def __init__(self):
▶3        self.inbox, self.outbox = [], []
▶4 
▶5    def push(self, x):
▶6        self.inbox.append(x)
▶7 
▶8    def _shift(self):
▶9        if not self.outbox:
▶10            while self.inbox:
▶11                self.outbox.append(self.inbox.pop())
▶12 
▶13    def pop(self):
▶14        self._shift()
▶15        return self.outbox.pop()
▶16 
▶17    def peek(self):
▶18        self._shift()
▶19        return self.outbox[-1]
▶20 
▶21    def empty(self):
▶22        return not self.inbox and not self.outbox

05

Common pitfalls

Pouring on every operation

✗ Wrong

def _shift(self):
    while self.inbox:
        self.outbox.append(self.inbox.pop())

✓ Right

def _shift(self):
    if not self.outbox:
        while self.inbox:
            self.outbox.append(self.inbox.pop())

Pouring while the outbox still holds items puts newer elements underneath older ones, destroying FIFO order. The guard is what keeps the two halves consistent — and what makes each element cross only once.

Pouring back and forth on every call

✗ Wrong

# push: move outbox -> inbox, append, move back

✓ Right

# push: append to inbox only; pour lazily on pop/peek

That makes every operation O(n) instead of amortised O(1). Elements should sit in the inbox until someone actually needs to read from the front.

Checking only one stack for emptiness

✗ Wrong

return not self.outbox

✓ Right

return not self.inbox and not self.outbox

Elements may be waiting in the inbox that haven't been poured yet, so an empty outbox says nothing about the queue as a whole. The queue is empty only when both halves are.

06

Edge cases

pop with both stacks holding items

Serve outbox; inbox must NOT be poured on top (would reorder).

peek after many mixed ops

Same rule as pop minus removal — always outbox top after a lazy pour.

07

Complexity

Time

amortized O(1)

Space

O(n)

Each element crosses stacks once.