Implement Queue using Stacks: The Lazy Two-Stack Transfer

A stack hands you back the newest thing you gave it. A queue must hand back the oldest. Implement Queue using Stacks asks you to fake the second behavior using only the first — and the answer hides one of the most useful ideas in data-structure design: a stack reverses order, so two stacks restore it.

The problem is rated easy, but the follow-up is where interviews are won: make every operation amortized O(1). Most candidates reach for a solution that shuffles every element on every push; the good one moves each element at most once — and explaining why that's O(1) on average is the real test.

The same lazy-transfer instinct — do the expensive reorganization only when forced to, then ride it for free — shows up in buffered I/O, functional queues, and dynamic arrays.

The problem#

Design a first-in-first-out (FIFO) queue using only two stacks. Your MyQueue class must support the standard queue API:

• push(x) — enqueue x at the back
• pop() — remove and return the front element
• peek() — return the front element without removing it
• empty() — return true if the queue holds nothing

You may only use standard stack operations: push to top, pop from top, peek at top, and size/empty checks. No indexing into the middle, no shift().

The constraint is the whole problem. An array's shift() would trivially give FIFO — but you're limited to LIFO primitives, so the order has to be manufactured.

The brute force baseline#

The direct approach keeps one stack permanently in queue order: on every push, drain the stack into a helper, drop the new element at the bottom, and drain everything back.

pop and peek are O(1), but every push moves all n existing elements twice — out and back. A workload of n pushes costs O(n²) total stack operations, and the work is wasted: the queue gets reorganized on every push even if nobody ever asks for the front. Interviewers accept this as a baseline and immediately ask you to beat it.

The key insight: transfer lazily, reverse once#

This is the Two Stacks pattern. Split the responsibilities:

• inStack receives every push. Newest on top, oldest at the bottom — LIFO order.
• outStack serves every pop and peek. When it has elements, its top is exactly the queue front.

The bridge between them is one observation: draining a stack into another stack reverses it. Pop inStack repeatedly and push each element onto outStack, and the element at the bottom of inStack — the oldest one — lands on top of outStack. One reversal converts LIFO into FIFO.

The second half of the insight is when to transfer: only when outStack is empty and a front-access is needed. Never earlier. Elements already sitting in outStack are older than anything in inStack, so they must all leave first. Transferring while outStack still has elements would bury older elements under newer ones and corrupt the order.

This laziness is what makes the cost analysis work. Each element makes a fixed journey: pushed onto inStack once, moved to outStack at most once, popped off outStack at most once. Three stack operations per element, ever — so any sequence of n operations costs O(n) total, amortized O(1) each.

The optimal solution#

This is the exact algorithm the visualizer steps through:

Three details carry the correctness:

• transfer() guards itself with outStack.length === 0. Calling it is always safe; it only does work when outStack has run dry.
• pop() and peek() both call transfer() first, so the front element is always on top of outStack by the time they read it.
• empty() checks both stacks — after a transfer, everything lives in outStack; right after pushes, everything lives in inStack.

Walkthrough: push(1), push(2), peek(), pop(), empty()#

Stacks are written bottom → top, so the rightmost value is the top.

Step 3 is the whole trick in one row: inStack held [1, 2] with 2 on top, and the drain popped 2 first, then 1 — so outStack ends as [2, 1] with 1 on top. The oldest element surfaced exactly where a queue front should be. Step 5 shows the payoff of laziness: the pop rides the earlier transfer for free.

Complexity#

The amortized argument, stated the way interviewers want to hear it: charge each element 3 stack operations at push time — entering inStack, its single possible transfer, its final pop. Every later operation spends only pre-paid credit, so n operations never exceed 3n stack ops total. A single pop() after n pushes does O(n) work, but that spike happens at most once per batch of pushes.

Common mistakes#

• Transferring while outStack isn't empty. This is the classic order-corrupting bug. If outStack = [2, 1] and you drain a fresh inStack = [3] on top, outStack becomes [2, 1, 3] — and pop() now returns 3 before 1. Only transfer when outStack has fully emptied.
• Transferring on every push. That's the brute force wearing a disguise. Correct output, O(n) per push, and you'll be asked why you didn't hit the amortized O(1) follow-up.
• empty() checking only one stack. After push(1), pop(), push(2), element 2 sits in inStack while outStack is empty. Checking only outStack reports an empty queue that isn't. Both stacks must be empty.
• Using shift() or index access. array.shift() is a dequeue — using it means you never implemented anything. The exercise only allows push/pop/peek on the two stacks.
• Quoting amortized O(1) as worst-case O(1). A single pop can trigger a full O(n) transfer. The average over any sequence is O(1); one individual operation is not guaranteed to be.

Where this pattern shows up next#

Once "a stack reverses order" clicks, a whole family of stack problems opens up:

• Remove Outermost Parentheses — depth tracking, the simplest stack idea, without even materializing the stack.
• Evaluate Reverse Polish Notation — a stack as an evaluation machine: operands wait, operators consume.
• Next Greater Element I — the monotonic stack, where elements wait on the stack until their answer arrives.
• Daily Temperatures — the same monotonic wait-and-resolve idea at scale.

You can also step through it interactively and watch the transfer fire: the two towers side by side, elements draining from inStack to outStack, and the oldest value surfacing on top exactly when peek() needs it.

FAQ#

Why is implementing a queue with two stacks amortized O(1)?#

Because each element makes a bounded journey: pushed onto inStack once, transferred to outStack at most once, popped at most once — three stack operations for its entire lifetime. Any sequence of n queue operations therefore performs at most about 3n stack operations, which averages to O(1) each. A single pop can still cost O(n) when it triggers a transfer, but that expensive transfer only happens after enough cheap pushes have paid for it.

When exactly should elements move from inStack to outStack?#

Only when outStack is empty and a pop or peek needs the front element. Everything already in outStack is older than everything in inStack, so outStack must fully drain before the inStack batch matters. Transferring early — while outStack still holds elements — stacks newer elements on top of older ones and breaks FIFO order. The lazy rule is both the correctness condition and the source of the amortized O(1) bound.

Does peek() change the state of the queue?#

It can move elements between the two stacks, but it never changes the queue's contents or order. If outStack is empty, peek() triggers the same transfer pop() would, then reads outStack's top without removing it. Two consecutive peeks return the same value — the transfer is an internal reorganization, invisible through the queue API.

Why does empty() need to check both stacks?#

Because elements can legitimately live in either stack depending on transfer timing. Right after a series of pushes, everything is in inStack; right after a transfer, everything is in outStack. The queue is empty only when both stacks are empty — checking just one produces false "empty" reports and is one of the most common bugs in this problem.

Is there a mirror problem that implements a stack using queues?#

Yes — LeetCode 225, Implement Stack using Queues, flips the exercise. The standard trick there is rotation: after enqueueing a new element, dequeue and re-enqueue the previous size-1 elements so the newest one reaches the front, making push O(n) but pop and top O(1). The asymmetry is instructive: stacks simulate a queue with an amortized-O(1) lazy reversal, while queues simulate a stack only with an eager O(n) rotation, because a single stack drain reverses order but queue rotations never do.