Problem Description

You need to implement a queue data structure using only two stacks. A queue follows First-In-First-Out (FIFO) principle, meaning elements are removed in the same order they were added. However, stacks follow Last-In-First-Out (LIFO) principle.

Your MyQueue class must support these four operations:

1. push(x): Adds element x to the back of the queue
2. pop(): Removes and returns the element from the front of the queue
3. peek(): Returns the element at the front of the queue without removing it
4. empty(): Returns true if the queue has no elements, false otherwise

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

• Push to top
• Pop from top
• Peek at top
• Check size
• Check if empty

The solution uses two stacks to achieve queue behavior. stk1 serves as the input stack where new elements are pushed. stk2 serves as the output stack for pop and peek operations.

The clever trick is the move() helper function: when we need to access the front of the queue (for pop() or peek()), and stk2 is empty, we transfer all elements from stk1 to stk2. This reversal of elements transforms the LIFO order back to FIFO order, allowing us to access elements in the correct queue order from stk2.

For example, if we push 1, 2, 3 into the queue:

• They go into stk1 as [1, 2, 3] (3 on top)
• When we need to pop, they're moved to stk2 as [3, 2, 1] (1 on top)
• Now popping from stk2 gives us 1, which was the first element pushed

Intuition

The fundamental challenge here is that stacks and queues have opposite access patterns. A stack gives us access to the most recently added element (LIFO), while a queue needs access to the oldest element (FIFO). How can we bridge this gap using only stack operations?

The key insight comes from observing what happens when we transfer elements between two stacks. If we have elements [1, 2, 3] in a stack (with 3 on top) and pop them one by one into another stack, the second stack will have [3, 2, 1] (with 1 on top). This reversal is crucial - the element that was at the bottom of the first stack is now at the top of the second stack!

This gives us our strategy: we can use one stack for incoming elements and another for outgoing elements. Think of it like having two containers where:

• The first container (stk1) collects new arrivals in the order they come
• The second container (stk2) is where we serve from

When stk2 is empty and we need to serve (pop or peek), we transfer everything from stk1 to stk2. This transfer reverses the order, making the oldest element in stk1 become the topmost element in stk2 - exactly what we need for queue behavior!

The beauty of this approach is that each element moves at most twice: once into stk1 during push, and once from stk1 to stk2 during the transfer. After the transfer, elements in stk2 are already in the correct order for serving, so subsequent pops and peeks are direct operations until stk2 is empty again.

This "lazy" transfer strategy (only moving elements when necessary) ensures we maintain amortized O(1) complexity for all operations while using only basic stack operations.

Solution Approach

The implementation uses two stacks to simulate queue behavior. Let's walk through each component:

Data Structure Setup

We initialize two empty stacks:

• stk1: The input stack for enqueue operations
• stk2: The output stack for dequeue operations

Push Operation

The push(x) operation is straightforward - we simply append the element to stk1:

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

This maintains O(1) time complexity since we're just adding to the top of the stack.

The Move Helper Function

The core logic lies in the move() helper function:

def move(self):
    if not self.stk2:
        while self.stk1:
            self.stk2.append(self.stk1.pop())

This function transfers all elements from stk1 to stk2 only when stk2 is empty. The transfer reverses the order of elements, converting LIFO to FIFO ordering.

Pop Operation

For pop(), we first call move() to ensure stk2 has elements in the correct order, then pop from stk2:

def pop(self) -> int:
    self.move()
    return self.stk2.pop()

If stk2 already has elements, move() does nothing. Otherwise, it transfers all elements from stk1.

Peek Operation

The peek() operation follows the same pattern but returns the top element without removing it:

def peek(self) -> int:
    self.move()
    return self.stk2[-1]

Empty Check

The queue is empty only when both stacks are empty:

def empty(self) -> bool:
    return not self.stk1 and not self.stk2

Time Complexity Analysis

• Push: O(1) - Direct append to stk1
• Pop/Peek: Amortized O(1) - Each element is moved at most once from stk1 to stk2. Over n operations, the total cost is O(n), giving amortized O(1) per operation
• Empty: O(1) - Simple boolean check

The key pattern here is the "lazy evaluation" - we only transfer elements when necessary, maintaining efficiency while using only standard stack operations.

Example Walkthrough

Let's trace through a sequence of operations to see how the two-stack approach works:

Initial state: stk1 = [], stk2 = []

Step 1: push(1)

• Add 1 to stk1
• Result: stk1 = [1], stk2 = []

Step 2: push(2)

• Add 2 to stk1
• Result: stk1 = [1, 2], stk2 = []

Step 3: push(3)

• Add 3 to stk1
• Result: stk1 = [1, 2, 3], stk2 = [] (3 is on top)

Step 4: pop()

• Call move(): Since stk2 is empty, transfer all elements from stk1 to stk2
  • Pop 3 from stk1, push to stk2: stk2 = [3]
  • Pop 2 from stk1, push to stk2: stk2 = [3, 2]
  • Pop 1 from stk1, push to stk2: stk2 = [3, 2, 1] (1 is on top)
