Implement Queue Using Two Stacks — Amortized O(1) Solution

A queue follows FIFO (First In, First Out). A stack follows LIFO (Last In, First Out). These are opposite orderings. So how do you make a queue from two stacks? By using one stack to reverse the order of the other.

This is LeetCode 232 and one of the most frequently asked design questions in interviews.

Core Insight

If you push elements onto Stack A in order [1, 2, 3], then pop them all into Stack B, Stack B contains [3, 2, 1]. Now popping from Stack B gives 1, 2, 3 — exactly FIFO order.

Push 1, 2, 3 onto Stack A:    Stack A = [1, 2, 3] (top = 3)

Transfer to Stack B:
  Pop 3 → push to B           Stack B = [3]
  Pop 2 → push to B           Stack B = [3, 2]
  Pop 1 → push to B           Stack B = [3, 2, 1] (top = 1)

Pop from Stack B → 1 ✓ (FIFO)
Pop from Stack B → 2 ✓ (FIFO)

Approach 1: Costly Enqueue

Every time we enqueue, transfer everything to maintain order.

class QueueCostlyEnqueue:
    """
    Queue using two stacks — O(n) enqueue, O(1) dequeue.
    """
    def __init__(self):
        self.s1 = []  # main stack (front of queue on top)
        self.s2 = []  # temporary

    def enqueue(self, val):
        # Move everything to s2
        while self.s1:
            self.s2.append(self.s1.pop())

        # Push new element to bottom of s1
        self.s1.append(val)

        # Move everything back
        while self.s2:
            self.s1.append(self.s2.pop())

    def dequeue(self):
        if not self.s1:
            raise IndexError("Queue is empty")
        return self.s1.pop()

    def peek(self):
        if not self.s1:
            raise IndexError("Queue is empty")
        return self.s1[-1]

    def is_empty(self):
        return len(self.s1) == 0

Trace

enqueue(1): s1=[1]
enqueue(2): move 1→s2, push 2→s1, move 1 back → s1=[2,1]
enqueue(3): move 1,2→s2, push 3→s1, move 2,1 back → s1=[3,2,1]
dequeue():  pop → 1 ✓
dequeue():  pop → 2 ✓

Complexity

Operation	Time	Space
enqueue	O(n)	O(n)
dequeue	O(1)	O(1)
peek	O(1)	O(1)

Approach 2: Costly Dequeue (Lazy Transfer)

This is the preferred approach. Only transfer when the output stack is empty.

class MyQueue:
    """
    Queue using two stacks — amortized O(1) for all operations.
    LeetCode 232.
    """
    def __init__(self):
        self.in_stack = []   # for push
        self.out_stack = []  # for pop/peek

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

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

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

    def empty(self) -> bool:
        return not self.in_stack and not self.out_stack

    def _transfer(self):
        """Only transfer when out_stack is empty."""
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())

Why This Is Better: Amortized O(1) Analysis

Each element goes through exactly 4 operations in its lifetime:

1. Push onto in_stack — O(1)
2. Pop from in_stack — O(1)
3. Push onto out_stack — O(1)
4. Pop from out_stack — O(1)

Total cost per element = 4 operations. Spread across n elements, the amortized cost per operation is O(1).

Trace

push(1):   in=[1]         out=[]
push(2):   in=[1,2]       out=[]
push(3):   in=[1,2,3]     out=[]
pop():     transfer!       in=[]  out=[3,2,1]  → returns 1
push(4):   in=[4]         out=[3,2]
pop():     out not empty   in=[4] out=[3,2]    → returns 2
pop():     out not empty   in=[4] out=[3]      → returns 3
pop():     transfer!       in=[]  out=[]        → returns 4

Notice: we only transfer when out_stack is empty. Elements pushed after a transfer wait in in_stack until the next transfer.

Edge Cases

# Empty queue operations
q = MyQueue()
assert q.empty() == True

# Single element
q.push(1)
assert q.peek() == 1
assert q.pop() == 1
assert q.empty() == True

# Interleaved push/pop
q.push(1)
q.push(2)
assert q.pop() == 1    # triggers transfer
q.push(3)
assert q.pop() == 2    # no transfer needed
assert q.pop() == 3    # triggers transfer

Comparing the Two Approaches

Approach	Enqueue	Dequeue	Best When
Costly Enqueue	O(n)	O(1)	Many more dequeues than enqueues
Lazy Transfer	O(1)	Amortized O(1)	General use, interviews

The lazy transfer approach is almost always preferred because:

• Both operations are amortized O(1)
• No wasted work — elements only transfer once
• Simpler to reason about

When to Use This Pattern

• Interview question: This is asked directly or as part of larger designs
• Functional programming: Languages without built-in queues but with stacks
• Undo/redo systems: Understanding stack-to-queue conversion helps design these
• Message processing: When you need FIFO from LIFO storage

Common Interview Follow-ups

1. Can you implement it with one stack? Yes, using recursion (the call stack acts as the second stack), but it is O(n) per dequeue.
2. What about thread safety? You would need locks around _transfer and the push/pop operations.
3. Can you make it with O(1) worst case? Not with plain stacks — amortized O(1) is the best you can achieve.

Related Problems

• Implement Stack using Queues — the reverse problem
• Min Stack — another stack design problem
• Circular Queue — queue with fixed size