LeetCode 232: Implement Queue using Stacks Solution in Python – A Step-by-Step Guide

What Is LeetCode 232: Implement Queue using Stacks?

In LeetCode 232: Implement Queue using Stacks, you need to implement a MyQueue class with:

• push(x): Adds x to the back of the queue.
• pop(): Removes and returns the front element.
• peek(): Returns the front element without removing it.
• empty(): Returns True if the queue is empty, False otherwise.
• Constraint: Use only stack operations (push to top, pop from top, peek top, check empty).

This is a flip of LeetCode 225: Implement Stack using Queues, focusing on queue behavior with stacks.

Problem Statement

• Goal: Simulate a queue using stacks.
• Operations: Standard queue methods via stack primitives.

Constraints

• Number of calls: 1 to 100.
• Values: 1 to 9.
• All operations are valid (e.g., no pop on empty queue).

Examples

• Sequence:

MyQueue queue = new MyQueue(); queue.push(1); // Queue: [1] queue.push(2); // Queue: [1,2] queue.peek(); // Returns 1 queue.pop(); // Returns 1, Queue: [2] queue.empty(); // Returns False

Understanding the Problem: Queue from Stacks

To solve LeetCode 232: Implement Queue using Stacks in Python, we need to transform a stack’s LIFO (last-in-first-out) behavior into a queue’s FIFO (first-in-first-out) order. This isn’t about number properties like LeetCode 231: Power of Two—it’s a data structure puzzle. A queue’s front is the oldest element, while a stack’s top is the newest. We’ll use two stacks to reorder elements and explore two approaches: 1. Best Solution (Two Stacks, Amortized O(1) Push): O(1) amortized push, O(n) pop—optimized for frequent pushes. 2. Alternative Solution (Two Stacks, Costly Pop): O(n) push, O(1) pop—optimized for frequent pops.

Let’s dive into the best solution.

Best Solution: Two-Stack Approach with Amortized O(1) Push

Why This Is the Best Solution

The two-stack approach with amortized O(1) push is our top choice for LeetCode 232 because it keeps push operations fast and efficient in most scenarios, with pop operations amortized over time. It’s practical, elegant, and suits typical queue usage where pushes often outnumber pops.

How It Works

• Use two stacks:
• in_stack: For pushing new elements (top is newest).
• out_stack: For popping/peeking (top is oldest).
• Push: Add to in_stack (O(1)).
• Pop/Peek: If out_stack is empty, move all from in_stack to out_stack (reversing order), then pop/peek from out_stack (O(1) amortized).
• Empty: Check if both stacks are empty.

Step-by-Step Example

Example 1: Operations Sequence

• Sequence: push(1), push(2), peek(), pop(), empty().
• Process:
• push(1): in_stack = [1], out_stack = [].
• push(2): in_stack = [1,2], out_stack = [].
• peek(): out_stack empty, move in_stack to out_stack → out_stack = [2,1] (reversed), in_stack = []. Peek top: 1.
• pop(): Pop from out_stack → 1, out_stack = [2].
• empty(): in_stack = [], out_stack = [2], not empty, return False.
• Result: Queue behaves as [2].

Example 2: push(1), pop()

• push(1): in_stack = [1].
• pop(): Move to out_stack = [1], pop 1, out_stack = [].

Code with Detailed Line-by-Line Explanation

Here’s the Python implementation:

Copy codeclass MyQueue:
    def __init__(self):
        # Line 1: Initialize two stacks
        self.in_stack = []  # For incoming elements
        self.out_stack = []  # For outgoing elements

    def push(self, x: int) -> None:
        # Line 2: Add to in_stack
        self.in_stack.append(x)  # O(1), e.g., [1,2]

    def pop(self) -> int:
        # Line 3: Ensure out_stack has elements
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())  # Reverse order
        # Line 4: Pop from out_stack
        return self.out_stack.pop()  # O(1) after transfer

    def peek(self) -> int:
        # Line 5: Ensure out_stack has elements
        if not self.out_stack:
            while self.in_stack:
                self.out_stack.append(self.in_stack.pop())
        # Line 6: Peek top of out_stack
        return self.out_stack[-1]  # O(1) after transfer

    def empty(self) -> bool:
        # Line 7: Check both stacks
        return not self.in_stack and not self.out_stack  # O(1)

