Loading…

easyStack QueueFrequently asked

Queue Using Two Stacks

Q: How do you solve Queue Using Two Stacks using the Costly Dequeue — Reverse on Every Removal approach?

When to use it: Mention it as the obvious first design, then point out the per-dequeue O(n) cost and improve it with lazy transfer. The naive design makes `enqueue` cheap and `dequeue` expensive. Push every element onto the inbox stack. To dequeue, the front of the queue is the element at the *bottom* of the inbox — unreachable directly. So pour the whole inbox into a temporary stack (reversing it, front now on top), pop the front, then pour everything back into the inbox. **Why pour back.** In this design the inbox is the single source of truth, always holding elements newest-on-top. After grabbing the front you restore that invariant by returning every remaining element to the inbox, ready for the next enqueue. **Why this is correct but slow.** Each dequeue touches all n elements twice — once out, once back — so a single dequeue is O(n) and a sequence of n dequeues is O(n²). For 10⁵ operations that's up to 10¹⁰ moves. Correct, easy to reason about, but quadratic. **The wasteful part.** Notice we pour everything back only to pour it out again on the very next dequeue. That round trip is pure waste. The optimal version simply *leaves* the reversed elements in the outbox and reuses them until they run out — turning repeated O(n) work into amortized O(1). Time complexity: enqueue O(1), dequeue/peek O(n). Space complexity: O(n).

Stack & Queue · 9 of 17 · 9 min

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue must support all the standard operations:

enqueue(x) — add element x to the back of the queue.
dequeue() — remove and return the element at the front of the queue.
peek() — return the element at the front without removing it.
empty() — return whether the queue is empty.

You may only use the standard stack operations: push to top, pop from top, peek at top, size, and is-empty.

In plain English

A stack returns the most recently added element (LIFO); a queue must return the least recently added (FIFO). One reversal converts one into the other, so the design hinges on reversing elements exactly once and reusing that reversed order until it runs out.

Examples

Example 1

Input: enqueue(1), enqueue(2), peek(), dequeue(), empty()
Output: peek→1, dequeue→1, empty→false
Note: 1 was enqueued first, so it's the front. peek returns 1 without removing; dequeue removes and returns 1; 2 still remains so empty is false.

Example 2

Input: enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue()
Output: dequeue→1, dequeue→2
Note: First dequeue pours [1,2,3] from inbox into outbox as [3,2,1] (1 on top), returns 1. Second dequeue reuses outbox, returns 2 — no refill needed.

Example 3

Input: enqueue(5), dequeue(), enqueue(6), dequeue()
Output: dequeue→5, dequeue→6
Note: Refill happens twice because the outbox empties between dequeues — but each element still moves at most twice overall.

Constraints

1 ≤ x ≤ 10⁹ for enqueued values
At most 10⁵ calls total across enqueue, dequeue, peek, empty
dequeue and peek are only called on a non-empty queue
Only stack operations may be used internally — no native queue/deque

Clarifying questions4First question: Are dequeue and peek ever called on an empty queue?Explore questions

Q1.Are dequeue and peek ever called on an empty queue?
Per the constraints, no. If they could be, decide whether to return a sentinel or throw — say it out loud.
Q2.Is amortized O(1) acceptable, or do you need worst-case O(1) per operation?
Two stacks give amortized O(1). True worst-case O(1) needs a more complex design (e.g. three stacks with incremental copying).
Q3.Can I use the language's built-in stack type?
Yes — ArrayDeque in Java or a list in Python, used strictly as a stack. You just can't use a native queue.
Q4.Should peek and dequeue share the refill logic?
Yes — both need the front element, so both trigger a refill when the outbox is empty. Factor it into one helper.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Keep two stacks: an inbox for pushes and an outbox for pops/peeks. enqueue always pushes onto inbox. dequeue/peek work on outbox; when outbox is empty, pour the entire inbox into it, which reverses the order so the oldest element ends up on top. Each element moves at most once between stacks, giving amortized O(1) per operation even though a single dequeue can be O(n).

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that reversing a stack yields a queue, and whether you can justify amortized O(1) instead of claiming a single dequeue is O(1).

