Implement Stack using Queues: The Queue Rotation Trick

Implement Stack using Queues (LeetCode 225) reads like a hazing ritual: build a LIFO structure while you're only allowed FIFO operations. Nobody ships this in production — if you need a stack, you use a stack. Interviewers keep asking it anyway, because it tests something real: can you restore an invariant at write time so that every read becomes trivial?

The answer is a three-line trick called queue rotation. After enqueuing a new element, cycle every older element behind it. The queue's front now always holds the stack's top, and pop, top, and empty collapse into one-liners.

It's the fifteen-line version of the "pay once on write, read for free" reasoning behind precomputed indexes and materialized views.

The problem#

Design a class MyStack that behaves exactly like a LIFO stack — push(x), pop(), top(), empty() — while internally using only standard queue operations: enqueue to the back, dequeue from the front, peek the front, and check size.

Push 1, then push 2. top() must return 2 — last in, first out. pop() removes that same 2, and empty() is false: 1 is still inside.

The tension is baked into the definitions: a queue hands back the oldest element, a stack must hand back the newest. Something, somewhere, has to invert the order — and the whole problem is deciding where you pay for that inversion.

The brute force baseline#

The instinctive approach uses two queues and pays on read. Pushes go into q1 untouched. To pop, drain everything except the last element into helper q2, take that last element, then swap the queues' roles:

It works, but it is worse on nearly every axis. pop and top both cost O(n) — and top is especially awkward, because after draining to reach the newest element you still need to keep it, so it gets re-enqueued behind everything else. You maintain two structures, a role swap that is easy to forget, and drain logic duplicated across two methods. The order inversion is being paid on every read, in the messiest possible place.

The key insight: rotate on push#

Flip where the work happens. Instead of untangling FIFO order at read time, fix the order the moment it breaks — at write time.

When you enqueue x into a queue that now holds size elements, exactly size - 1 older elements stand in front of it. Dequeue each one and enqueue it again, and x cycles around to the front:

Read that final queue front to back: [3, 2, 1]. That is exactly the stack read top to bottom. This is the queue rotation pattern, and it establishes a single invariant: after every push, the queue holds the stack's elements in top-first order.

Once the invariant holds, everything else is free: pop is a plain dequeue, top a front peek, empty a size check. The entire difficulty of the problem now lives in one small loop inside push.

The optimal solution#

Here push/shift on the array stand in for the queue's enqueue/dequeue, and queue[0] is the front peek. Two details carry all the correctness:

• The loop bound is queue.length - 1, measured after the new element is enqueued. Rotate one fewer time than the size and the new element stops exactly at the front; rotate length times and you've done a full lap back to FIFO order.
• pop and top skip empty checks because LeetCode guarantees they're only called on a non-empty stack. In production code you'd guard both.

You can step through it interactively — the visualizer animates each rotation individually, and the size-minus-one bound clicks once you watch it. Try the "Stress rotation" test case to feel push's O(n) cost grow.

Walkthrough#

Operations: push(1), push(2), push(3), pop(), pop(), pop()

Check the queue column after each push: it always reads as the stack, top first. The three pops then return 3, 2, 1 — perfect LIFO — even though each pop is a plain FIFO dequeue doing zero extra work. Steps 2 and 3 also show the cost curve: one rotation for the second push, two for the third, n − 1 for the nth.

Complexity#

Neither approach makes every operation O(1) — a queue preserves order, so the only reversal available with FIFO primitives is explicit rotation, paid in full on each push. You choose where the O(n) lives; the single-queue version puts it in one place and buys O(1) for all three reads.

Common mistakes#

• Rotating length times instead of length - 1. A full rotation restores the original order, leaving the new element at the back. Nothing crashes — the structure just quietly behaves FIFO, and push(3), push(7), pop() returns 3 instead of 7.
• Rotating before enqueuing. Rotate first and you're cycling the old elements among themselves; the new element then lands at the back anyway. The order is fixed: enqueue, then rotate size − 1.
• Reaching for two queues by default. The two-queue variant doubles the state, needs a role swap after every drain, and makes both pop and top O(n). Single-queue rotation is the answer interviewers are fishing for.
• Using operations a queue doesn't have. Indexing into the middle or removing from the back dissolves the exercise. The JavaScript solution stays legal: push (enqueue back), shift (dequeue front), [0] (peek front), .length (size) — nothing else.
• Claiming true O(1) pop on a plain JavaScript array. shift() re-indexes the remaining elements, so it's O(n) on the array itself; the array is a stand-in for an abstract queue with O(1) dequeue. Say so out loud in an interview.

Where this pattern shows up next#

With structure-impersonation done, the rest of the track is about using stacks to compute:

• Remove Outermost Parentheses — the gentlest next step: tracking nesting depth as an implicit stack.
• Evaluate Reverse Polish Notation — the stack as an evaluation engine: operands pile up, operators collapse them.
• Next Greater Element I — the monotonic stack, the most-asked stack pattern in interviews.
• Daily Temperatures — monotonic stack over indices, the direct follow-up to Next Greater Element.

FAQ#

Why rotate size − 1 times and not size?#

After enqueuing the new element into a queue of size n, exactly n − 1 older elements stand in front of it. Moving each of those to the back leaves the new element parked at the front. A full n rotations move the new element itself around to the rear, restoring the original FIFO order, so the structure stops behaving like a stack. This off-by-one is the most common bug in the problem.

Can you implement a stack using only one queue?#

Yes — one queue is the standard solution. Push enqueues the new element and then rotates the size − 1 older elements behind it, so the queue front is always the stack top; pop, top, and empty then map directly onto dequeue, front-peek, and size-check. Two-queue variants exist but require twice the state and make pop and top O(n) instead of O(1).

What is the time complexity of implementing a stack with queues?#

With the rotation approach: push is O(n) because it performs size − 1 rotations, while pop, top, and empty are all O(1); space is O(n) for the stored elements. The alternative allocation — O(1) push with O(n) pop and top — comes from the two-queue drain approach. No arrangement of FIFO-only operations makes every operation O(1), even amortized.

Why can two stacks make an efficient queue, but queues can't make an efficient stack?#

A stack reverses order: drain one stack into another and the elements come out backwards, and two reversals cancel out. That's why the mirror problem, Implement Queue using Stacks, achieves amortized O(1) — each element moves between stacks at most once, lazily. A queue preserves order, so combining queues never inverts anything; the only inversion available is rotation, and every push pays it in full. The asymmetry is structural, not a missing trick.

Does JavaScript's shift() break the O(1) claims?#

On a plain array, technically yes — shift() is O(n) because the remaining elements get re-indexed. But the complexity analysis is stated against abstract queue operations, where dequeue is O(1), and the array is just the idiomatic LeetCode stand-in. That's the accepted convention in interviews; for a genuinely O(1) dequeue in production JavaScript, use a linked-list deque or a ring buffer.