LeetCode 225: Implement Stack using Queues Solution in Python Explained

Problem Statement

In LeetCode 225: Implement Stack using Queues, you need to implement a MyStack class with:

• push(x): Adds x to the top of the stack.
• pop(): Removes and returns the top element.
• top(): Returns the top element without removing it.
• empty(): Returns true if the stack is empty, false otherwise.
• Use only standard queue operations: enqueue (add to rear), dequeue (remove from front), peek (view front), and is_empty.

You can use one or more queues. This differs from expression evaluation in LeetCode 224: Basic Calculator, focusing instead on adapting queue behavior to mimic a stack.

Constraints

• 1 ≤ x ≤ 9.
• At most 100 calls to methods.
• All calls are valid (e.g., no pop on empty stack).

Examples

Let’s see a sequence of operations:

Copy codeMyStack stack = new MyStack();
stack.push(1);      // Stack: [1]
stack.push(2);      // Stack: [2,1]
stack.top();        // Returns 2
stack.pop();        // Returns 2, Stack: [1]
stack.empty();      // Returns false

This shows we’re implementing LIFO using FIFO.

Understanding the Problem

How do we solve LeetCode 225: Implement Stack using Queues in Python? A stack is LIFO (last in, first out), while a queue is FIFO (first in, first out). To make a queue act like a stack, we need to rearrange elements so the most recent addition is at the front. A naive approach might use a single queue with costly operations, but we can optimize. This isn’t a geometric problem like LeetCode 223: Rectangle Area; it’s about data structure transformation. We’ll use: 1. Two Queues with Push Cost: O(n) push, O(1) pop/top—our best solution. 2. Single Queue: O(n) push, O(1) pop/top—an alternative.

Let’s dive into the best solution.

Best Solution: Two Queues with Push Cost Approach

Explanation

The Two Queues with Push Cost approach uses two queues:

• q1: Main queue holding the stack elements (top at front).
• q2: Temporary queue for reordering during push.
• Push: Enqueue to q2, move all from q1 to q2, swap q1 and q2.
• Pop: Dequeue from q1.
• Top: Peek at q1’s front.
• Empty: Check if q1 is empty.

This makes push O(n) (reordering n elements) and pop/top O(1), balancing simplicity and efficiency—our best solution.

For pushing 1, 2, 3, it ensures the newest element is at the front.

Step-by-Step Example

Example 1: Operations Sequence

Goal: Implement and test the stack.

• Step 1: Initialize.
• q1 = deque([]), q2 = deque([]).
• Step 2: push(1):
• q2.append(1) → q2=[1].
• Move q1=[] to q2 (empty).
• Swap: q1=[1], q2=[].
• Step 3: push(2):
• q2.append(2) → q2=[2].
• Move q1=[1] to q2 → q2=[2,1].
• Swap: q1=[2,1], q2=[].
• Step 4: push(3):
• q2.append(3) → q2=[3].
• Move q1=[2,1] to q2 → q2=[3,2,1].
• Swap: q1=[3,2,1], q2=[].
• Step 5: top():
• Return q1[0] = 3.
• Step 6: pop():
• q1.popleft() → q1=[2,1], return 3.
• Step 7: empty():
• len(q1) > 0, return false.
• Result: Stack behaves as [2,1] after operations.

Example 2: push(1), pop()

• push(1): q1=[1].
• pop(): q1=[], return 1.

How the Code Works (Two Queues with Push Cost) – Detailed Line-by-Line Explanation

Here’s the Python code with a detailed breakdown using collections.deque:

Copy codefrom collections import deque

class MyStack:
    def __init__(self):
        # Line 1: Initialize two queues
        self.q1 = deque()
        # Main queue (e.g., deque([]))
        self.q2 = deque()
        # Temp queue (e.g., deque([]))

    def push(self, x: int) -> None:
        # Line 2: Push new element
        self.q2.append(x)
        # Add to q2 (e.g., q2=[3])

        # Line 3: Move all from q1 to q2
        while self.q1:
            # Transfer elements (e.g., q1=[2,1])
            self.q2.append(self.q1.popleft())
            # q2 grows (e.g., q2=[3,2,1])

        # Line 4: Swap q1 and q2
        self.q1, self.q2 = self.q2, self.q1
        # q1=[3,2,1], q2=[] now

    def pop(self) -> int:
        # Line 5: Remove and return top
        return self.q1.popleft()
        # Dequeue front (e.g., 3, q1=[2,1])

    def top(self) -> int:
        # Line 6: Return top without removal
        return self.q1[0]
        # Peek front (e.g., 3)

    def empty(self) -> bool:
        # Line 7: Check if stack is empty
        return len(self.q1) == 0
        # True if q1 empty (e.g., false)

This solution mimics a stack using two queues efficiently.

Alternative: Single Queue Approach

Explanation

The Single Queue approach uses one queue:

• Push: Enqueue, then rotate all earlier elements to the back.
• Pop: Dequeue.
• Top: Peek front.
• Empty: Check if queue is empty.

Push is O(n) (rotating n elements), pop/top are O(1), using O(n) space.

Step-by-Step Example

For push(1), push(2):

• push(1): q=[1].
• push(2): q=[1,2], rotate → q=[2,1].
• top(): 2.
• pop(): 2, q=[1].

How the Code Works (Single Queue)

Copy codefrom collections import deque

class MyStackSingle:
    def __init__(self):
        self.q = deque()

    def push(self, x: int) -> None:
        self.q.append(x)
        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

Complexity

• Two Queues with Push Cost:
• Push: O(n) – move n elements.
• Pop/Top: O(1).
• Space: O(n) – two queues.
• Single Queue:
• Push: O(n) – rotate n elements.
• Pop/Top: O(1).
• Space: O(n) – one queue.

Efficiency Notes

Two Queues with Push Cost is our best solution for its clarity and flexibility (can optimize pop instead). Single Queue is more space-efficient but less intuitive due to rotation.

Key Insights

• LIFO from FIFO: Reorder on push.
• Queues: FIFO structure.
• Trade-off: Push vs. pop cost.

Additional Example

push(1), push(2), pop(), push(3):

• Two Queues: q1=[3,1].
• Single Queue: q=[3,1].

Edge Cases

• Empty: true.
• Single element: Works fine.
• Max calls: Within constraints.

Both handle these well.

Final Thoughts

LeetCode 225: Implement Stack using Queues in Python is a creative data structure challenge. Two Queues with Push Cost offers a balanced approach, while Single Queue minimizes space. Want more? Try LeetCode 232: Implement Queue using Stacks or LeetCode 20: Valid Parentheses. Test your skills—Solve LeetCode 225 on LeetCode with push(1), push(2), top() (expecting 2)—stack it up today!