Implement Queue Using Stacks: The Lazy Transfer Trick

LeetCode's Implement Queue Using Stacks (problem 232) asks you to build a FIFO queue using only two stacks. It is rated easy, but the "amortized O(1)" analysis trips up a lot of people. The trick itself is elegant: you use one stack for pushing and another for popping, and you only transfer elements between them when you absolutely have to. That laziness is what makes it efficient.

The problem

Implement a first-in, first-out queue using only two stacks. Your queue should support the standard operations:

• push(x) pushes element x to the back of the queue
• pop() removes the element from the front and returns it
• peek() returns the front element without removing it
• empty() returns True if the queue has no elements

You may only use standard stack operations: push to top, pop from top, peek at top, and check if empty.

q = MyQueue()
q.push(1)
q.push(2)
q.peek()   # returns 1
q.pop()    # returns 1
q.empty()  # returns False

The challenge is that stacks are LIFO (last in, first out) while queues are FIFO (first in, first out). If you push 1, 2, 3 onto a stack and then pop, you get 3 first. But a queue should give you 1 first. How do you flip the order?

The key insight: two stacks flip the order

Here is the trick: if you pop every element from one stack and push each one onto a second stack, the order reverses. The element that was at the bottom of the first stack ends up on top of the second stack.

Think about it. Stack A has [1, 2, 3] with 3 on top. Pop 3, push onto stack B. Pop 2, push onto B. Pop 1, push onto B. Now stack B has [3, 2, 1] with 1 on top. The oldest element is now the most accessible one. That is exactly what a queue needs.

So the two-stack queue works like this:

1. Input stack: where new elements get pushed.
2. Output stack: where elements get popped/peeked from.

When someone calls pop() or peek() and the output stack is empty, dump everything from the input stack into the output stack. That single transfer flips the order. After that, you just pop from the output stack like normal.

Step-by-step walkthrough

Let's trace through a sequence: push(1), push(2), push(3), peek(), pop(), push(4), pop(). Watch how the two stacks work together to maintain FIFO order.

The important thing to notice: we only transferred elements once, in step 4. After that transfer, the output stack had everything in the right order. Subsequent pops did not need another transfer because the output stack still had elements.

The code

class MyQueue:
    def __init__(self):
        self.input = []   # push stack
        self.output = []  # pop stack

    def push(self, x: int) -> None:
        self.input.append(x)

    def pop(self) -> int:
        self._transfer()
        return self.output.pop()

    def peek(self) -> int:
        self._transfer()
        return self.output[-1]

    def empty(self) -> bool:
        return not self.input and not self.output

    def _transfer(self) -> None:
        if not self.output:
            while self.input:
                self.output.append(self.input.pop())

That is the whole solution. Let's break down the logic:

1. push: always append to the input stack. O(1), no tricks.
2. pop: call _transfer (which does nothing if output is not empty), then pop from the output stack.
3. peek: same as pop but use output[-1] instead of output.pop().
4. empty: both stacks must be empty for the queue to be empty.
5. _transfer: the heart of the algorithm. Only runs when the output stack is empty. Pops everything from input and pushes onto output, reversing the order.

The _transfer method is the only place where work happens in bulk, and it only fires when the output stack is completely drained.

Why the amortized cost is O(1)

This is the part that confuses people. A single pop() call might trigger a transfer that moves n elements. That sounds like O(n). How can it be O(1)?

The key is that every element gets transferred at most once. An element enters the system through push (one operation on the input stack). It gets transferred from the input stack to the output stack exactly once (one pop from input, one push to output). Then it leaves through pop (one operation on the output stack). That is a constant number of stack operations per element across its entire lifetime.

If you push n elements and then pop all of them, the transfer moves n elements in one shot, but that single expensive pop "pays for" all n elements at once. Spread the cost across all n operations and each one is O(1) on average.

Space: O(n) where n is the number of elements in the queue. Every element lives in exactly one of the two stacks at any time.

Common mistakes

Watch out for these when implementing the two-stack queue:

1. Transferring on every pop. If you dump input into output every single time someone calls pop(), you lose the amortized guarantee. Only transfer when the output stack is empty. If output still has elements, they are already in the right order.

2. Forgetting to check both stacks in empty(). The queue is only empty when both stacks are empty. Elements might be sitting in the input stack waiting to be transferred.

3. Mixing up push targets. New elements always go to the input stack. If you accidentally push to the output stack, the FIFO ordering breaks.

4. Transferring in the wrong direction. The transfer goes from input to output, not the other way around. If you transfer from output back to input, you just un-reverse the order and end up back where you started.

The building blocks

This problem is built on two core building blocks:

Stack reversal

The idea that popping from one stack and pushing onto another reverses the element order. This is the fundamental mechanism that converts LIFO to FIFO. You will see this same reversal concept in problems that need to process elements in a different order than they were received.

Lazy evaluation

The decision to defer work until it is actually needed. We do not reorganize elements on every push. We wait until someone asks for the front element and the output stack is empty. Only then do we pay the transfer cost. This lazy approach is what gives us amortized O(1) instead of O(n) per operation.

These two ideas combine to create a surprisingly efficient data structure. Stack reversal provides the mechanism, and lazy evaluation provides the performance.

Edge cases

Before submitting, verify your solution handles these:

• Interleaved push and pop. push(1), pop(), push(2), pop(). The transfer fires on each pop since the output stack gets drained every time. Each transfer moves just one element.
• Multiple pops after multiple pushes. push(1), push(2), push(3), pop(), pop(), pop(). One transfer moves all three, then the three pops just read from the output stack.
• Peek followed by pop. peek() triggers the transfer, and the subsequent pop() should return the same value that peek returned. Both call _transfer but the second call does nothing because output is already populated.
• Push after partial drain. push(1), push(2), pop(), push(3), pop(). After the first pop transfers [1, 2] to output, push(3) goes to input. The second pop takes 2 from output (not 3). Element 3 stays in input until the next transfer.
• Single element. push(1), peek(), pop(). The transfer moves one element. Simple but worth verifying.

From understanding to recall

The two-stack queue is one of those problems where the idea clicks immediately but the implementation details are easy to fumble. Which stack do you push to? When do you transfer? Do you transfer on push or on pop? Is it if not self.output or if not self.input?

These are small details, but in an interview, mixing up the transfer direction or forgetting the lazy check turns a correct solution into a broken one. The code is only about 15 lines, but each line carries weight. The if not self.output guard, the while loop direction, the not self.input and not self.output in empty. Get any of them wrong and specific test cases will fail.

Spaced repetition drilling locks in these details. You write the implementation from scratch at increasing intervals until the transfer logic and the laziness guard are second nature. That is the difference between "I know two stacks make a queue" and "I can implement it correctly in ninety seconds."

Related posts

• Min Stack - Another two-stack design problem where an auxiliary stack tracks extra state alongside the main stack
• Stacks: Last In, First Out - Deep dive into the stack data structure itself, including LIFO ordering and the operations that make this queue trick possible

CodeBricks breaks the two-stack queue pattern into its reusable pieces and drills them individually. You type the implementation from scratch each session, building the muscle memory so that when LeetCode 232 or any "implement X using Y" question comes up in an interview, you can write it without hesitation.