#232 Implement Queue using Stacks

frequently reported atApple Microsoft Bloomberg Amazon Meta

the problem

In plain words

Build a FIFO queue (push, pop, peek, empty) using only standard stack operations: push to top, peek/pop from top, size and isEmpty.

in push(1), push(2), peek(), pop(), empty()

out 1, 1, false

1 went in first, so it comes out first.

1 ≤ x ≤ 9
At most 100 calls
pop and peek are always valid
Follow-up: amortized O(1) per operation

your turn

Try it before you peek

Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.

Solve it in the browser

Design: implement every operation. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.

Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.

Marking the problem solved, or opening every hint, also shows it.

the aha

Key insight

patternStack & queue design

Pouring one stack into another reverses it — and reversing LIFO gives FIFO. Only pour when the output stack is empty, so each element is poured once.

solutions

From brute force to optimal

Keep the oldest element on top of one stack at all times by moving everything out and back on each push.

Move all of main into temp.
Push x onto the empty main (it sits at the bottom = rear).
Move everything back on top of it.
pop/peek simply read main's top.

timepush O(n), pop/peek O(1)

Each push moves all n elements twice.

spaceO(n)

The two stacks hold the n elements.

javajava.util.*

1// On LeetCode, name this class MyQueue.2class MyQueueCostlyPush {3    private final Deque<Integer> main = new ArrayDeque<>(); // top = front of the queue4    private final Deque<Integer> temp = new ArrayDeque<>();5 6    public void push(int x) {7        while (!main.isEmpty()) temp.push(main.pop()); // empty main8        main.push(x); // x sits at the bottom = rear9        while (!temp.isEmpty()) main.push(temp.pop()); // older ones go back on top10    }11 12    public int pop() {13        return main.pop();14    }15 16    public int peek() {17        return main.peek();18    }19 20    public boolean empty() {21        return main.isEmpty();22    }23}

Push into in. Serve from out. Refill out from in only when out is empty.

push: in.push(x).
peek/pop: if out is empty, pour all of in into out.
Return / pop out's top.
empty: both stacks empty.

timeO(1) amortized per operation

Every element is pushed to in once, moved to out once and popped once — a constant amount of work per element.

spaceO(n)

Each element lives in exactly one of the two stacks.

javajava.util.*

1class MyQueue {2    private final Deque<Integer> in = new ArrayDeque<>(); // receives every push3    private final Deque<Integer> out = new ArrayDeque<>(); // serves pops, oldest on top4 5    public void push(int x) {6        in.push(x);7    }8 9    public int pop() {10        peek(); // makes sure the front is on top of out11        return out.pop();12    }13 14    public int peek() {15        if (out.isEmpty()) { // only refill when out has nothing left16            while (!in.isEmpty()) out.push(in.pop()); // reversing puts the oldest on top17        }18        return out.peek();19    }20 21    public boolean empty() {22        return in.isEmpty() && out.isEmpty();23    }24}

sim

Dry run

loading simulation…

javajava.util.*

1class MyQueue {2    private final Deque<Integer> in = new ArrayDeque<>(); // receives every push3    private final Deque<Integer> out = new ArrayDeque<>(); // serves pops, oldest on top4 5    public void push(int x) {6        in.push(x);7    }8 9    public int pop() {10        peek(); // makes sure the front is on top of out11        return out.pop();12    }13 14    public int peek() {15        if (out.isEmpty()) { // only refill when out has nothing left16            while (!in.isEmpty()) out.push(in.pop()); // reversing puts the oldest on top17        }18        return out.peek();19    }20 21    public boolean empty() {22        return in.isEmpty() && out.isEmpty();23    }24}

in the room

How to say it in the interview

talk track

Say: "Reversing a stack once turns LIFO into FIFO."
Explain why you must NOT pour while out still has elements — that would put newer elements above older ones.
State the complexity carefully: worst case O(n) for one pop, amortized O(1) per operation.

traps

Pouring in into a non-empty out — breaks the order.
Forgetting that empty() must check both stacks.

what they ask next

Follow-ups

Can you make every single operation O(1) worst case?

Not with this simple scheme; amortized is what the problem asks for. Real-time queues from stacks exist (incremental transfer) but are rarely expected.

Why does this matter in practice?

It's how purely functional languages build immutable queues (two lists), and the idea behind amortized analysis in general.

before you submit

Edge cases to test

Push after a transfer: the new element must wait behind everything already in out — never pour into a non-empty out.
peek twice in a row returns the same element and removes nothing.
The queue empties completely and is refilled — empty() must look at both stacks.

practise next