Queue Using Stacks

Implement Queue using Stacks is a classic "build one data structure out of another" interview problem. A stack only lets you reach the most recently added item (LIFO), yet a queue must serve the oldest item first (FIFO). The elegant fix uses two stacks and one well-timed reversal.

The slow way first

The naive idea: keep a single stack and, on every pop(), reverse it into a helper stack, take the bottom element, and reverse everything back. That works, but you pay an O(n) reversal on every single dequeue — and you throw that work away each time, only to redo it on the next call.

The question to ask: can I avoid re-reversing the same elements over and over? If an element has already been flipped into the right order, I should leave it there until it is served.

The idea: an in stack and an out stack

Keep two stacks. The in stack catches every push — enqueue is just one push, O(1). The out stack serves every pop and peek. The key move: when you need to dequeue and the out stack is empty, pour the entire in stack into the out stack, popping in's top and pushing it onto out, one at a time. That single transfer reverses the order, so the oldest element ends up on top of out — exactly where a queue wants it.

The crucial insight: you only pour when out is empty. As long as out still has elements, dequeues just pop it directly. Each element is moved from in to out at most once, which is what makes the whole thing fast.

Walk through it

Step through the animation. We enqueue 1, 2, 3 — they pile onto the in stack with 3 on top. The first dequeue() finds out empty, so it pours: 3 goes over first (landing at the bottom of out), then 2, then 1 — leaving 1 on top of out. Popping out returns 1, the first value enqueued. FIFO order preserved.

Pseudocode

in_stack  = empty stack      # catches every enqueue
out_stack = empty stack      # serves every dequeue
 
push(x):
    in_stack.push(x)
 
peek():
    if out_stack is empty:
        while in_stack not empty:        # pour: this reversal happens once
            out_stack.push(in_stack.pop())
    return out_stack.top()
 
pop():
    peek()                   # make sure out_stack is ready
    return out_stack.pop()

The Python solution

class MyQueue:
    def __init__(self):
        self.in_stack = []
        self.out_stack = []
 
    def push(self, x):
        self.in_stack.append(x)
 
    def pop(self):
        self.peek()
        return self.out_stack.pop()
 
    def peek(self):
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        return self.out_stack[-1]

• in_stack and out_stack are plain Python lists used as stacks (append pushes, pop() removes the top).
• push is a single append onto the in stack — always O(1).
• peek is where the work lives: if the out stack is empty, the while loop pours every element of in into out, reversing the order so the oldest item rises to the top.
• Lines 14-16 are the one-time reversal — they run only when out is empty, so the cost is shared across many cheap dequeues.
• pop calls peek first (to guarantee out is ready), then removes and returns the out top.

Complexity

A single dequeue can cost O(n) when it triggers a pour, but every element is poured at most once before it leaves. Spread across all operations, that averages out to amortized O(1) per call — the hallmark of this two-stack design.

When this pattern shows up

Practice