Where candidates slip

Transferring elements back and forth on every operation (O(n) each), or refilling the outbox while it still has elements, which corrupts the order.

How to stand out

State the invariant ('outbox holds the front of the queue, oldest on top'), refill only when outbox is empty, and give the amortized argument: each element is pushed and popped at most twice.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Costly Dequeue — Reverse on Every Removal	`enqueue O(1), dequeue/peek O(n)`	`O(n)`	Mention it as the obvious first design, then point out the per-dequeue O(n) cost and improve it with lazy transfer.	Read
2	Two Stacks — Lazy Transfer (Optimal)Optimal	`amortized O(1) per op`	`O(n)`	The answer they want. Phrase it as 'refill the outbox only when it's empty' and give the amortized O(1) argument.	Read

Interactive decision treeInteractiveChoose the right approachFollow the branches and learn why each constraint changes the solution.First decision previewdequeue() / peek()outbox empty?NoYesExplore the full tree

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Costly Dequeue — Reverse on Every Removal

Timeenqueue O(1), dequeue/peek O(n)SpaceO(n)

Mention it as the obvious first design, then point out the per-dequeue O(n) cost and improve it with lazy transfer.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

enqueue is easy — push onto a stack. The hard part is that the element you want to remove is at the BOTTOM of that stack. How do you reach the bottom of a stack?

2Hint 2Explore hint

To remove the front, pour everything into a second stack so the bottom element rises to the top, pop it, then pour everything back.

3Hint 3Explore hint

This works but every dequeue moves all n elements twice. Can you avoid pouring back?

A · Core idea

The naive design makes enqueue cheap and dequeue expensive. Push every element onto the inbox stack. To dequeue, the front of the queue is the element at the bottom of the inbox — unreachable directly. So pour the whole inbox into a temporary stack (reversing it, front now on top), pop the front, then pour everything back into the inbox.

Why pour back. In this design the inbox is the single source of truth, always holding elements newest-on-top. After grabbing the front you restore that invariant by returning every remaining element to the inbox, ready for the next enqueue.

Why this is correct but slow. Each dequeue touches all n elements twice — once out, once back — so a single dequeue is O(n) and a sequence of n dequeues is O(n²). For 10⁵ operations that's up to 10¹⁰ moves. Correct, easy to reason about, but quadratic.

The wasteful part. Notice we pour everything back only to pour it out again on the very next dequeue. That round trip is pure waste. The optimal version simply leaves the reversed elements in the outbox and reuses them until they run out — turning repeated O(n) work into amortized O(1).

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

enqueue(1), enqueue(2), enqueue(3), dequeue()

Array state

start

inbox holds all, 3 on top

[0]

[1]

top ↓

[2]

Current pointerResolved stateNot processed

Final resultreturns 1, inbox restored to [2,3]

C · Code with teaching comments

