Implement Queue using Stack
Implement Queue Using Stacks: implement FIFO push/pop/peek using only stack operations.
- 1 <= x <= 9
- At most 100 calls will be made to push, pop, peek, and empty.
- All the calls to pop and peek are valid.
Intuition
To implement queue using stacks you have to build FIFO out of a structure that is strictly LIFO. A stack hands back the newest item; a queue must hand back the oldest. So somewhere, the order has to be reversed.
A single stack cannot do it without emptying itself on every operation. But notice what happens when you pour one stack into another: the bottom of the first becomes the top of the second. One transfer reverses the order, and reversal is exactly what converts LIFO into FIFO.
That gives the two-stack design. An inbox receives every push, keeping newest on top. An outbox serves every pop, holding the elements already reversed so the oldest is on top. Pushes go to one, removals come from the other.
The part that makes this efficient is when you pour:
- Only transfer when the outbox is empty, never on every operation.
If you poured on every push you would be doing O(n) work constantly. By waiting until the outbox runs dry, each element moves from inbox to outbox exactly once in its entire lifetime. Any single pop might trigger an expensive transfer, but that cost is spread across all the cheap pops that follow, giving amortised O(1). Pouring early would also be wrong, not just slow — mixing newly pushed elements into an already-reversed outbox breaks the ordering.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for amortized O(1) time and O(n) space.
Give each stack one direction
inbox only receives pushes; outbox only serves pops and peeks. Neither ever reverses role. Keeping the two responsibilities separate is what makes the invariant easy to state and hard to break.
Push straight onto the inbox
A push is a single stack push onto inbox — genuinely O(1), with no inspection of the outbox. The new element is the newest, so it belongs at the top of the collecting stack.
Transfer only when the outbox is empty
Before a pop or peek, if outbox is empty, pour every element from inbox into it. The pouring reverses the order, so the oldest element ends up on top. If the outbox still has elements, do not pour — those are older and must be served first.
Serve from the outbox top
Once the transfer rule is honoured, the top of outbox is always the oldest element in the queue. Pop returns it and removes it; peek returns it and leaves it. Both are single stack operations.
Understand the amortised bound
Each element is pushed to inbox once, popped from inbox once, pushed to outbox once, and popped from outbox once — four operations over its whole lifetime, no matter how many calls happen around it. Spread across n operations that is O(1) each on average, even though one individual pop can cost O(n).
Report size and emptiness across both
The queue holds everything in both stacks, so size is the sum of the two lengths and empty is true only when both are empty. Checking just one is a common bug that reports an empty queue while the inbox is still full.
Solution & live demo
Common pitfalls
Pouring on every operation
def _shift(self):
while self.inbox:
self.outbox.append(self.inbox.pop())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
# push: move outbox -> inbox, append, move back
# 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
return not self.outbox
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.
Edge cases
Serve outbox; inbox must NOT be poured on top (would reorder).
Same rule as pop minus removal — always outbox top after a lazy pour.