Implement Stack Using Queues — Queue Rotation Design Problem

Problem Statement#

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support push, top, pop, and empty operations.

You must use only standard queue operations — push to back, peek/pop from front, size, and is empty.

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All calls to pop and top are valid.

Input:  ["MyStack","push","push","top","pop","empty"]
        [[],[1],[2],[],[],[]]
Output: [null,null,null,2,2,false]
Explanation:
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top();   // return 2
myStack.pop();   // return 2
myStack.empty(); // return False

Input:  ["MyStack","push","top","pop","empty"]
        [[],[1],[],[],[]]
Output: [null,null,1,1,true]

Input:  ["MyStack","push","push","push","pop","top"]
        [[],[1],[2],[3],[],[]]
Output: [null,null,null,null,3,2]

Why This Problem Matters#

This is a classic data-structure design problem asked at Amazon, Microsoft, and Google. It forces you to understand the fundamental difference between LIFO (stack) and FIFO (queue) semantics at a mechanical level. If you can simulate one using the other, you truly understand both.

Beyond the interview, this pattern appears in systems where you only have queue primitives — for example, some message-queue systems or hardware FIFOs — but need stack-like access. The rotation trick also demonstrates how clever ordering can compensate for missing primitives.

Interviewers follow this problem with "now implement a queue using stacks" (LC 232), "what if push should be O(1) instead of pop?" and "can you do this amortized O(1) per operation?" These are variants that require understanding the trade-offs between eager and lazy approaches.

The Core Insight#

A queue is FIFO; a stack is LIFO. The key insight: if after every push you rotate all previous elements to the back of the queue, the newly pushed element ends up at the front — exactly where the stack top should be.

Single-queue approach (expensive push, cheap pop):

• push(x): append x to the queue, then rotate all previous elements (queue size minus one) from front to back. Now x is at the front.
• pop(): dequeue from front (which is the most recently pushed element).
• top(): peek at the front.
• empty(): check if the queue is empty.

Two-queue approach (lazy transfer on pop):

• Keep elements in q1. On pop, transfer all but the last element to q2, remove and return the last element, then swap q1 and q2. This makes push O(1) but pop O(n).

Both are valid; the single-queue rotation is more elegant and commonly expected.

Visual Dry Run#

Single-queue rotation, push sequence: 1, 2, 3

After push(1):

q: [1]   (front → back)

After push(2): append 2, rotate 1 element:

q before rotation: [1, 2]
rotate 1:          [2, 1]  ← 2 is at front, which is the "top"

After push(3): append 3, rotate 2 elements:

q before rotation: [2, 1, 3]
rotate 1st:        [1, 3, 2]
rotate 2nd:        [3, 2, 1]  ← 3 is at front

top() = 3, pop() removes 3, next top() = 2. This is correct LIFO behavior.

Solution (Optimal)#

# Python — single queue rotation, O(n) push, O(1) pop/top
from collections import deque
 
class MyStack:
    def __init__(self):
        self.q = deque()
 
    def push(self, x: int) -> None:
        self.q.append(x)
        # Rotate all previous elements to the back
        # so the new element is at the front (stack top)
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())
 
    def pop(self) -> int:
        return self.q.popleft()  # front is always the stack top
 
    def top(self) -> int:
        return self.q[0]         # peek at front without removing
 
    def empty(self) -> bool:
        return len(self.q) == 0

// JavaScript — single queue rotation, O(n) push, O(1) pop/top
class MyStack {
    constructor() {
        this.q = [];
    }
 
    push(x) {
        this.q.push(x);
        // Rotate all previous elements to the back
        for (let i = 0; i < this.q.length - 1; i++) {
            this.q.push(this.q.shift());
        }
    }
 
    pop() {
        return this.q.shift();   // front is always the stack top
    }
 
    top() {
        return this.q[0];        // peek without removing
    }
 
    empty() {
        return this.q.length === 0;
    }
}

Complexity:

Common Mistakes#

1. Rotating the wrong number of times. After pushing x, you need to rotate len(q) - 1 times (the size before push plus one, minus one). A common off-by-one is rotating len(q) times, which brings the new element back to the back.

2. Using queue[0] for top without rotation. If you do not rotate on push, queue[0] is the oldest element (FIFO order), not the newest. The rotation is what makes queue[0] the stack top.

3. Two-queue approach: forgetting to swap after transfer. When you transfer elements from q1 to q2 during pop, you must swap the references; otherwise the next push goes to the wrong queue.

4. Calling pop before checking empty. The problem guarantees valid calls, but in practice always guard pop with an empty check — interviewers may ask you to handle invalid calls.

5. Using len() inside the rotation loop. In some implementations, if you compute len(q) inside the loop and q is mutating, you may loop too many or too few times. Capture the count before the loop.

Interview Tips#

• Lead with the insight: "A queue is FIFO; I need LIFO. If I always keep the most recently pushed element at the front, I can simulate a stack using dequeue-from-front operations."
• Compare the two approaches: "Single-queue rotation makes push O(n) but pop/top O(1). Two-queue lazy transfer makes push O(1) but pop O(n). Choose based on access patterns."
• Mention amortized analysis: if the workload has many pushes and few pops, single-queue is better; if pops are rare, two-queue is better.
• For follow-up "can you make all operations O(1)?": explain that it is impossible — you fundamentally need to reverse the order at some point, which costs O(n) somewhere.

Follow-up Questions#

1. Implement a queue using stacks (LC 232) — the reverse problem; use two stacks with lazy transfer.
2. Make push O(1) instead of pop O(1) — use the two-queue transfer-on-pop approach.
3. What if you need a stack with O(1) min? — LC 155 Min Stack, use an auxiliary stack tracking minimums.
4. Implement a deque using two stacks — push to one stack, pop from the other with lazy transfer.
5. Design a stack that supports getMin in O(1) time and O(1) space — not possible; minimum tracking requires O(n) state in the worst case.

Key Takeaways#

• Simulating LIFO with FIFO requires reversing order at some point; the single-queue rotation achieves this on every push.
• The rotation trick: after appending a new element, rotate all previous elements to the back — the new element becomes the front (stack top).
• Push is O(n) in the single-queue approach; pop, top, and empty are all O(1).
• The two-queue approach makes push O(1) at the cost of O(n) pop — useful if writes are far more frequent than reads.
• This problem and its reverse (LC 232 queue-using-stacks) are design interview staples testing your understanding of LIFO vs FIFO at a fundamental level.
• In practice, always use a built-in stack; this problem exists to test conceptual depth, not production code.