Implement Queue using Stacks is one of those problems where interviewers care more about whether you can explain amortized O(1) than whether you can write the code. The solution is short, but the amortized argument — why each element is transferred at most once across its lifetime — is what separates candidates who memorized the pattern from those who actually understand it.

---

The Problem

Implement a first-in-first-out (FIFO) queue using only two stacks. The queue must support push, pop, peek, and empty, all with amortized O(1) time.

Example

MyQueue q = new MyQueue();
q.push(1); q.push(2);
q.peek();  // → 1
q.pop();   // → 1
q.empty(); // → false

Already comfortable with the solution? Practice it in a mock interview →

---

What Interviewers Are Actually Testing

Skill	What Interviewers Observe
Two-stack insight	Do you know to use an inbox and outbox stack?
Amortized complexity	Can you explain why O(1) amortized holds even though a single pop can be O(n)?
Lazy transfer	Do you only transfer when the outbox is empty, not on every operation?
Design clarity	Is the code well-organized with clear separation of concerns?

---

Step 1: Clarifying Questions

1. What operations must be O(1)? Amortized O(1) is allowed — confirm.
2. Is pop called on an empty queue? Assume valid operations per constraints.

---

Step 2: The Naive (O(n)) Approach

On every push, transfer all elements from stack1 to stack2, push the new element to stack2, transfer everything back to stack1. FIFO maintained, but O(n) per push. Not acceptable.

---

Step 3: The Key Insight

Use two stacks: an inbox (in_stack) and an outbox (out_stack). Push always goes to the inbox. Pop reads from the outbox. Only when the outbox is empty do you transfer from inbox to outbox. Each element is transferred at most once, giving amortized O(1) per operation.

---

Step 4: Optimal Strategy

• Push: append to in_stack. O(1).
• Pop/Peek: if out_stack is empty, transfer all elements from in_stack to out_stack (this reverses their order, making the oldest element the top). Then pop/peek from out_stack.
• Empty: both stacks are empty.

---

Python Implementation

class MyQueue:
    def __init__(self):
        self.in_stack = []   # Receives new elements
        self.out_stack = []  # Serves old elements in FIFO order

    def push(self, x: int) -> None:
        self.in_stack.append(x)

    def _transfer(self) -> None:
        """Move all elements from in_stack to out_stack (reverses order)."""
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

    def pop(self) -> int:
        self._transfer()
        return self.out_stack.pop()

    def peek(self) -> int:
        self._transfer()
        return self.out_stack[-1]

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

---

Time & Space Complexity

Operation	Amortized	Worst Case
push	O(1)	O(1)
pop	O(1)	O(n)
peek	O(1)	O(n)
empty	O(1)	O(1)

Amortized argument: Each element is pushed once → O(1). Each element is transferred at most once → O(1). Each element is popped once → O(1). Total work per element: O(1). Any single pop that triggers a transfer is O(n), but those n elements were each pushed once, so the amortized cost per element is still O(1).

---

Common Interview Mistakes

1. Transferring on every push. This gives O(n) push instead of amortized O(1) pop — same total work, but worse distribution and missing the insight.

2. Not explaining amortized complexity. Just saying “O(1)” without the amortized argument suggests you don’t understand why.

3. Not implementing _transfer as a helper. Duplicating the transfer logic in pop and peek leads to bugs.

4. Wrong empty check. The queue is empty only when both stacks are empty — not just one.

---

What a Strong Candidate Sounds Like

“I’ll use two stacks: an inbox and an outbox. Push always goes to the inbox. Pop reads from the outbox. I only transfer from inbox to outbox when the outbox is empty. Each element is transferred at most once — pushed once, transferred once, popped once — so the amortized cost is O(1) per operation even though a single pop can trigger an O(n) transfer.”

---

Example Interview Dialogue

Interviewer: Walk me through a scenario where a pop takes O(n).

Candidate: Say I push 5 elements. The inbox has [1,2,3,4,5]. When I call pop for the first time, the outbox is empty, so I transfer all 5 — the outbox becomes [5,4,3,2,1]. That transfer was O(5). But now the next 4 pops are O(1) each — I just pop from the outbox. Over 5 operations, the total work is 5+4 = 9, which is still O(1) amortized per element.

Interviewer: Why is lazy transfer better than eager transfer?

Candidate: Eager transfer — moving everything on every push — does O(n) work per push. Lazy transfer batches the work: each element moves from inbox to outbox exactly once. The total work across all operations is O(n), making every individual operation O(1) amortized.

---

Related Problems to Practice

• Min Stack — Design with auxiliary state.
• Valid Parentheses — Stack fundamentals.
• Basic Calculator — Stack-based expression evaluation.

---

Practice This in a Mock Interview

The amortized O(1) argument is the make-or-break moment in this problem. Practice explaining it out loud — interviewers listen for whether you truly understand per-element accounting or just memorized the answer.

Start a mock interview for Implement Queue using Stacks on Intervu.

---

Further reading:

• How to Prepare for a Coding Interview in 2026, the complete roadmap
• Why LeetCode alone isn’t enough, and what to practice instead
• Practice any LeetCode problem as a live mock interview
• The Grind 75 Pathway, a structured study plan with AI practice links
• Browse all walkthroughs on GitHub