Introduction

Implementing a stack with two queues is a classic interview and data-structure exercise. It forces you to simulate Last-In First-Out behavior on top of First-In First-Out primitives. The core design choice is where you pay the cost: during push or during pop.

Problem Setup and Tradeoff

A stack requires these operations:

• push(x) inserts an element on top.
• pop() removes and returns the top element.
• top() returns the top element without removing it.
• empty() tells whether the stack has no elements.

With two queues, there are two standard strategies:

• expensive push, cheap pop
• cheap push, expensive pop

Both are valid. Choose based on expected call frequency.

Strategy A: Expensive Push, Cheap Pop

In this approach, queue q1 always keeps stack order at its front. To push, place the new element into q2, move all items from q1 to q2, then swap the two queues.

Python implementation

1from collections import deque
2
3class StackTwoQueues:
4    def __init__(self):
5        self.q1 = deque()
6        self.q2 = deque()
7
8    def push(self, x: int) -> None:
9        self.q2.append(x)
10        while self.q1:
11            self.q2.append(self.q1.popleft())
12        self.q1, self.q2 = self.q2, self.q1
13
14    def pop(self) -> int:
15        if not self.q1:
16            raise IndexError("pop from empty stack")
17        return self.q1.popleft()
18
19    def top(self) -> int:
20        if not self.q1:
21            raise IndexError("top from empty stack")
22        return self.q1[0]
23
24    def empty(self) -> bool:
25        return len(self.q1) == 0
26
27
28if __name__ == "__main__":
29    s = StackTwoQueues()
30    s.push(10)
31    s.push(20)
32    s.push(30)
33
34    print(s.top())   # 30
35    print(s.pop())   # 30
36    print(s.pop())   # 20
37    print(s.empty()) # False

Complexity for Strategy A:

• push: O(n)
• pop: O(1)
• top: O(1)
• extra space: O(n)

This is a good choice when reads and pops are frequent compared to pushes.

Strategy B: Cheap Push, Expensive Pop

You can invert the cost profile. Push directly to q1, then for pop move n - 1 elements to q2, remove the last element, and swap queues.

1from collections import deque
2
3class StackTwoQueuesPopHeavy:
4    def __init__(self):
5        self.q1 = deque()
6        self.q2 = deque()
7
8    def push(self, x: int) -> None:
9        self.q1.append(x)
10
11    def pop(self) -> int:
12        if not self.q1:
13            raise IndexError("pop from empty stack")
14
15        while len(self.q1) > 1:
16            self.q2.append(self.q1.popleft())
17
18        val = self.q1.popleft()
19        self.q1, self.q2 = self.q2, self.q1
20        return val
21
22    def top(self) -> int:
23        if not self.q1:
24            raise IndexError("top from empty stack")
25
26        while len(self.q1) > 1:
27            self.q2.append(self.q1.popleft())
28
29        val = self.q1.popleft()
30        self.q2.append(val)
31        self.q1, self.q2 = self.q2, self.q1
32        return val
33
34    def empty(self) -> bool:
35        return len(self.q1) == 0

Complexity for Strategy B:

• push: O(1)
• pop: O(n)
• top: O(n)
• extra space: O(n)

Correctness Intuition

For Strategy A, every push rebuilds queue order so the newest element becomes the next dequeued item from q1. That exactly matches stack top behavior.

For Strategy B, queue order remains insertion order until pop time. The transfer step isolates the newest element as the final remaining element in q1, which is then removed.

A short invariant for Strategy A is:

• after each push, q1 front equals stack top.

A short invariant for Strategy B is:

• before each pop, newest element is the last item in q1.

These invariants make debugging easier than memorizing raw steps.

Testing Recommendations

For interview code, basic manual checks are often enough. For production helpers, add unit tests for:

• popping from empty stack
• top on empty stack
• alternating push and pop sequences
• repeated pushes followed by full drain

Example using Python assertions:

1def test_stack_behavior():
2    s = StackTwoQueues()
3    assert s.empty()
4
5    s.push(1)
6    s.push(2)
7    s.push(3)
8
9    assert s.top() == 3
10    assert s.pop() == 3
11    assert s.pop() == 2
12    assert s.pop() == 1
13    assert s.empty()

Common Pitfalls

A common bug is forgetting to swap queues after transfer. Without swapping, subsequent calls read from the wrong queue and order breaks.

Another issue is not handling empty states. pop and top should fail explicitly instead of returning incorrect sentinel values.

Developers also mix strategy logic accidentally, such as using Strategy A push with Strategy B top. Keep one consistent method set.

Finally, avoid hiding complexity assumptions. If your workload is push-heavy, Strategy A may degrade throughput. Pick the strategy that aligns with expected usage patterns.

Summary

• Two queues can implement stack semantics correctly with clear invariants.
• Strategy A makes push expensive and pop cheap.
• Strategy B makes push cheap and pop expensive.
• Queue swapping and empty checks are critical for correctness.
• Unit tests should cover edge cases and operation order guarantees.