Implement Queue using Stacks: Multiple Solutions and Complexity Analysis

A queue is a First-In-First-Out (FIFO) data structure, while a stack follows Last-In-First-Out (LIFO). Implementing a queue using only stacks means we must simulate FIFO behavior with LIFO primitives. This classic problem tests your understanding of data structure fundamentals, amortized analysis, and design trade-offs. In this tutorial we'll explore multiple solutions, from the straightforward but inefficient to the elegant amortized O(1) approach, complete with code examples and complexity breakdowns.

1. The Core Idea: Why This Matters

In many coding interviews and real-world scenarios, you are constrained to use only stacks (or their underlying push/pop operations) to build a queue. This forces you to think about how to reverse order efficiently. The key insight is that two stacks can reverse order: pushing elements onto one stack and then transferring them to another reverses the sequence, turning LIFO into FIFO. Understanding this teaches amortized analysis, lazy evaluation, and how to balance expensive operations.

2. Approach 1: Push-Costly (Enqueue Expensive)

In this version, every enqueue operation ensures that the main stack maintains queue order (oldest element on top). We use two stacks: main (acts as the queue front) and aux (temporary). For each enqueue:

Pop all elements from main to aux (now aux has reversed order, newest on top).
Push the new element onto aux (now newest is above older ones).
Pop everything back from aux to main, restoring queue order with the new element at the bottom.

Dequeue simply pops from main. This makes enqueue O(n) time, dequeue O(1).

class QueuePushCostly:
    def __init__(self):
        self.main = []   # stack, top is front of queue
        self.aux = []    # temporary stack

    def enqueue(self, item):
        # Transfer all from main to aux
        while self.main:
            self.aux.append(self.main.pop())
        # Push new item onto aux (now at bottom when reversed back)
        self.aux.append(item)
        # Transfer back to main
        while self.aux:
            self.main.append(self.aux.pop())

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

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

    def empty(self):
        return len(self.main) == 0

    def size(self):
        return len(self.main)

Time Complexity: enqueue O(n), dequeue O(1), peek O(1). Space: O(n) for n elements.

3. Approach 2: Pop-Costly (Dequeue Expensive)

Here we keep the newest element on top of the primary stack (in_stack). Enqueue is simply a push onto in_stack – O(1). Dequeue becomes expensive: when out_stack (which holds reversed order) is empty, we pop everything from in_stack to out_stack, reversing order. The top of out_stack becomes the front of the queue. Then we pop from out_stack. This is the classic two-stack queue.

class QueuePopCostly:
    def __init__(self):
        self.in_stack = []   # newest on top
        self.out_stack = []  # oldest on top (reversed)

    def enqueue(self, item):
        self.in_stack.append(item)

    def dequeue(self):
        if not self.out_stack:
            # Transfer all from in_stack to out_stack (reverses order)
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        if not self.out_stack:
            raise IndexError("Queue empty")
        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())
        if not self.out_stack:
            raise IndexError("Queue empty")
        return self.out_stack[-1]

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

    def size(self):
        return len(self.in_stack) + len(self.out_stack)

Time Complexity: enqueue O(1), dequeue worst-case O(n) but amortized O(1). Let’s dive into the amortized analysis.

4. Amortized Analysis: Why Dequeue is O(1) on Average

Each element is moved from in_stack to out_stack exactly once during its lifetime in the queue. A dequeue operation might trigger a transfer of m elements, costing O(m). However, those m elements were previously enqueued via m separate O(1) operations. If we perform n enqueues and then n dequeues, total cost = n * O(1) (enqueue) + O(n) (first transfer) + (n-1) * O(1) (subsequent dequeues). That's O(n) total, or O(1) per operation on average. Formally, using the accounting method, we assign a cost of 2 for each enqueue (1 for the push, 1 prepaid for future transfer), making dequeue effectively free. Hence amortized O(1) per operation.

5. Approach 3: Recursive Dequeue (Using Call Stack)

A less practical but theoretically interesting solution uses recursion (and the implicit call stack) to reverse order on dequeue without an explicit second stack. To dequeue, we pop from the primary stack; if the stack is empty after pop, we have the front element. Otherwise, we recursively call dequeue, and after obtaining the front element, we push back the popped element. This effectively uses the function call stack as temporary storage. It's O(n) per dequeue and risks stack overflow, so it's rarely used in production but demonstrates deep understanding.

class QueueRecursive:
    def __init__(self):
        self.stack = []

    def enqueue(self, item):
        self.stack.append(item)

    def dequeue(self):
        if not self.stack:
            raise IndexError("Queue empty")
        top = self.stack.pop()
        if not self.stack:  # base case: top was the oldest
            return top
        else:
            front = self.dequeue()
            self.stack.append(top)
            return front

    def empty(self):
        return len(self.stack) == 0

Time complexity: enqueue O(1), dequeue O(n) due to recursion through the entire stack. Not amortized.

6. Complexity Analysis Summary

Let’s compare the three approaches side-by-side:

Push-Costly: Enqueue O(n), Dequeue O(1). No amortized benefit. Simple but slow for write-heavy workloads.
Pop-Costly (Two Stacks Lazy): Enqueue O(1), Dequeue amortized O(1). Best for general use and interviews.
Recursive: Enqueue O(1), Dequeue O(n). Elegant but impractical due to recursion depth.

7. Best Practices and Interview Tips

When implementing a queue using stacks, follow these guidelines:

Prefer the lazy two-stack approach (pop-costly). It gives amortized O(1) and is the expected solution in most technical interviews.
Handle edge cases: Empty queue exceptions on dequeue/peek; ensure peek also triggers transfer if needed.
Explain amortized analysis: Walk the interviewer through why each element is moved only once, giving O(1) amortized.
Keep operations clean: Use descriptive variable names (in_stack/out_stack or push_stack/pop_stack).
Consider thread safety: In production, these structures aren't thread-safe by default; you'd need locks or concurrent stacks.
Test thoroughly: Verify interleaved enqueue and dequeue sequences, and empty state transitions.

8. Usage Example and Testing

Here's how you might use the lazy two-stack queue and a quick test:

def test_queue():
    q = QueuePopCostly()
    q.enqueue(1)
    q.enqueue(2)
    q.enqueue(3)
    print(q.dequeue())  # 1
    q.enqueue(4)
    print(q.peek())     # 2
    print(q.dequeue())  # 2
    print(q.dequeue())  # 3
    print(q.dequeue())  # 4
    print(q.empty())    # True

test_queue()

9. Conclusion

Implementing a queue with stacks is a brilliant exercise in data structure adaptation and amortized analysis. The two-stack lazy solution offers optimal amortized performance and remains the gold standard for interviews and practical use. By exploring push-costly, pop-costly, and recursive methods, you gain a deeper appreciation for how order reversal can be managed efficiently. Remember: the key is moving elements only when necessary, spreading the cost across operations. Use this knowledge to ace your next coding challenge and to design elegant abstractions with limited primitives.