Implement Queue using Stacks

Implement a first-in-first-out queue using only stacks (LIFO structures). Support:

push(x) — push x to the back of the queue.
pop() — remove and return the front element.
peek() — return the front element without removing it.
empty() — return whether the queue is empty.

pop and peek are only called on a non-empty queue. Use only standard stack operations (push, pop/top, size/empty).

Hints

· Stuck? Reveal one nudge at a time.

A stack is LIFO but a queue needs FIFO — how does pouring one stack into another help?

Pouring input into output reverses the order, putting the oldest element on top.

Only transfer when the output stack is empty; that keeps it amortized O(1).

Common doubts

If output still holds elements, they're already in front-first order. Pouring again would re-reverse them and break FIFO.

Each element is moved from input to output at most once in its lifetime, so the total transfer work across all operations is O(n) — amortized O(1) each.

One stack can only reverse once; you'd have to reverse back and forth on every operation. The second stack caches the reversed order so you reverse each element only once.

Interview follow-ups

· What an interviewer asks next.

Yes — a push-costly variant keeps the queue reversed on every push, making pop/peek O(1) but push O(n). The two-stack lazy version is usually preferred.

Purely functional (immutable) queues use exactly this front-list / back-list pair, reversing the back list onto the front when it empties.

Fun facts

The two-stack queue is the classic example of amortized analysis in algorithms courses.
Immutable/persistent queues in functional languages are built from this very front/back pair of stacks.

Asked at

AmazonMicrosoftGoogle

Frequently Sometimes Occasionally

Example 1

Input: push(1), push(2), peek(), pop(), empty()
Output: 1, 1, false
peek and pop both return 1 (the oldest); after popping, 2 remains, so empty is false.

Example 2

Input: push(5), pop(), empty()
Output: 5, true
Push then pop returns 5, leaving the queue empty.

Constraints

- 1 <= x <= 10^5 - At most 100 operations. - pop and peek are only called on a non-empty queue.

Two stacks make a queue. Pushes pile onto an input stack. When you need the front, you pour the input stack into an output stack — which reverses it, so the output stack's top is the queue's front. Refilling only when the output stack is empty makes every operation amortized O(1).

Prerequisites

Before you start

· Concepts used directly in the solution.

Stack operations. Push, pop (top), and size are the only primitives allowed.

Amortized analysis. Each element is moved between stacks at most once, so the average cost per op is O(1).

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

The contract

“Are pop and peek called on an empty queue?”

No — only when the queue is non-empty.

“Can I use anything besides stacks?”

No — the whole point is to build FIFO from two LIFO stacks.

The ideal opening — say it like this

I keep two stacks: an input stack for pushes and an output stack for the front.

When the output stack is empty and I need the front, I pour the whole input stack into it, which reverses the order.

Refilling only when output is empty makes each operation amortized O(1).

Understand the problem

Worked example — push 1, push 2, peek, pop

push 1 -> input [1]                       (null)
push 2 -> input [1,2]                      (null)
peek   -> output empty: pour -> output [2,1]; top is 1   returns 1
pop    -> output [2,1] -> pop 1 -> [2]     returns 1

Key observations

1Aha

Pouring one stack into another reverses it

Popping input and pushing to output flips LIFO order, so the queue's front (oldest) rises to the top of output.

2Aha

Refill only when output is empty

If output still has elements, they're already in front-first order — don't disturb them. Refill from input only after output drains.

3Aha

Amortized O(1)

Every element is transferred at most once from input to output over its lifetime, so despite an occasional O(n) pour, the average per-operation cost is O(1).

Summary

Key takeaway

Two stacks: push onto input; for the front, pour input into output (reversing it) but only when output is empty. Then pop/peek are output-stack operations. Amortized O(1) per operation, since each element moves at most once.

push(x): input.push(x)
move():  if output empty: while input: output.push(input.pop())
pop():   move(); return output.pop()
peek():  move(); return output.top()
empty(): input empty and output empty