• Time Complexity:
• Push: O(1).
• Pop/Peek: O(n) worst-case, O(1) amortized.
• Space Complexity: O(n) – total elements across stacks.

Alternative Solution: Two-Stack Approach with Costly Pop

Why an Alternative Approach?

The two-stack approach with costly pop shifts the heavy lifting to the push operation, making pop and peek O(1). It’s a solid alternative if your use case involves more frequent pops than pushes, offering a different trade-off.

How It Works

• Use two stacks:
• s1: Temporary stack for new elements.
• s2: Main stack with queue order (top is front).
• Push: Move all from s2 to s1, add new element to s1, move back to s2.
• Pop/Peek: Directly use s2.
• Empty: Check s2.

Step-by-Step Example

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

• push(1): s1 = [1], move to s2 = [1], s1 = [].
• push(2): s1 = [1], s1 = [1,2], move to s2 = [1,2], s1 = [].
• pop(): s2 = [2], return 1.

Code for Costly Pop Approach

Copy codeclass MyQueue:
    def __init__(self):
        self.s1 = []  # Temp stack
        self.s2 = []  # Main queue stack

    def push(self, x: int) -> None:
        # Line 1: Move s2 to s1
        while self.s2:
            self.s1.append(self.s2.pop())
        # Line 2: Add new element
        self.s1.append(x)
        # Line 3: Move back to s2
        while self.s1:
            self.s2.append(self.s1.pop())

    def pop(self) -> int:
        # Line 4: Pop from s2
        return self.s2.pop()

    def peek(self) -> int:
        # Line 5: Peek s2
        return self.s2[-1]

    def empty(self) -> bool:
        # Line 6: Check s2
        return not self.s2

• Time Complexity:
• Push: O(n).
• Pop/Peek: O(1).
• Space Complexity: O(n).

Comparing the Two Solutions

• Best Solution (Amortized O(1) Push):
• Pros: Fast push, amortized O(1) operations.
• Cons: Pop can be O(n) occasionally.
• Alternative Solution (Costly Pop):
• Pros: O(1) pop/peek, simple retrieval.
• Cons: O(n) push.

The amortized O(1) push method is our best for typical queue usage.

Additional Examples and Edge Cases

Single Element

• push(1), pop(): Both return 1, empty afterward.

Multiple Pushes

• push(1), push(2), push(3): Queue as [1,2,3].
• Both maintain order.

Empty Queue

• empty(): True initially, both handle correctly.

Complexity Breakdown

• Amortized O(1) Push:
• Push: O(1).
• Pop/Peek: O(1) amortized, O(n) worst.
• Space: O(n).
• Costly Pop:
• Push: O(n).
• Pop/Peek: O(1).
• Space: O(n).

Best solution optimizes frequent pushes.

Key Takeaways for Beginners

• Queue from Stacks: Reorder LIFO to FIFO.
• Two Stacks: Shift work between push and pop.
• Amortization: Balances cost over operations.
• Python Tip: Lists as stacks—learn more at [Python Basics](/python/basics).

Final Thoughts: Queue Up with Stacks

LeetCode 232: Implement Queue using Stacks in Python is a fun twist on data structures. The amortized O(1) push solution excels in efficiency, while the costly pop approach simplifies retrieval. Want more stack fun? Try LeetCode 225: Implement Stack using Queues or LeetCode 20: Valid Parentheses. Ready to queue? Visit Solve LeetCode 232 on LeetCode and stack it up today!