Algorithm

Implement Queue using Stacks

Design Pattern

Queue using Stacks

Implement a first in first out (FIFO) queue using only two stacks. The implemented queue should support all the functions of a normal queue: push, peek, pop, and empty. void push(int x) pushes element x to the back. int pop() removes and returns the front element. int peek() returns the front element. boolean empty() returns true if empty. Each operation must only use standard stack operations.

CONSTRAINTS
  • 1 <= x <= 9
  • At most 100 calls to push, pop, peek, and empty
  • All calls to pop and peek are valid (queue will not be empty)
EXAMPLE 1
Input: push(1), push(2), peek(), pop(), empty()
Output: 1, 1, false
1 and 2 arrive. peek returns the oldest, 1; pop also returns 1. 2 is still waiting, so empty is false. FIFO order is preserved.
EXAMPLE 2
Input: push(1), pop(), push(2), peek()
Output: 1, 2
1 arrives and is immediately popped → 1. Then 2 arrives and is the only element, so peek returns 2.
Why keep two stacks instead of reversing one in place each time?
Two stacks let the reversal be lazy and shared: items reversed once into the outStack stay reversed until served. Reversing a single stack on every operation would redo the same work repeatedly, making each call O(N).
When exactly is a transfer allowed?
Only when the outStack is empty. If it still holds items, its top is already the correct front — transferring would re-scramble order and waste work.
The problem says pop/peek are always valid — do I still handle empty?
Not strictly required by the constraints, but a robust empty() (true only when both stacks are empty) is cheap and worth having.

A stack is like a tube where you only ever touch the top (LIFO). A queue is like a tunnel where people enter one end and exit the other (FIFO). One stack is backwards for a queue, but two stacks together can fix this!

Think of it as a Waterfall. You pour items from one container into another, and the order flips perfectly. By doing this pour only when our exit container is empty, we convert LIFO into FIFO with very little extra work.

The Waterfall

We maintain two stacks: an inStack for arrivals and an outStack for departures.
- Push: Always add the new person to the back of the arrival line (inStack).
- Pop/Peek: We need the person at the very front. If our departure stack (outStack) is empty, we pour everything from the arrival stack into it. Because of the LIFO property, the person who was at the very bottom of the arrival stack (the first one to arrive) is now at the very top of the departure stack!
- Amortized Efficiency: Even though a single transfer might take time, every item only moves from one stack to the other exactly once. This means the overall cost is constant over time.

Code Blueprint
text
CLASS MyQueue:
    inStack = []
    outStack = []

    FUNCTION push(x):
        inStack.PUSH(x)

    FUNCTION pop():
        transfer_if_needed()
        RETURN outStack.POP()

    FUNCTION peek():
        transfer_if_needed()
        RETURN outStack.PEEK()

    FUNCTION transfer_if_needed():
        IF outStack is empty:
            WHILE inStack is NOT empty:
                outStack.PUSH(inStack.POP())
Worked Example:interleave arrivals and departures
0
1
1
2
inStack Top
push(1), push(2): Items pushed onto inStack in LIFO order. outStack is empty.
0
2
1
1
outStack Top
pop(): outStack is empty, so transfer all elements from inStack to outStack to reverse order. inStack = []. outStack = [2, 1].
0
2
outStack Top
Pop from outStack: Pops and returns 1. outStack = [2]. FIFO order preserved!
Interactive Strategy Visualization
QUEUE EMULATION INSIGHT

Bridging LIFO and FIFO with Dual Stacks

S1: Inbox
S2: Outbox

The Reversal Insight

A single stack reverses order (LIFO). By transferring to a second stack, we reverse the reversal, effectively yielding the original order (FIFO).

AMORTIZED O(1)Each element is pushed/popped between stacks exactly twice. Average cost per operation remains constant.
Operation1 / 6
[push(1)]Push 1 to s1.

Strategy: Lazy Transfer

Don't move elements unnecessarily. Only transfer from Inbox (S1) to Outbox (S2) when S2 is empty and a Pop/Peek is requested.

O(N) Reverse Every Pop
→
O(1) Amortized Lazy Two-Stack Transfer