• After move: stk1 = [], stk2 = [3, 2, 1]
• Pop from stk2: returns 1
• Result: stk1 = [], stk2 = [3, 2]

Step 5: push(4)

• Add 4 to stk1
• Result: stk1 = [4], stk2 = [3, 2]

Step 6: peek()

• Call move(): Since stk2 is not empty, no transfer occurs
• Return top of stk2: returns 2
• Result: stk1 = [4], stk2 = [3, 2] (no change)

Step 7: pop()

• Call move(): stk2 still not empty, no transfer
• Pop from stk2: returns 2
• Result: stk1 = [4], stk2 = [3]

Step 8: pop()

• Call move(): stk2 still not empty, no transfer
• Pop from stk2: returns 3
• Result: stk1 = [4], stk2 = []

Step 9: pop()

• Call move(): Since stk2 is empty, transfer all from stk1
  • Pop 4 from stk1, push to stk2: stk2 = [4]
• After move: stk1 = [], stk2 = [4]
• Pop from stk2: returns 4
• Result: stk1 = [], stk2 = []

Notice how the elements were returned in FIFO order (1, 2, 3, 4) despite using only stack operations. The key moment is when move() transfers elements - this reversal converts the LIFO ordering of stk1 into the FIFO ordering needed for queue operations.

Solution Implementation

Time and Space Complexity

Time Complexity:

• push(x): O(1) - Simply appends an element to stk1.
• pop(): Amortized O(1) - While a single operation might take O(n) when moving all elements from stk1 to stk2, each element is moved at most once from stk1 to stk2. Over n operations, the total cost is O(n), giving amortized O(1) per operation.
• peek(): Amortized O(1) - Same reasoning as pop(). The move() function is called which has amortized O(1) cost, and accessing the last element of stk2 is O(1).
• empty(): O(1) - As mentioned in the reference answer, checking whether both stacks are empty is a constant time operation.
• move(): O(k) where k is the number of elements in stk1 when stk2 is empty, but this contributes to the amortized O(1) complexity of pop() and peek().

Space Complexity:

• O(n) where n is the total number of elements in the queue. The implementation uses two stacks (stk1 and stk2) to store all elements, and at any point, the total elements across both stacks equals the number of elements in the queue.

Common Pitfalls

1. Unnecessary Element Transfers

A common mistake is transferring elements between stacks on every operation, even when not needed. This destroys the amortized O(1) complexity.

Incorrect approach:

def pop(self) -> int:
    # Wrong: Always transferring all elements back and forth
    while self.stk1:
        self.stk2.append(self.stk1.pop())
    result = self.stk2.pop()
    while self.stk2:
        self.stk1.append(self.stk2.pop())
    return result

Solution: Only transfer when output_stack is empty. Once elements are in output_stack, leave them there until they're all consumed.

2. Incorrect Empty Check

Checking only one stack can lead to false positives when elements exist in the other stack.

Incorrect approach:

def empty(self) -> bool:
    # Wrong: Only checking one stack
    return len(self.input_stack) == 0

Solution: Check both stacks: return not self.input_stack and not self.output_stack

3. Transferring on Push Operations

Some implementations mistakenly transfer elements during push operations, which is unnecessary and inefficient.

Incorrect approach:

def push(self, x: int) -> None:
    # Wrong: Unnecessary transfers during push
    while self.output_stack:
        self.input_stack.append(self.output_stack.pop())
    self.input_stack.append(x)

Solution: Simply push to input_stack. Transfers should only happen when accessing the front element (pop/peek).

4. Not Preserving Elements in Output Stack

After a pop or peek operation, some implementations transfer remaining elements back to the input stack, which breaks the amortized complexity.

Incorrect approach:

def peek(self) -> int:
    self._transfer_if_needed()
    result = self.output_stack[-1]
    # Wrong: Moving elements back unnecessarily
    while self.output_stack:
        self.input_stack.append(self.output_stack.pop())
    return result

Solution: Keep elements in output_stack after operations. They're already in the correct order for future pop/peek operations.

5. Race Conditions in Multi-threaded Environments

The implementation isn't thread-safe. Concurrent access could lead to data corruption or incorrect results.

Solution for thread safety:

import threading

class ThreadSafeQueue:
    def __init__(self):
        self.input_stack = []
        self.output_stack = []
        self.lock = threading.Lock()
  
    def push(self, x: int) -> None:
        with self.lock:
            self.input_stack.append(x)
  
    def pop(self) -> int:
        with self.lock:
            self._transfer_if_needed()
            return self.output_stack.pop()

6. Missing Edge Case Handling

Not handling operations on empty queue can cause runtime errors.

Solution: Add validation:

def pop(self) -> int:
    if self.empty():
        raise IndexError("pop from empty queue")
    self._transfer_if_needed()
    return self.output_stack.pop()