Problem Description

This problem asks you to implement a stack data structure using only two queues. A stack follows Last-In-First-Out (LIFO) principle, while a queue follows First-In-First-Out (FIFO) principle. The challenge is to simulate stack behavior using queue operations.

You need to implement a MyStack class with four methods:

• push(x): Add element x to the top of the stack
• pop(): Remove and return the top element from the stack
• top(): Return the top element without removing it
• empty(): Check if the stack is empty and return true or false

The key constraint is that you can only use standard queue operations:

• Push to back (enqueue)
• Pop/peek from front (dequeue)
• Check size
• Check if empty

The solution uses two queues q1 and q2. The clever approach maintains q1 such that its front element is always the stack's top element. During a push operation:

1. New element x is added to q2
2. All elements from q1 are transferred to q2 (behind x)
3. q1 and q2 are swapped

This ensures the most recently pushed element is always at the front of q1, making pop() and top() operations simple - they just operate on the front of q1. The time complexity for push is O(n) where n is the number of elements, while pop(), top(), and empty() are all O(1).

Intuition

The fundamental challenge is that queues and stacks have opposite access patterns. In a queue, the first element added is the first one removed (FIFO), while in a stack, the last element added is the first one removed (LIFO). To bridge this gap, we need to manipulate the order of elements.

The key insight is that we want the most recently added element to be accessible first. Since queues only allow removal from the front, we need to ensure the newest element is always at the front of our queue.

Think about what happens when we add a new element to a queue - it goes to the back. But we want it at the front for stack behavior. One way to achieve this is to reverse the entire queue after each insertion. However, we can't reverse a queue in-place using only standard queue operations.

This leads us to use two queues. When pushing a new element:

• We can add it to an empty queue q2 first, making it the front element
• Then transfer all existing elements from q1 to q2, placing them behind the new element
• Finally swap the queues, so q1 always contains our "stack" with the newest element at front

This rearrangement ensures that elements in q1 are ordered from newest to oldest (front to back), perfectly mimicking stack behavior. The beauty of this approach is that once elements are arranged this way during push, all other operations become trivial - pop() and top() simply access the front of q1, which is exactly where our stack's top element resides.

The trade-off is clear: we do more work during push (moving all elements) to make pop and top extremely efficient.

Solution Approach

The implementation uses two queues q1 and q2, where q1 serves as the main storage for stack elements and q2 acts as a temporary helper queue. The core strategy is to maintain q1 such that elements are ordered from newest to oldest (front to back).

Data Structure Initialization:

def __init__(self):
    self.q1 = deque()
    self.q2 = deque()

We initialize two empty queues using Python's deque (double-ended queue) which supports efficient queue operations.

Push Operation - O(n):

def push(self, x: int) -> None:
    self.q2.append(x)
    while self.q1:
        self.q2.append(self.q1.popleft())
    self.q1, self.q2 = self.q2, self.q1

1. Add the new element x to the empty queue q2
2. Transfer all elements from q1 to q2 one by one using popleft() and append()
3. Swap the references of q1 and q2

After this operation, q1 contains all elements with x at the front, followed by the previously existing elements in their original order.

Pop Operation - O(1):

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

