Implement Queue using Stacks

The Problem

Design a first-in, first-out queue using only standard stack operations.

You need to support:

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

The Two-Shelf Analogy

Imagine a ticket line managed with two vertical shelves of trays.

The arrival shelf (inStack) is where every new ticket gets dropped. New arrivals always land on top, so this shelf is naturally last-in, first-out.

The service shelf (outStack) is where the clerk serves customers from. When the clerk needs the next ticket and the service shelf is empty, they lift every tray from the arrival shelf and place it onto the service shelf one by one. That full pour reverses the order. The oldest ticket, which was buried at the bottom of the arrival shelf, becomes the top tray on the service shelf.

That is the whole trick:

• push only touches the arrival shelf
• pop and peek only use the service shelf
• only when the service shelf is empty do you pour from arrival to service

The queue order is never stored separately. It is implied by both shelves together: front tickets live on top of outStack, and brand-new arrivals wait inside inStack until a future pour.

Why This Works

A stack reverses order. Two reversals restore the original oldest-first order at the moment you need to serve.

If you poured on every push, you would do unnecessary work. The lazy rule is better:

• keep stacking new arrivals into inStack
• only pour when outStack is empty and someone asks for the front

That makes each element move at most twice:

1. pushed once into inStack
2. maybe transferred once into outStack

So even though one pop can trigger a big pour, the amortized cost is still O(1) per operation.

---

How I Think Through This

I treat inStack as "new arrivals I have not reversed yet" and outStack as "front of the queue, ready to serve." The invariant is simple: if outStack has anything, its top is the true queue front.

Take the sequence push(1), push(2), push(3), peek(), pop(), push(4).

That last step is the key teaching moment. 4 is newer than 2 and 3, so it must not jump ahead just because it was the latest push. Leaving it in inStack preserves FIFO order.

---

Building the Algorithm

Step 1: Separate Arrival from Service

Start with two stacks:

• inStack for every push
• outStack for the front-facing operations later

At this stage, push is just inStack.push(x), and empty() is true only when both stacks are empty.

Hints & gotchas

• Do not push into both stacks. inStack is the landing zone for every new element.
• empty() must inspect both stacks. Items might already have been transferred into outStack.
• The queue is represented by the pair, not one stack alone.

Step 2: Pour Only When Needed

Now add one helper: if outStack is empty, move everything from inStack to outStack.

That helper should run before pop() and peek(). After the pour, the oldest queued item sits on top of outStack, exactly where a stack can serve it.

Hints & gotchas

• Only transfer when outStack is empty. If you pour while it already has items, you will break FIFO order.
• Transfer all items, not just one. The full reversal is what restores oldest-first service.
• peek() and pop() share the same prep step. Both need the front exposed on top of outStack.

---

The Invariant

The invariant is: if outStack is non-empty, its top is the real queue front.

---

Common Misconceptions

"I should transfer on every push so the queue is always ready." That works logically, but it destroys the intended efficiency. New items can wait in inStack until the service side runs dry.

"When outStack is empty, I only need to move one item." Moving just one item exposes the oldest item once, but leaves the next-oldest item trapped under newer arrivals in inStack. You must move the entire stack.

"If outStack already has items, new pushes should go there too." No. That would place brand-new arrivals ahead of older items already waiting to be served. New pushes always go to inStack.

"empty() only checks inStack because pushes go there." Wrong. After a transfer, all remaining queue items may live entirely inside outStack.

---

Complete Solution