Reference implementation previewclass MyQueue { private final Deque<Integer> inbox = new ArrayDeque<>(); public void enqueue(int x) { inbox.push(x);Explore the full code

solution.javaJava

Costly Dequeue — Reverse on Every Removal — reference

4 teaching notes

1
class MyQueue {
2
    private final Deque<Integer> inbox = new ArrayDeque<>();
3
 
4
    public void enqueue(int x) {
5
        // enqueue is a single push — newest element on top.
6
        inbox.push(x);
7
    }
8
 
9
    public int dequeue() {
10
        Deque<Integer> temp = new ArrayDeque<>();
11
        // Pour the whole inbox into temp, reversing it so the queue front rises to the
12
        // top.
13
        while (!inbox.isEmpty()) temp.push(inbox.pop());
14
        // The oldest element is now on top of temp — that's the queue front.
15
        int front = temp.pop();
16
        // Restore everything to the inbox — this pour-back is the O(n) waste the
17
        // optimal version removes.
18
        while (!temp.isEmpty()) inbox.push(temp.pop());
19
        return front;
20
    }
21
 
22
    public boolean empty() {
23
        return inbox.isEmpty();
24
    }
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityenqueue O(1), dequeue/peek O(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The reversal idea is already correct here; the inefficiency is restoring the inbox after every dequeue. Recognising that the reversed order can be kept and reused is the leap to the optimal solution.

Complexityenqueue O(1), dequeue/peek O(n) time, O(n) space — enqueue is a single push, O(1). dequeue moves all n elements to the second stack and back, so each removal is O(n); n removals cost O(n²) in total.

E · Edge cases and pitfalls3Pouring back after every dequeue — pure wasted work, O(n) per call.Explore edge cases

Pitfalls

Pouring back after every dequeue — pure wasted work, O(n) per call.
Forgetting to restore the inbox, which loses the FIFO ordering on the next enqueue.
Calling this O(1) — a single dequeue is genuinely O(n) here.

03.2

Approach 2 of 2 · Optimal

Two Stacks — Lazy Transfer (Optimal)

Timeamortized O(1) per opSpaceO(n)

The answer they want. Phrase it as 'refill the outbox only when it's empty' and give the amortized O(1) argument.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you didn't pour everything back after a dequeue? Could you leave the reversed elements somewhere and keep popping them?

2Hint 2Explore hint

Use two stacks: inbox for enqueue, outbox for dequeue/peek. Only when the outbox is empty do you pour the entire inbox into it.

3Hint 3Explore hint

Each element is pushed onto inbox once, then moved to outbox once, then popped once — at most a constant number of touches. That's why it's amortized O(1) despite the occasional O(n) refill.

A · Core idea

Maintain two stacks with distinct jobs. The inbox receives every enqueue (O(1) push). The outbox serves every dequeue and peek. The key rule: only when the outbox is empty do you pour the entire inbox into it. Pouring one stack into another reverses it, so the oldest element — the true queue front — ends up on top of the outbox.

The invariant that makes it correct. At all times the outbox holds a prefix of the queue front with the oldest element on top, and the inbox holds the more recent elements newest on top. Reading the queue front means: if the outbox has anything, its top is the front; otherwise refill from the inbox first. Because we only refill an empty outbox, we never interleave a fresh batch on top of an older one — that would scramble the order. This is the single most important rule.

Why the reversal gives FIFO. Suppose you enqueue 1, 2, 3. The inbox is [1, 2, 3] with 3 on top. Pour it into the outbox one pop at a time: pop 3, push 3; pop 2, push 2; pop 1, push 1. The outbox is now [3, 2, 1] with 1 on top. Popping the outbox yields 1, 2, 3 — exactly FIFO. One reversal flips LIFO into FIFO.

Why this is amortized O(1), not O(1). A dequeue that finds an empty outbox does O(n) work to refill. But every element participates in a refill at most once — once it's in the outbox it's never moved again, only popped. So over a run of operations the expensive refills are rare and each element's total cost is constant: one inbox push, one move, one outbox pop. Dividing total work by the number of operations gives O(1) amortized. Be precise in an interview: say 'amortized', and if asked for worst-case-per-op O(1), note that needs a more elaborate design.

Why peek shares the refill. peek also needs the front, so it runs the same 'refill if empty' step and then reads (not pops) the outbox top. Factor the refill into a private helper both methods call.

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue(), enqueue(4), dequeue()

Array state

before

all in inbox, 3 on top; outbox empty

[0]

[1]

inbox-top ↓

[2]

Current pointerResolved stateNot processed

Final resultreturns 1, 2, 3 in FIFO order

C · Code with teaching comments

solution.javaJava

Two Stacks — Lazy Transfer (Optimal) — optimal

6 teaching notes

1
class MyQueue {
2
    private final Deque<Integer> inbox = new ArrayDeque<>();
3
    private final Deque<Integer> outbox = new ArrayDeque<>();
4
 
5
    public void enqueue(int x) {
6
        // enqueue is always O(1) — every new element lands on the inbox.
7
        inbox.push(x);
8
    }
9
 
10
    public int dequeue() {
11
        // Both dequeue and peek call this so the front is guaranteed to sit on top of
12
        // the outbox.
13
        shiftIfNeeded();
14
        // After the shift, the outbox top is the oldest element — pop it to dequeue.
15
        return outbox.pop();
16
    }
17
 
18
    public int peek() {
19
        shiftIfNeeded();
20
        return outbox.peek();
21
    }
22
 
23
    public boolean empty() {
24
        // Queue is empty only when BOTH stacks are empty — elements may live in either.
25
        return inbox.isEmpty() && outbox.isEmpty();
26
    }
27
 
28
    private void shiftIfNeeded() {
29
        // The crucial guard: refill ONLY when the outbox is empty, so batches never
30
        // interleave.
31
        if (outbox.isEmpty()) {
32
            while (!inbox.isEmpty()) {
33
                // Pouring inbox→outbox reverses order, putting the oldest element on
34
                // top — LIFO becomes FIFO.
35
                outbox.push(inbox.pop());
36
            }
37
        }
38
    }
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityamortized O(1) per op timeO(n) spaceOpen the invariant and proofExplore the proof

The whole speedup comes from not undoing work. The costly version reverses and then un-reverses on every dequeue; the lazy version reverses once and reuses that order until exhausted. 'Do the expensive transformation once and reuse it' is the reusable amortization idea — the same reasoning behind dynamic-array doubling and splay-tree restructuring.

Complexityamortized O(1) per op time, O(n) space — Any element is pushed to inbox, moved to outbox, and popped exactly once over its lifetime — 3 constant-cost touches. Across m operations the total work is O(m), so each operation is amortized O(1). enqueue is always O(1); a dequeue that triggers a refill is O(n) but pays for the many cheap dequeues that follow.

E · Edge cases and pitfalls6enqueue(1), dequeue(), enqueue(2), peek() — First dequeue refills outbox with [1], pops 1. enqueue(2) goes to inbox. peek finds outbox empty, refills with [2], returns 2 without removing.Explore edge cases

Edge cases handled

enqueue(1), dequeue(), enqueue(2), peek()First dequeue refills outbox with [1], pops 1. enqueue(2) goes to inbox. peek finds outbox empty, refills with [2], returns 2 without removing.
interleaved enqueue/dequeueRefills happen whenever the outbox drains, but each element is still moved at most twice overall — amortization holds.
empty() with elements split across stacksReturns false unless BOTH inbox and outbox are empty; checking only one stack is a bug.

Pitfalls

Refilling the outbox when it is NOT empty — interleaves new and old batches and breaks FIFO order.
Checking only one stack in empty() — elements can sit in either.
Claiming worst-case O(1) per dequeue — it's amortized; a refill is O(n).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Editable code previewclass MyQueue { private final Deque<Integer> inbox = new ArrayDeque<>(); private final Deque<Integer> outbox = new ArrayDeque<>(); public void enqueue(int x) {Explore the playground

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Refilling a non-empty outbox

If you pour the inbox in while the outbox still has older elements, the newer batch lands on top and gets served before the older one — FIFO is violated.

Explore the code comparison

Don't write this

private void shift() {
    while (!inbox.isEmpty()) outbox.push(inbox.pop());
}  // runs unconditionally, even when outbox is non-empty

Write this instead

private void shiftIfNeeded() {
    if (outbox.isEmpty()) {
        while (!inbox.isEmpty()) outbox.push(inbox.pop());
    }
}

empty() checks only one stack

After a refill, elements live in the outbox while the inbox is empty (and vice versa). Testing a single stack reports the queue empty when it isn't.

Explore the code comparison

Don't write this

def empty(self) -> bool:
    return not self.inbox

Write this instead

def empty(self) -> bool:
    return not self.inbox and not self.outbox

Pouring back every dequeue

Restoring the inbox after each removal throws away the reversed order you just built, forcing an O(n) reversal on the very next dequeue.

Explore the code comparison

Don't write this

front = temp.pop()
while temp:
    self.inbox.append(temp.pop())  # wasteful restore
return front

Write this instead

self._shift_if_needed()
return self.outbox.pop()  # reuse the reversed outbox until empty

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two stacks reverse each other → FIFO from LIFO

Code pattern to memorize

enqueue(x): inbox.push(x)
dequeue()/peek():
    if outbox empty:
        while inbox not empty: outbox.push(inbox.pop())
    return outbox.pop()  # or peek()

Rules to remember

1Only refill the outbox when it is empty — refilling early scrambles the order.
2Pour the entire inbox into the outbox in one go, not one element at a time.
3Reversing a stack once (LIFO) and reading it gives FIFO — that single reversal is the whole trick.
4dequeue is O(n) on the transfer step but amortized O(1): each element is moved at most twice total (in, then out).
5Never push directly onto the outbox in enqueue — that breaks the ordering invariant.

Use this pattern when

You only have stacks (LIFO) but need queue (FIFO) semantics
Building one ADT out of another in a design / OOP question
Amortized analysis is acceptable (no hard per-op latency cap)
Implementing iterative tree traversal or undo/redo with ordering flips

Choose another pattern when

A native queue / deque is available → just use it, O(1) guaranteed
Hard real-time worst-case O(1) per op required → two stacks give amortized, not worst-case
You need random access or indexing → neither a stack nor a queue fits

Interview takeaway

Reversing a LIFO structure turns it into a FIFO one. Two stacks, with a lazy one-direction transfer, is the classic 'build one data structure from another' answer — and the amortized argument (each item moves a constant number of times) is the reusable idea.

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Transferable patternCanonical Two-Stack queue. The reusable ideas are 'reverse a LIFO to get FIFO' and 'do an expensive transform once, then reuse it' (amortization). Same amortized reasoning powers dynamic-array growth and Implement Stack using Queues.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Implement Queue using Stacks
Coming soon
The identical problem on LeetCode — same inbox/outbox lazy transfer.
Implement Stack using Queues
Coming soon
The mirror image: build LIFO from FIFO by rotating a single queue.
Design Circular Queue
Coming soon
Fixed-capacity queue on an array with wraparound — different trade-offs.
Number of Recent Calls
Coming soon
A queue used as a sliding time window — practice on FIFO eviction.

Same pattern

←

Balanced Brackets

Continue · Next problem

Equal Stacks

easyStack QueueFrequently asked

Queue Using Two Stacks

Stack & Queue · 9 of 17 · 9 min

Implement a first-in-first-out (FIFO) queue using only two stacks. The implemented queue must support all the standard operations:

enqueue(x) — add element x to the back of the queue.
dequeue() — remove and return the element at the front of the queue.
peek() — return the element at the front without removing it.
empty() — return whether the queue is empty.

You may only use the standard stack operations: push to top, pop from top, peek at top, size, and is-empty.

In plain English

Examples

Example 1

Input: enqueue(1), enqueue(2), peek(), dequeue(), empty()
Output: peek→1, dequeue→1, empty→false
Note: 1 was enqueued first, so it's the front. peek returns 1 without removing; dequeue removes and returns 1; 2 still remains so empty is false.

Example 2

Input: enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue()
Output: dequeue→1, dequeue→2
Note: First dequeue pours [1,2,3] from inbox into outbox as [3,2,1] (1 on top), returns 1. Second dequeue reuses outbox, returns 2 — no refill needed.

Example 3

Input: enqueue(5), dequeue(), enqueue(6), dequeue()
Output: dequeue→5, dequeue→6
Note: Refill happens twice because the outbox empties between dequeues — but each element still moves at most twice overall.

Constraints

1 ≤ x ≤ 10⁹ for enqueued values
At most 10⁵ calls total across enqueue, dequeue, peek, empty
dequeue and peek are only called on a non-empty queue
Only stack operations may be used internally — no native queue/deque

Clarifying questions4First question: Are dequeue and peek ever called on an empty queue?Explore questions

Q1.Are dequeue and peek ever called on an empty queue?
Per the constraints, no. If they could be, decide whether to return a sentinel or throw — say it out loud.
Q2.Is amortized O(1) acceptable, or do you need worst-case O(1) per operation?
Two stacks give amortized O(1). True worst-case O(1) needs a more complex design (e.g. three stacks with incremental copying).
Q3.Can I use the language's built-in stack type?
Yes — ArrayDeque in Java or a list in Python, used strictly as a stack. You just can't use a native queue.
Q4.Should peek and dequeue share the refill logic?
Yes — both need the front element, so both trigger a refill when the outbox is empty. Factor it into one helper.

Quick interview revision

Understand

30-second explanation

Build the interview-ready mental model before comparing implementations.

Interview contextWhat is testedWhere candidates slipHow to stand outExplore interview context

What's being tested

Whether you see that reversing a stack yields a queue, and whether you can justify amortized O(1) instead of claiming a single dequeue is O(1).

Where candidates slip

Transferring elements back and forth on every operation (O(n) each), or refilling the outbox while it still has elements, which corrupts the order.

How to stand out

State the invariant ('outbox holds the front of the queue, oldest on top'), refill only when outbox is empty, and give the amortized argument: each element is pushed and popped at most twice.

Choose

Compare the available approaches

Use constraints and trade-offs to select the route you can defend in an interview.

Approaches at a glanceCompare before you dive in

#	Approach	Time	Space	When to mention	Jump
1	Costly Dequeue — Reverse on Every Removal	`enqueue O(1), dequeue/peek O(n)`	`O(n)`	Mention it as the obvious first design, then point out the per-dequeue O(n) cost and improve it with lazy transfer.	Read
2	Two Stacks — Lazy Transfer (Optimal)Optimal	`amortized O(1) per op`	`O(n)`	The answer they want. Phrase it as 'refill the outbox only when it's empty' and give the amortized O(1) argument.	Read

Learn & trace

Build each solution step by step

Move from the core idea to a visual trace, implementation, proof, and edge cases.

03.1

Approach 1 of 2

Costly Dequeue — Reverse on Every Removal

Timeenqueue O(1), dequeue/peek O(n)SpaceO(n)

Mention it as the obvious first design, then point out the per-dequeue O(n) cost and improve it with lazy transfer.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

enqueue is easy — push onto a stack. The hard part is that the element you want to remove is at the BOTTOM of that stack. How do you reach the bottom of a stack?

2Hint 2Explore hint

To remove the front, pour everything into a second stack so the bottom element rises to the top, pop it, then pour everything back.

3Hint 3Explore hint

This works but every dequeue moves all n elements twice. Can you avoid pouring back?

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

enqueue(1), enqueue(2), enqueue(3), dequeue()

Array state

start

inbox holds all, 3 on top

[0]

[1]

top ↓

[2]

Current pointerResolved stateNot processed

Final resultreturns 1, inbox restored to [2,3]

C · Code with teaching comments

Reference implementation previewclass MyQueue { private final Deque<Integer> inbox = new ArrayDeque<>(); public void enqueue(int x) { inbox.push(x);Explore the full code

solution.javaJava

Costly Dequeue — Reverse on Every Removal — reference

4 teaching notes

1
class MyQueue {
2
    private final Deque<Integer> inbox = new ArrayDeque<>();
3
 
4
    public void enqueue(int x) {
5
        // enqueue is a single push — newest element on top.
6
        inbox.push(x);
7
    }
8
 
9
    public int dequeue() {
10
        Deque<Integer> temp = new ArrayDeque<>();
11
        // Pour the whole inbox into temp, reversing it so the queue front rises to the
12
        // top.
13
        while (!inbox.isEmpty()) temp.push(inbox.pop());
14
        // The oldest element is now on top of temp — that's the queue front.
15
        int front = temp.pop();
16
        // Restore everything to the inbox — this pour-back is the O(n) waste the
17
        // optimal version removes.
18
        while (!temp.isEmpty()) inbox.push(temp.pop());
19
        return front;
20
    }
21
 
22
    public boolean empty() {
23
        return inbox.isEmpty();
24
    }
25
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.25 lines

D · Why it works and complexityenqueue O(1), dequeue/peek O(n) timeO(n) spaceOpen the invariant and proofExplore the proof

The reversal idea is already correct here; the inefficiency is restoring the inbox after every dequeue. Recognising that the reversed order can be kept and reused is the leap to the optimal solution.

E · Edge cases and pitfalls3Pouring back after every dequeue — pure wasted work, O(n) per call.Explore edge cases

Pitfalls

Pouring back after every dequeue — pure wasted work, O(n) per call.
Forgetting to restore the inbox, which loses the FIFO ordering on the next enqueue.
Calling this O(1) — a single dequeue is genuinely O(n) here.

03.2

Approach 2 of 2 · Optimal

Two Stacks — Lazy Transfer (Optimal)

Timeamortized O(1) per opSpaceO(n)

The answer they want. Phrase it as 'refill the outbox only when it's empty' and give the amortized O(1) argument.

Stuck? Progressive hintsReveal one at a time

1Hint 1Explore hint

What if you didn't pour everything back after a dequeue? Could you leave the reversed elements somewhere and keep popping them?

2Hint 2Explore hint

Use two stacks: inbox for enqueue, outbox for dequeue/peek. Only when the outbox is empty do you pour the entire inbox into it.

3Hint 3Explore hint

Each element is pushed onto inbox once, then moved to outbox once, then popped once — at most a constant number of touches. That's why it's amortized O(1) despite the occasional O(n) refill.

A · Core idea

B · Visual dry run

Interactive dry run

Select a frame to connect the decision with its visual state.

enqueue(1), enqueue(2), enqueue(3), dequeue(), dequeue(), enqueue(4), dequeue()

Array state

before

all in inbox, 3 on top; outbox empty

[0]

[1]

inbox-top ↓

[2]

Current pointerResolved stateNot processed

Final resultreturns 1, 2, 3 in FIFO order

C · Code with teaching comments

solution.javaJava

Two Stacks — Lazy Transfer (Optimal) — optimal

6 teaching notes

1
class MyQueue {
2
    private final Deque<Integer> inbox = new ArrayDeque<>();
3
    private final Deque<Integer> outbox = new ArrayDeque<>();
4
 
5
    public void enqueue(int x) {
6
        // enqueue is always O(1) — every new element lands on the inbox.
7
        inbox.push(x);
8
    }
9
 
10
    public int dequeue() {
11
        // Both dequeue and peek call this so the front is guaranteed to sit on top of
12
        // the outbox.
13
        shiftIfNeeded();
14
        // After the shift, the outbox top is the oldest element — pop it to dequeue.
15
        return outbox.pop();
16
    }
17
 
18
    public int peek() {
19
        shiftIfNeeded();
20
        return outbox.peek();
21
    }
22
 
23
    public boolean empty() {
24
        // Queue is empty only when BOTH stacks are empty — elements may live in either.
25
        return inbox.isEmpty() && outbox.isEmpty();
26
    }
27
 
28
    private void shiftIfNeeded() {
29
        // The crucial guard: refill ONLY when the outbox is empty, so batches never
30
        // interleave.
31
        if (outbox.isEmpty()) {
32
            while (!inbox.isEmpty()) {
33
                // Pouring inbox→outbox reverses order, putting the oldest element on
34
                // top — LIFO becomes FIFO.
35
                outbox.push(inbox.pop());
36
            }
37
        }
38
    }
39
}

Yellow row = the algorithm's core logic. Amber `//` lines above it = what you'd say out loud.39 lines

D · Why it works and complexityamortized O(1) per op timeO(n) spaceOpen the invariant and proofExplore the proof

Edge cases handled

enqueue(1), dequeue(), enqueue(2), peek()First dequeue refills outbox with [1], pops 1. enqueue(2) goes to inbox. peek finds outbox empty, refills with [2], returns 2 without removing.
interleaved enqueue/dequeueRefills happen whenever the outbox drains, but each element is still moved at most twice overall — amortization holds.
empty() with elements split across stacksReturns false unless BOTH inbox and outbox are empty; checking only one stack is a bug.

Pitfalls

Refilling the outbox when it is NOT empty — interleaves new and old batches and breaks FIFO order.
Checking only one stack in empty() — elements can sit in either.
Claiming worst-case O(1) per dequeue — it's amortized; a refill is O(n).

Practice

Try the solution yourself

Edit the optimal implementation, test another input, and observe the result.

Try it — Java· run a complete program; method snippets need a driver

Avoid mistakes

Recognize the interview traps

Understand why common attempts fail before reviewing the corrected implementation.

Refilling a non-empty outbox

If you pour the inbox in while the outbox still has older elements, the newer batch lands on top and gets served before the older one — FIFO is violated.

Explore the code comparison

Don't write this

private void shift() {
    while (!inbox.isEmpty()) outbox.push(inbox.pop());
}  // runs unconditionally, even when outbox is non-empty

Write this instead

private void shiftIfNeeded() {
    if (outbox.isEmpty()) {
        while (!inbox.isEmpty()) outbox.push(inbox.pop());
    }
}

empty() checks only one stack

After a refill, elements live in the outbox while the inbox is empty (and vice versa). Testing a single stack reports the queue empty when it isn't.

Explore the code comparison

Don't write this

def empty(self) -> bool:
    return not self.inbox

Write this instead

def empty(self) -> bool:
    return not self.inbox and not self.outbox

Pouring back every dequeue

Restoring the inbox after each removal throws away the reversed order you just built, forcing an O(n) reversal on the very next dequeue.

Explore the code comparison

Don't write this

front = temp.pop()
while temp:
    self.inbox.append(temp.pop())  # wasteful restore
return front

Write this instead

self._shift_if_needed()
return self.outbox.pop()  # reuse the reversed outbox until empty

Revise

Carry the pattern into the interview

Quick interview revision

Pattern to remember

Two stacks reverse each other → FIFO from LIFO

Code pattern to memorize

enqueue(x): inbox.push(x)
dequeue()/peek():
    if outbox empty:
        while inbox not empty: outbox.push(inbox.pop())
    return outbox.pop()  # or peek()

Rules to remember

1Only refill the outbox when it is empty — refilling early scrambles the order.
2Pour the entire inbox into the outbox in one go, not one element at a time.
3Reversing a stack once (LIFO) and reading it gives FIFO — that single reversal is the whole trick.
4dequeue is O(n) on the transfer step but amortized O(1): each element is moved at most twice total (in, then out).
5Never push directly onto the outbox in enqueue — that breaks the ordering invariant.

Use this pattern when

You only have stacks (LIFO) but need queue (FIFO) semantics
Building one ADT out of another in a design / OOP question
Amortized analysis is acceptable (no hard per-op latency cap)
Implementing iterative tree traversal or undo/redo with ordering flips

Choose another pattern when

A native queue / deque is available → just use it, O(1) guaranteed
Hard real-time worst-case O(1) per op required → two stacks give amortized, not worst-case
You need random access or indexing → neither a stack nor a queue fits

Interview takeaway

Continue

Transfer the pattern to another problem

Use a direct variation or pattern sibling to prove the idea is reusable.

Practice queueDirect variations and pattern siblings

Direct follow-ups

Implement Queue using Stacks
Coming soon
The identical problem on LeetCode — same inbox/outbox lazy transfer.
Implement Stack using Queues
Coming soon
The mirror image: build LIFO from FIFO by rotating a single queue.
Design Circular Queue
Coming soon
Fixed-capacity queue on an array with wraparound — different trade-offs.
Number of Recent Calls
Coming soon
A queue used as a sliding time window — practice on FIFO eviction.

Same pattern

←

Balanced Brackets

Continue · Next problem

Equal Stacks