Simply remove and return the front element of q1, which is the most recently pushed element (stack's top).

Top Operation - O(1):

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

Access the front element of q1 without removing it. This gives us the stack's top element.

Empty Operation - O(1):

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

Check if q1 is empty by verifying its length is zero.

The pattern used here is essentially "reversing on insertion" - by rearranging elements during each push operation, we ensure that subsequent read operations (pop and top) are optimal. This is a classic time-complexity trade-off where we accept slower insertion to achieve faster retrieval.

Example Walkthrough

Let's walk through a sequence of operations to see how the two-queue approach maintains stack behavior:

Initial State:

• q1 = [] (empty)
• q2 = [] (empty)

Operation 1: push(3)

1. Add 3 to q2: q2 = [3]
2. Transfer all elements from q1 to q2: q1 is empty, so nothing to transfer
3. Swap queues: q1 = [3], q2 = []

State after push(3): q1 = [3], q2 = []

Operation 2: push(7)

1. Add 7 to q2: q2 = [7]
2. Transfer all elements from q1 to q2:
   • Remove 3 from front of q1, add to back of q2
   • Now q2 = [7, 3], q1 = []
3. Swap queues: q1 = [7, 3], q2 = []

State after push(7): q1 = [7, 3], q2 = []

Operation 3: push(5)

1. Add 5 to q2: q2 = [5]
2. Transfer all elements from q1 to q2:
   • Remove 7 from front of q1, add to back of q2: q2 = [5, 7]
   • Remove 3 from front of q1, add to back of q2: q2 = [5, 7, 3]
   • Now q1 = []
3. Swap queues: q1 = [5, 7, 3], q2 = []

State after push(5): q1 = [5, 7, 3], q2 = []

Operation 4: top()

• Return front element of q1 without removing: returns 5
• State remains: q1 = [5, 7, 3], q2 = []

Operation 5: pop()

• Remove and return front element of q1: returns 5
• State after: q1 = [7, 3], q2 = []

Operation 6: pop()

• Remove and return front element of q1: returns 7
• State after: q1 = [3], q2 = []

Operation 7: empty()

• Check if q1 is empty: len(q1) = 1, returns false

Operation 8: pop()

• Remove and return front element of q1: returns 3
• State after: q1 = [], q2 = []

Operation 9: empty()

• Check if q1 is empty: len(q1) = 0, returns true

Notice how the elements are popped in LIFO order (5, 7, 3) even though we're using queues. The key is that after each push, the newest element is positioned at the front of q1, making it immediately accessible for pop and top operations.

Solution Implementation

Time and Space Complexity

Time Complexity:

• push(x): O(n) where n is the number of elements currently in the stack. This is because we need to transfer all elements from q1 to q2 after adding the new element, which requires n dequeue and enqueue operations.
• pop(): O(1) since we only perform a single dequeue operation from q1.
• top(): O(1) since we only access the first element of q1 directly.
• empty(): O(1) since we only check the length of q1.

Space Complexity: O(n) where n is the number of elements in the stack. At any given time, all elements are stored in either q1 or temporarily in both queues during the push operation. The maximum space used is when all n elements are stored in q1, plus the temporary space in q2 during transfers. However, since we swap the references rather than copying, the overall space complexity remains O(n).

Common Pitfalls

1. Forgetting to Swap Queues After Push Operation

A common mistake is transferring elements from q1 to q2 but forgetting to swap the queue references afterward. This breaks the invariant that q1 should always contain the stack elements.

Incorrect Implementation:

def push(self, x: int) -> None:
    self.q2.append(x)
    while self.q1:
        self.q2.append(self.q1.popleft())
    # Missing swap! q1 is now empty and q2 has all elements

Correct Implementation:

def push(self, x: int) -> None:
    self.q2.append(x)
    while self.q1:
        self.q2.append(self.q1.popleft())
    self.q1, self.q2 = self.q2, self.q1  # Critical swap operation

2. Using Wrong Queue Order During Push

Another pitfall is adding the new element after transferring existing elements, which results in incorrect stack order.

Incorrect Implementation:

def push(self, x: int) -> None:
    while self.q1:
        self.q2.append(self.q1.popleft())
    self.q2.append(x)  # Wrong! x should be first, not last
    self.q1, self.q2 = self.q2, self.q1

Correct Implementation:

def push(self, x: int) -> None:
    self.q2.append(x)  # Add new element first
    while self.q1:
        self.q2.append(self.q1.popleft())  # Then add existing elements
    self.q1, self.q2 = self.q2, self.q1

3. Accessing Empty Queue in top() Method

Calling top() on an empty stack will raise an IndexError when trying to access q1[0].

Vulnerable Implementation:

def top(self) -> int:
    return self.q1[0]  # Crashes if q1 is empty

Defensive Implementation:

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

4. Memory Leak with Queue References

Not properly clearing q2 after swapping can lead to unnecessary memory usage if the implementation is modified later.

Better Practice:

def push(self, x: int) -> None:
    self.q2.append(x)
    while self.q1:
        self.q2.append(self.q1.popleft())
    self.q1, self.q2 = self.q2, self.q1
    # q2 is now referencing the old q1 which is already empty - no issue
    # But explicitly clearing can prevent bugs if code is modified later
    self.q2.clear()  # Optional but safer

5. Using List Instead of Deque

Using Python's list with pop(0) instead of deque with popleft() results in O(n) time complexity for dequeue operations.

Inefficient Implementation:

def __init__(self):
    self.q1 = []  # Using list
    self.q2 = []

def pop(self) -> int:
    return self.q1.pop(0)  # O(n) operation with list!

Efficient Implementation:

from collections import deque

def __init__(self):
    self.q1 = deque()  # Using deque
    self.q2 = deque()

def pop(self) -> int:
    return self.q1.popleft()  # O(1) operation with deque