Implement a Queue Using Two Stacks: Amortized O(1) Explained

Implementing a queue with two stacks is a short coding question with a long follow-up. The code fits in a dozen lines. What the interviewer actually wants to hear is the word amortized, and a clear explanation of why a dequeue that sometimes moves every element is still O(1) on average. This article builds the queue, shows the one mistake that breaks the order, and counts the work so the amortized claim is something you can check rather than recite.

The problem it solves

Build a first-in, first-out queue with push, pop, peek and empty, using only stack operations: push to the top, pop from the top, look at the top, check size. A stack is last-in, first-out, so a single stack returns items in exactly the wrong order.

After pushing 1, 2 and 3, a queue must return 1, then 2. A stack would return 3 first.

The intuition

Pouring one stack into another reverses it. Pop 3, 2, 1 off the first stack and push them onto the second, and the second now has 1 on top. Reversing a reversal restores the arrival order, which is exactly what a queue needs.

So keep two stacks with separate jobs:

• Inbox: every push goes here. It is always a single, cheap append.
• Outbox: every pop and peek reads from here. Its top is always the oldest item in the queue.

The rule that makes it correct is pour only when the outbox is empty. While the outbox holds anything, those items are older than everything in the inbox and must leave first. Pouring early would drop newer items on top of them. When the outbox is empty, pour the whole inbox across in one go; now the oldest remaining item is on top.

The cost argument is just as short. Follow one item through its life: pushed onto the inbox once, popped off the inbox once, pushed onto the outbox once, popped off the outbox once. Four stack operations per item, ever. A pop that pours a thousand items is expensive, but those thousand items never move again, and the next 999 pops are single operations. Spread over all the calls, the cost per operation is constant. That is what amortized O(1) means: a guarantee about the total, not about each call.

Watch it run

The animation follows the lesson: enqueue 1, 2 and 3, then dequeue twice. Arrivals pile up in the inbox, and departures are served from the outbox. enqueue(1) is a plain push. After enqueue(2) the problem is visible: 1 is buried under 2, but a queue must serve 1 first. After enqueue(3) the inbox holds the arrival order upside down. The first dequeue() finds the outbox empty, so it pours the whole inbox across. 3 was on top of the inbox, so it lands at the bottom of the outbox; 2 follows on top of it; 1 goes last and ends up on top. The order has been flipped. Popping the outbox returns 1, the oldest item; that one dequeue cost O(n), but it paid for all three. The second dequeue() finds the outbox not empty, so there is no pouring, just a pop that returns 2. Every item crosses between the stacks at most once.

The code

The lesson's queue with peek and a counter of stack operations:

class TwoStackQueue:
    def __init__(self):
        self.inbox, self.outbox = [], []
        self.ops = 0                              # stack pushes and pops, both stacks

    def push(self, x):
        self.inbox.append(x)
        self.ops += 1

    def _refill(self):
        if not self.outbox:                       # pour only when the outbox is empty
            while self.inbox:
                self.outbox.append(self.inbox.pop())
                self.ops += 2

    def pop(self):
        self._refill()
        self.ops += 1
        return self.outbox.pop()

    def peek(self):
        self._refill()
        return self.outbox[-1]

    def empty(self):
        return not self.inbox and not self.outbox

q = TwoStackQueue()
for x in [1, 2, 3]:
    q.push(x)
print(q.pop(), q.pop(), q.ops)                    # 1 2 11
q.push(4)
print(q.peek(), q.pop(), q.pop(), q.empty())      # 3 3 4 True

Pouring whenever you pop, even when the outbox still has items, breaks the order:

class Broken(TwoStackQueue):
    def _refill(self):
        while self.inbox:                         # pours on top of older items
            self.outbox.append(self.inbox.pop())

b = Broken()
for x in [1, 2, 3]:
    b.push(x)
print(b.pop())                                    # 1
b.push(4)
print(b.pop())                                    # 4   but 2 arrived first

One expensive pop, then cheap ones: the amortized cost in numbers.

q = TwoStackQueue()
for x in range(1000):
    q.push(x)
before = q.ops
q.pop()
print(q.ops - before)                             # 2001
for _ in range(999):
    q.pop()
print(q.ops, q.ops / 2000)                        # 4000 2.0

Against collections.deque on 3,000 random sequences of operations, also checking the four-operations-per-item bound:

import random
from collections import deque

random.seed(18)
ok = True
for _ in range(3000):
    q, ref, pushes = TwoStackQueue(), deque(), 0
    for _ in range(random.randint(1, 30)):
        if ref and random.random() < 0.45:
            ok &= q.pop() == ref.popleft()
        elif ref and random.random() < 0.2:
            ok &= q.peek() == ref[0]
        else:
            x = random.randint(0, 99)
            q.push(x)
            ref.append(x)
            pushes += 1
        ok &= q.empty() == (not ref)
    ok &= q.ops <= 4 * pushes
print(ok)                                         # True

The complexity

• push: O(1) always.
• pop and peek: O(1) amortized, O(n) worst case for a single call that pours n items.
• Total: any sequence of m operations costs O(m), because each item costs at most four stack operations over its lifetime. In the run above, 1,000 pushes and 1,000 pops cost exactly 4,000.
• Space: O(n) for the items, split across the two stacks.

Where it goes wrong

• Pouring when the outbox is not empty. Newer items land on top of older ones, as the broken version shows.
• Pouring back after every pop. Moving everything back to the inbox makes every pop O(n) and the whole thing O(n²).
• Claiming O(1) worst case. It is amortized. If a single slow call matters, as in hard real-time code, say so and use a real queue or a ring buffer.
• Forgetting peek also needs the refill. Reading outbox[-1] on an empty outbox fails even when the queue has items.
• Checking empty on one stack. The queue is empty only when both are.

When it shows up in interviews

It is a common easy question and a favourite for introducing amortized analysis. Expect "what is the cost of pop?", and treat "O(n)" as half an answer. The reverse question, a stack from queues, also comes up; there one operation is O(n) every time, with no amortization to save it. In system design the same inbox and outbox idea appears as a write buffer drained in batches.

How to say it in an interview

"I keep an inbox stack for pushes and an outbox stack for pops. Push always goes to the inbox. For pop or peek, if the outbox is empty I pour the whole inbox into it, which reverses the order so the oldest item is on top, then I pop from the outbox. I only pour when the outbox is empty, otherwise newer items would land on top of older ones. Push is O(1). Pop is O(n) in the worst case, but each item is pushed at most twice and popped at most twice in its lifetime, so any sequence of operations is linear and pop is O(1) amortized."

The stack itself is covered in stack basics, and another stack with an extra guarantee is in min stack.