Implement Queue Using Stacks — Amortized O(1) Lazy Transfer

Problem Statement#

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue should support push, peek, pop, and empty operations.

You must use only standard stack operations: push to top, peek or pop from top, size, and is empty.

Constraints:

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

Input:  ["MyQueue","push","push","peek","pop","empty"]
        [[],[1],[2],[],[],[]]
Output: [null,null,null,1,1,false]

Input:  ["MyQueue","push","push","pop","peek"]
        [[],[1],[2],[],[]]
Output: [null,null,null,1,2]

Input:  ["MyQueue","push","pop","empty"]
        [[],[5],[],[]]
Output: [null,null,5,true]

Why This Problem Matters#

LeetCode 232 is the companion to LC 225 (implement stack using queues). Together they teach the deepest possible understanding of LIFO and FIFO semantics. This problem is asked at Amazon, Google, and Microsoft precisely because it tests amortized complexity analysis — one of the most frequently misunderstood concepts in interviews.

The two-stack queue is not just an academic exercise. Many real systems separate write buffers from read buffers. The same pattern appears in printer spoolers, network packet buffers, and CPU pipelines where writes and reads operate at different rates.

Interviewers love this problem because candidates who do not understand amortized analysis will incorrectly claim "pop is O(n), so the solution is inefficient." Candidates who understand it will explain that each element is pushed and transferred at most once, making the total work O(n) for n operations — amortized O(1) per operation.

The Core Insight#

Two stacks can simulate a queue because reversing a reversed sequence restores the original order.

• Use inbox (write stack) for all push operations — O(1) always.
• Use outbox (read stack) for pop and peek.
• When outbox is empty and you need to read, transfer everything from inbox to outbox in one batch. This reverses the order twice — push reverses once, transfer reverses again — yielding FIFO order.

The key insight for amortized O(1): each element is moved from inbox to outbox at most once. Over n operations, the total transfer cost is at most n, making the amortized cost per operation O(1).

Visual Dry Run#

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

After push(1), push(2), push(3):

inbox:  [3, 2, 1]  (top = 3, most recently pushed)
outbox: []

pop() called — outbox is empty, trigger transfer:

Move 3 from inbox top to outbox → outbox: [3]
Move 2 from inbox top to outbox → outbox: [3, 2]
Move 1 from inbox top to outbox → outbox: [3, 2, 1]  (top = 1)
inbox: []

pop() from outbox top = 1 (correct FIFO — first in, first out).

Solution (Optimal)#

# Python — two-stack lazy transfer, amortized O(1) per operation
class MyQueue:
    def __init__(self):
        self.inbox = []    # write stack: new elements pushed here
        self.outbox = []   # read stack: elements ready in FIFO order
 
    def push(self, x: int) -> None:
        # Always push to inbox — O(1)
        self.inbox.append(x)
 
    def _transfer(self) -> None:
        # Transfer all from inbox to outbox only when outbox is empty
        # This lazy strategy gives amortized O(1) — each element moves once
        if not self.outbox:
            while self.inbox:
                self.outbox.append(self.inbox.pop())
 
    def pop(self) -> int:
        self._transfer()
        return self.outbox.pop()   # outbox top is the queue front
 
    def peek(self) -> int:
        self._transfer()
        return self.outbox[-1]     # peek without removing
 
    def empty(self) -> bool:
        # Queue is empty only when BOTH stacks are empty
        return not self.inbox and not self.outbox

// JavaScript — two-stack lazy transfer, amortized O(1) per operation
class MyQueue {
    constructor() {
        this.inbox = [];    // write stack
        this.outbox = [];   // read stack
    }
 
    push(x) {
        this.inbox.push(x);  // always O(1)
    }
 
    _transfer() {
        // Only transfer when outbox is empty — lazy approach
        if (this.outbox.length === 0) {
            while (this.inbox.length > 0) {
                this.outbox.push(this.inbox.pop());
            }
        }
    }
 
    pop() {
        this._transfer();
        return this.outbox.pop();
    }
 
    peek() {
        this._transfer();
        return this.outbox[this.outbox.length - 1];
    }
 
    empty() {
        return this.inbox.length === 0 && this.outbox.length === 0;
    }
}

Complexity:

Common Mistakes#

1. Transferring on every pop instead of only when outbox is empty. If you transfer every time you pop, you still get correct results but lose the amortized benefit — each element moves back and forth, making pop truly O(n) on average.

2. Not checking both stacks in empty(). If you only check outbox.isEmpty(), you miss elements still in inbox. The queue is empty only when both stacks are empty.

3. Partial transfer: stopping when outbox has one element. Some candidates stop the transfer early to try to be clever. Transfer everything in one batch — partial transfers break the FIFO guarantee for subsequent operations.

4. Transferring back from outbox to inbox. The transfer is one-way: inbox to outbox. Moving elements the other direction scrambles the order permanently.

5. Forgetting the push-after-peek interaction. After a peek, new pushes go to inbox. The next pop correctly gets the front (from outbox) before the newly pushed elements. The two-stack invariant handles this automatically.

Interview Tips#

• State the amortized O(1) claim explicitly: "Each element is pushed once, transferred at most once, and popped once — three O(1) operations per element. So n operations cost O(n) total, amortized O(1) each."
• Draw the two-stack diagram: inbox on the left, outbox on the right, arrow showing the one-time transfer.
• Contrast with the eager approach (transfer on every push): push is O(n), pop is O(1), but no better amortized performance.
• If asked why not just use a deque: in practice, yes — but this problem tests conceptual understanding of amortized complexity and LIFO vs FIFO, not practical design.

Follow-up Questions#

1. Implement a stack using queues (LC 225) — the reverse problem; rotation on push makes push O(n) and pop O(1).
2. What is the amortized cost if you transfer on push instead of pop? Push becomes O(n), pop becomes O(1); total amortized performance is identical.
3. Can you do all operations O(1) worst case? No — at some point you must reverse order, which requires O(n) work.
4. Implement a deque using two stacks. Push-front and pop-front use the left stack; push-back and pop-back use the right stack; trigger transfer when the target stack is empty.
5. Design a queue with max operation in O(1). Use an additional monotonic deque alongside the two-stack structure to track the running maximum.

Key Takeaways#

• Two-stack queue: inbox for writes, outbox for reads; transfer lazily from inbox to outbox only when outbox is empty.
• Amortized O(1) per operation: each element is moved at most once — push to inbox, transfer to outbox, pop from outbox — so n operations cost O(n) total.
• The empty() check must inspect both stacks — elements may still be in inbox when outbox is empty.
• Lazy transfer is the key insight: do not transfer eagerly on every push; wait until outbox is needed.
• This pattern separating read and write into two buffers that occasionally sync appears in real systems: print queues, network buffers, and double-buffering in graphics pipelines.
• Understanding amortized O(1) (not worst-case O(1)) is the single most important point to communicate in an interview about this problem.