Implement Queue using Stacks (LC 232)

Pattern: Stack ↔ Queue design (amortised analysis)
Difficulty: Easy (the analysis is the interview)
Key Concept: Reversing a stack into a second stack turns LIFO into FIFO. Only refill when the output stack is empty — that is what makes it amortised O(1) instead of O(n).

Problem Statement

Implement a FIFO queue using only two stacks. Support push(x), pop(), peek(), empty(), using only standard stack operations (push, peek/top, pop, size, isEmpty).

Follow-up: can each operation be amortised O(1)?

Example

push(1); push(2);
peek()  → 1
pop()   → 1
empty() → false

1. Algorithm & Pseudocode

Naive (costly push)

push(x):
    move everything from `in` to `temp`
    push x onto `in`
    move everything back from `temp` to `in`   // x is now at the bottom-of-LIFO = front
pop():  return in.pop()

Push is O(n), pop is O(1).

Optimal (lazy transfer — amortised O(1))

two stacks: `in` (for pushes), `out` (for pops)

push(x):
    in.push(x)

shift():                              // private helper
    if out is EMPTY:                  // ← the whole trick is this guard
        while in is not empty: out.push(in.pop())

pop():   shift(); return out.pop()
peek():  shift(); return out.peek()
empty(): return in.isEmpty() AND out.isEmpty()

2. Step-by-Step Analysis (Beginner-Friendly)

Why two stacks give you FIFO A stack reverses order. Pouring stack A into stack B reverses it once — so the element that entered A first ends up on top of B. Popping B therefore yields FIFO order. One reversal is all you need.
Why you must NOT refill when out is non-empty If you transferred on every pop, you’d interleave old and new elements and break the ordering — and you’d pay O(n) every time. The guard if (out.isEmpty()) is both the correctness condition and the performance condition.
The amortised argument (say this out loud) Each element is pushed to in once, popped from in once, pushed to out once, popped from out once — at most 4 stack operations over its entire lifetime, no matter how the calls are interleaved. So n queue operations cost O(n) total stack operations → O(1) amortised each. Worst case for a single call is still O(n) — that one pop that triggers the transfer. Interviewers explicitly want you to distinguish amortised from worst-case.
Why empty() checks both stacks Elements live in in until a pop/peek forces the shift. Checking only out would wrongly report empty right after a fresh batch of pushes.
peek() needs the shift too peek must return the front of the queue, which only exists on top of out. Reuse the same helper — don’t duplicate the transfer logic.

3. The Dry Run

Call	`in` (top→bottom)	`out` (top→bottom)	Returns	Note
`push(1)`	`1`	—	—	lands in `in`
`push(2)`	`2 1`	—	—
`peek()`	—	`1 2`	1	`out` empty → transfer all; 1 rises to top
`pop()`	—	`2`	1	`out` non-empty → no transfer
`push(3)`	`3`	`2`	—	new element waits in `in`
`pop()`	`3`	—	2	`out` non-empty → still no transfer ✓
`pop()`	—	—	3	`out` empty → transfer 3, then pop
`empty()`	—	—	true	both stacks empty

Notice element 3 was pushed after 1 and 2 were already sitting in out, and FIFO order still held. That’s the guard doing its job.

4. Java Solution

Naive (O(n) push)

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> temp = new ArrayDeque<>();

    public void push(int x) {
        while (!in.isEmpty()) temp.push(in.pop());
        in.push(x);
        while (!temp.isEmpty()) in.push(temp.pop());   // x ends up at the bottom
    }
    public int pop()  { return in.pop(); }
    public int peek() { return in.peek(); }
    public boolean empty() { return in.isEmpty(); }
}

push O(n) · pop/peek/empty O(1)

Optimal (amortised O(1))

class MyQueue {
    private final Deque<Integer> in  = new ArrayDeque<>();   // all pushes land here
    private final Deque<Integer> out = new ArrayDeque<>();   // all pops come from here

    public void push(int x) {
        in.push(x);                       // always O(1)
    }

    public int pop() {
        shift();
        return out.pop();
    }

    public int peek() {
        shift();
        return out.peek();
    }

    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }

    /** Refill `out` ONLY when it is empty — this preserves FIFO and gives amortised O(1). */
    private void shift() {
        if (out.isEmpty()) {
            while (!in.isEmpty()) out.push(in.pop());
        }
    }
}

push/pop/peek/empty — amortised O(1), worst case O(n) for the transferring call · Space O(n)

5. The “Java vs. Others” Edge

ArrayDeque for both stacks — array-backed and unsynchronized. java.util.Stack extends Vector so every operation takes a lock, and it iterates bottom-to-top. Never use it.
final fields — the two stacks are never reassigned. Marking them final is free documentation and lets the JIT treat them as constants. Small thing; interviewers notice.
ArrayDeque forbids null. That’s a feature here: out.peek() returning null could only mean “empty”, never “a null element was stored”. LinkedList would blur that.
The private shift() helper — pop and peek share the exact same precondition. Two copies of the transfer loop is where bugs breed. Extracting it is the design signal the question is really testing.
Boxing: Deque<Integer> boxes. Values −128..127 hit the Integer cache; larger values allocate. Fine for an interview; mention int[]-backed stacks if pushed on allocation.

6. Complexity Summary

Approach	push	pop	peek	empty	Space
Naive (transfer on push)	O(n)	O(1)	O(1)	O(1)	O(n)
Two stacks, lazy transfer	O(1)	O(1) amort	O(1) amort	O(1)	O(n)
— worst case, single call	O(1)	O(n)	O(n)	O(1)	—

7. Edge Cases & Follow-Ups

pop() / peek() on an empty queue — the problem guarantees valid calls, but say you’d throw NoSuchElementException (matching Deque.pop()’s own contract) in production code.
Sibling problem, opposite direction: LC 225 Stack using Queues — there the trick is to rotate the queue on push (for (i = 1; i < q.size(); i++) q.offer(q.poll())), making push O(n) and pop O(1). There is no amortised O(1) solution with one queue.
Thread safety: this is not thread-safe. In production you’d reach for ConcurrentLinkedQueue or ArrayBlockingQueue rather than hand-rolling. Worth one sentence.
Why would anyone do this? It’s a genuine technique when your only primitive is LIFO — e.g. reversing a stream with bounded memory, or implementing a queue on a stack machine.

#	Problem	Difficulty	Connection
LC 225	Implement Stack using Queues	Easy	mirror image; rotate on push
LC 622	Design Circular Queue	Medium	ring buffer instead of two stacks
LC 155	Min Stack	Medium	augment a stack with O(1) `getMin`
LC 1381	Design a Stack With Increment Operation	Medium	lazy propagation, same “defer the work” idea