Implement Stack Using Two Queues — Two Approaches Explained

This is LeetCode 225 — the reverse of implementing a queue with two stacks. A queue gives FIFO order, but a stack needs LIFO. The trick is rotating elements to bring the most recent one to the front.

Why Is This Harder Than Queue-via-Stacks?

With two stacks making a queue, each element transfers exactly once. With queues making a stack, we must rotate elements on every push or every pop — there is no amortized trick.

Approach 1: Costly Push

Make push expensive so pop is always O(1). After pushing a new element into q2, rotate all elements from q1 into q2, then swap names.

from collections import deque

class StackCostlyPush:
    """
    Stack using two queues — O(n) push, O(1) pop.
    """
    def __init__(self):
        self.q1 = deque()  # main queue
        self.q2 = deque()  # temporary

    def push(self, x: int) -> None:
        # Put new element in q2
        self.q2.append(x)

        # Move all from q1 to q2 (new element is now at front)
        while self.q1:
            self.q2.append(self.q1.popleft())

        # Swap q1 and q2
        self.q1, self.q2 = self.q2, self.q1

    def pop(self) -> int:
        if not self.q1:
            raise IndexError("Stack is empty")
        return self.q1.popleft()

    def top(self) -> int:
        if not self.q1:
            raise IndexError("Stack is empty")
        return self.q1[0]

    def empty(self) -> bool:
        return len(self.q1) == 0

Trace

push(1): q2=[1], move q1→q2, swap → q1=[1]
push(2): q2=[2], move 1→q2 → q2=[2,1], swap → q1=[2,1]
push(3): q2=[3], move 2,1→q2 → q2=[3,2,1], swap → q1=[3,2,1]
pop():   popleft → 3 ✓ (LIFO)
pop():   popleft → 2 ✓ (LIFO)

Approach 2: Costly Pop

Make pop expensive by rotating n-1 elements to find the last one pushed.

from collections import deque

class StackCostlyPop:
    """
    Stack using two queues — O(1) push, O(n) pop.
    """
    def __init__(self):
        self.q1 = deque()
        self.q2 = deque()

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

    def pop(self) -> int:
        if not self.q1:
            raise IndexError("Stack is empty")

        # Move all but last element to q2
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())

        # Last element is the "top" of stack
        result = self.q1.popleft()

        # Swap so q1 has the elements again
        self.q1, self.q2 = self.q2, self.q1
        return result

    def top(self) -> int:
        if not self.q1:
            raise IndexError("Stack is empty")
        # Same as pop but put element back
        while len(self.q1) > 1:
            self.q2.append(self.q1.popleft())
        result = self.q1.popleft()
        self.q2.append(result)
        self.q1, self.q2 = self.q2, self.q1
        return result

    def empty(self) -> bool:
        return len(self.q1) == 0

Trace

push(1): q1=[1]
push(2): q1=[1,2]
push(3): q1=[1,2,3]
pop():   move 1,2→q2, pop 3, swap → q1=[1,2], returns 3 ✓
pop():   move 1→q2, pop 2, swap → q1=[1], returns 2 ✓

Bonus: Single Queue Solution

You can implement a stack with just one queue by rotating after each push.

from collections import deque

class MyStack:
    """
    LeetCode 225 — Stack using a single queue.
    O(n) push, O(1) pop.
    """
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        # Rotate n-1 elements to bring new element to front
        for _ in range(len(self.q) - 1):
            self.q.append(self.q.popleft())

    def pop(self) -> int:
        return self.q.popleft()

    def top(self) -> int:
        return self.q[0]

    def empty(self) -> bool:
        return len(self.q) == 0

How the Rotation Works

push(1): q=[1]           → rotate 0 times → q=[1]
push(2): q=[1,2]         → rotate 1 time  → q=[2,1]
push(3): q=[2,1,3]       → rotate 2 times → q=[3,2,1]
pop():   popleft → 3 ✓

Comparing All Approaches

Edge Cases

s = MyStack()
assert s.empty() == True

s.push(1)
assert s.top() == 1
assert s.pop() == 1
assert s.empty() == True

# Push and pop interleaved
s.push(1)
s.push(2)
assert s.pop() == 2
s.push(3)
assert s.pop() == 3
assert s.pop() == 1

When to Use This Pattern

• Interview preparation: Direct question that tests data structure understanding
• Constrained environments: When only queue operations are available
• Understanding trade-offs: Push-heavy vs pop-heavy workloads demand different approaches

Related Problems

• Implement Queue using Two Stacks — the classic reverse problem
• Min Stack — another stack design question
• Circular Queue — queue design variant