Queue from two stacks

38 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

You only have stacks, piles where you can touch the top card only, and you are asked to build a queue, a line where the first one in is the first one out. Push 1, 2, 3 into the queue, then pop: you must get 1, the oldest. But a stack with 1, 2, 3 pushed has 3 on top.

By hand with one stack you could dig: to reach the bottom card, move every card above it to a side pile, take the bottom one, and move everything back. For a queue of n cards that is about 2n moves for every pop, and if you move the cards back every time, a sequence of n pops costs about n² moves.

The wasteful step is moving the cards back. When you pour a pile onto a side pile, the order flips: 3, 2, 1 becomes 1 on top. That flipped order is exactly a queue's order. Why undo it?

Build the structure, one piece at a time

Piece 1: an inbox stack. Every push goes onto the inbox. After push 1, push 2, push 3 the inbox is 1, 2, 3 with 3 on top.

Piece 2: an outbox stack. A pop takes from the outbox. If the outbox is empty, pour the whole inbox into it, one card at a time: 3 moves first and lands at the bottom, then 2, then 1 lands on top. Now the outbox is 3, 2, 1 with 1 on top. Pop gives 1.

Piece 3: leave the outbox alone. New pushes keep going to the inbox. The outbox still has 3, 2 with 2 on top, and those are older than anything in the inbox, so pops keep coming from the outbox until it is empty. Only then do we pour again.

Why it is correct

The invariant: reading the outbox from top to bottom and then the inbox from bottom to top gives all the queued elements from oldest to newest.

A push adds the newest element to the top of the inbox, which is the end of that reading order, so the invariant holds. A pop when the outbox is non-empty takes its top, which is the first element of the reading order, the oldest. A pour moves the inbox cards one by one onto the outbox; the inbox's bottom card (oldest) is moved last, so it ends on top of the outbox. Pouring only happens when the outbox is empty, so no older card gets buried under newer ones.

That last point is the subtle one. If you poured while the outbox still had cards, the newer inbox cards would land on top of older outbox cards, and the next pop would return a newer card first. Waiting until the outbox is empty prevents that.

Why it is fast

Follow one card. It is pushed onto the inbox once, moved to the outbox once, and popped once. Three moves in its whole life, no matter how many operations happen around it.

total moves for n elements ≤ 3n, so each operation is O(1) amortised

A single pop that triggers a pour can take n moves, but those moves pay for the next n pops, which are then free. Averaged over the sequence, each operation costs a constant. Compared with digging, which costs n moves per pop every time, this is the difference between n² and 3n.

How to recognise it in an interview

The cues are "implement a queue using stacks", "implement a stack using queues", "amortised O(1)", or any design where one structure must be simulated with another. Say: "Two stacks, one for arrivals and one for departures; pouring one into the other reverses the order, and I only pour when the departure stack is empty so each element moves at most once."

Implement Queue using Stacks is the example above. Implement Stack using Queues is the mirror: after each push, rotate the queue so the newest element is at the front, costing O(n) per push but O(1) per pop. Design Circular Queue is a different trick, a fixed array with head and tail indices that wrap around.

02The idea in one line

Push to inbox; when outbox is empty, pour inbox over so the order flips.

Reach for it when: Implement queue with stacks, undo/redo, amortised O(1) designs.

Cost: O(1) amortised per op.

03The walk-through, step by step

The video works one example: Queue via two stacks: push 1,2,3; pop; push 4; pop. These are its captions in order, so you can follow without the video or check a step you missed.

1. Two stacks: pushes land in inbox, pops come from outbox
2. push(1): onto inbox
3. push(2): onto inbox
4. push(3): onto inbox
5. pop(): outbox empty, pour inbox over, the order flips
6. pop() = 1: the oldest element was on top of outbox
7. push(4): inbox again; outbox keeps the older ones
8. pop() = 2: the oldest element was on top of outbox
9. pop() = 3: the oldest element was on top of outbox
10. Outbox empty again: next pop pours 4 over
11. Each element is moved at most once: O(1) amortised per op

04Asked at Google

5 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Queue & Deque: Monotonic deque window max, Queue over a time window.