Stack Using Queues LeetCode 225 Deep Dive

LeetCode 225 — Implement Stack using Queues — asks you to implement a LIFO (last-in, first-out) stack using only standard queue operations. The stack must support four operations: push(x) which pushes element x onto the top, pop() which removes and returns the top element, top() which returns the top element without removing it, and empty() which returns true if the stack is empty.

The challenge is that a queue is FIFO (first-in, first-out): the first element enqueued is the first element dequeued. A stack is the opposite — the last element pushed is the first element popped. You cannot use any built-in stack structure; you may only use push-to-back (enqueue) and pop-from-front (dequeue) queue operations, along with peek at front and size checks.

The problem permits using one or two queues. Most solutions use two queues for the pop-expensive approach and one queue for the push-expensive rotation approach. The push-expensive single-queue approach is the canonical interview answer because it keeps pop and top O(1), the two operations called most frequently in stack-heavy algorithms.

The push-expensive approach maintains the invariant that the front of the queue always holds the most recently pushed element — i.e., the stack top. When you push a new element, enqueue it to the back of the queue. Then rotate all the elements that were already in the queue (size - 1 of them) from the front to the back. This moves the newly pushed element from the back to the front, where it belongs as the new stack top.

After rotation, pop() and top() become trivially O(1): pop simply dequeues from the front, and top peeks at the front. The empty() operation checks whether the queue is empty. Push is O(n) due to the rotation, but this is an acceptable tradeoff when reads (pop and top) dominate writes (push) — which is the common case for stack usage in algorithms like DFS, expression evaluation, and bracket matching.

Using two queues is not necessary for this approach. One queue suffices: enqueue the new element, then dequeue-and-reenqueue size-1 elements. The queue maintains its FIFO discipline throughout; you are simply cycling elements to enforce LIFO order from the perspective of the dequeue end.

Consider a queue that currently holds [3, 1, 2] (front to back), representing the stack with 2 on top. You push 4. After enqueuing 4, the queue is [3, 1, 2, 4]. There are now four elements. The new element 4 must be at the front. You rotate size - 1 = 3 elements: dequeue 3 and enqueue it (queue becomes [1, 2, 4, 3]), dequeue 1 and enqueue it (queue becomes [2, 4, 3, 1]), dequeue 2 and enqueue it (queue becomes [4, 3, 1, 2]). Now 4 is at the front — the stack top.

The rotation count is always size - 1, not size. Rotating all size elements would cycle the queue back to its original state, leaving the new element at the back where it started — accomplishing nothing. Rotating exactly size - 1 elements leaves the new element at the front. This off-by-one is the most common mistake when implementing the rotation trick.

After the rotation, the queue [4, 3, 1, 2] correctly represents the stack with 4 on top, then 3, then 1, then 2 at the bottom. Any subsequent pop just dequeues from the front (returning 4), and the queue becomes [3, 1, 2] — exactly the original state before the push of 4. The LIFO invariant is preserved.

The pop-expensive approach uses two queues, commonly named q1 and q2. Push is O(1): simply enqueue the new element to q1. Pop is O(n): transfer all elements from q1 except the last one into q2, then dequeue the last element from q1 — that is the stack top. Finally, swap q1 and q2 so that q1 is ready for the next operation.

The top() operation follows the same logic as pop() but re-enqueues the last element instead of discarding it, or alternatively stores the last enqueued value in a member variable during push. The empty() operation checks whether q1 is empty. Push is O(1), pop is O(n), top is O(n) unless cached.

The pop-expensive approach is less commonly asked for in interviews because pop and top being O(n) means every stack read is expensive. In contrast, the push-expensive approach makes reads O(1), which is far more useful in practice. The pop-expensive approach is sometimes introduced first as the intuitive baseline before the more elegant push-expensive single-queue solution is revealed.

The single-queue optimization is the push-expensive approach implemented with exactly one queue instead of two. After pushing the new element to the back of the queue, rotate size - 1 elements from the front to the back. The result is identical to the two-queue push-expensive approach: the new element ends up at the front, pop and top are O(1), and push is O(n).

Using one queue instead of two reduces space from O(2n) to O(n) and simplifies the code — there is no queue swapping, no transfer loop, no q1/q2 naming. The single-queue version is considered the cleanest implementation of LeetCode 225 and is the solution most interviewers expect when they ask the follow-up: "Can you do it with one queue?"

In Python you can use collections.deque, which supports O(1) appendleft/append (enqueue) and popleft (dequeue). In Java, use ArrayDeque or LinkedList which implement the Queue interface. Both languages allow the single-queue rotation with a simple for loop: for _ in range(self.q.qsize() - 1): self.q.put(self.q.get()).

Python single-queue push-expensive implementation using collections.deque: class MyStack: def __init__(self): self.q = collections.deque(); def push(self, x): self.q.append(x); for _ in range(len(self.q) - 1): self.q.append(self.q.popleft()); def pop(self): return self.q.popleft(); def top(self): return self.q[0]; def empty(self): return not self.q. Push is O(n) due to the rotation, pop and top are O(1), empty is O(1). The deque supports O(1) append and popleft making the rotation efficient per operation.

Java single-queue push-expensive implementation using LinkedList: class MyStack { Queue<Integer> q = new LinkedList<>(); public void push(int x) { q.add(x); for (int i = 0; i < q.size() - 1; i++) q.add(q.poll()); } public int pop() { return q.poll(); } public int top() { return q.peek(); } public boolean empty() { return q.isEmpty(); } } Note that q.size() is evaluated before the loop modifies the queue — in Java the loop bound must capture the original size. Using a cached int size = q.size() before the loop is safer: for (int i = 0; i < size - 1; i++) q.add(q.poll()).

Both implementations share the same structure: one queue, push with rotation, O(1) pop/top. The time complexity for n operations is O(n) total for pops and tops (each O(1)), and O(n²) total for pushes (each push is O(current_size)). The space complexity is O(n) for n elements in the queue. In competitive programming and interviews, the single-queue push-expensive version is the expected optimal solution.

Implement Queue using Stacks — LeetCode 232 — is the exact inverse of LeetCode 225. Instead of simulating a stack with queues, you simulate a queue with stacks. The push-expensive and pop-expensive tradeoffs are symmetric: one stack is kept in reversed order so that the queue front is always at the top of that stack. The amortized pop-expensive approach for LeetCode 232 is more commonly taught because amortized O(1) pop is achievable with two stacks.

Min Stack — LeetCode 155 — asks you to design a stack that supports push, pop, top, and getMin in O(1). The trick is maintaining a parallel auxiliary stack that tracks the running minimum. This problem tests awareness of auxiliary data structure design — the same design thinking required for the queue-to-stack transformation in LeetCode 225.

The stack-queue duality family on LeetCode forms a cohesive cluster: Implement Stack using Queues (225), Implement Queue using Stacks (232), Design Circular Queue (622), Min Stack (155), and Max Stack (716). Mastering the rotation trick and the push/pop-expensive tradeoffs in LeetCode 225 gives you the foundational insight to approach all problems in this family. The key insight shared across all of them is that two complementary data structures can simulate each other at the cost of one O(n) operation per use.