Implement Stack using Queues | Leetcode 225 | Complete Python Code

Implement a last-in-first-out (LIFO) stack using only two queues. The implemented stack should support all the functions of a normal stack (push, top, pop, and empty).

Implement the MyStack class:

• void push(int x) Pushes element x to the top of the stack.
• int pop() Removes the element on the top of the stack and returns it.
• int top() Returns the element on the top of the stack.
• boolean empty() Returns true if the stack is empty, false otherwise.

Notes:

• You must use only standard operations of a queue, which means that only push to back, peek/pop from front, size and is empty operations are valid.
• Depending on your language, the queue may not be supported natively. You may simulate a queue using a list or deque (double-ended queue) as long as you use only a queue’s standard operations.

Example 1:

Input
["MyStack", "push", "push", "top", "pop", "empty"]
[[], [1], [2], [], [], []]

Output
[null, null, null, 2, 2, false]

Explanation
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // return 2
myStack.pop(); // return 2
myStack.empty(); // return False

Constraints:

• 1 <= x <= 9
• At most 100 calls will be made to push, pop, top, and empty.
• All the calls to pop and top are valid.

Follow-up: Can you implement the stack using only one queue?

Solution 1: Normal Approach (Using Two Queues)

Intuition

Use two queues to mimic stack behavior. One queue holds the main elements, and the other helps reverse the order during push. When pushing a new element, we add it to the empty queue, then move all elements from the main queue to this new one. This puts the new element at the front, simulating “top” of stack. It’s like pouring items from one line to another to put the newest at the front!

Detailed Approach

1. Initialization: Create two queues (q1 and q2) using deque.
2. Push(x):
   • Add x to q2 (temporary queue).
   • Move all elements from q1 to q2 (reverses order, new x becomes front after swap).
   • Swap q1 and q2 (now q1 has new x at front).
3. Pop(): Remove and return front of q1.
4. Top(): Return front of q1 without removing.
5. Empty(): Check if q1 is empty.
6. Why Normal?: Easy to understand, but push is O(n) due to moving elements. Pop/top are O(1).

Code

from collections import deque

class MyStack:
    def __init__(self):
        self.q1 = deque()  # Main queue
        self.q2 = deque()  # Helper queue
    
    def push(self, x: int) -> None:
        self.q2.append(x)  # Add new element to helper
        # Move all from main to helper
        while self.q1:
            self.q2.append(self.q1.popleft())
        # Swap: helper becomes main
        self.q1, self.q2 = self.q2, self.q1
    
    def pop(self) -> int:
        return self.q1.popleft()  # Remove front (top of stack)
    
    def top(self) -> int:
        return self.q1[0]  # Peek front
    
    def empty(self) -> bool:
        return len(self.q1) == 0  # Check if main is empty

Code Explanation

We maintain q1 as the “stack” where the front is the top. During push, we use q2 to temporarily hold the new element, then pour q1 into q2 (which puts old elements behind the new one). Swapping makes q1 the updated queue with new top at front. Pop and top directly use q1’s front (O(1)). Empty checks q1’s length.

Time and Space Complexity

• push(): O(n) – Moving n elements
• pop(): O(1)
• top(): O(1)
• empty(): O(1)
• Space: O(n) – Two queues holding up to n elements

Simplifying It

This is like having two lines: you add the new person to an empty line, then make everyone from the main line join behind them. Now the new person is first in line (top of stack). Simple but involves moving people each time you add someone!

Solution 2: Optimal Approach (Using One Queue with Rotation)

Intuition

Use just one queue and “rotate” it during push to bring the new element to the front. After adding the new element to the end, we remove and re-add the front elements (n-1 times) to move them behind the new one. This makes the new element the front (top of stack). It’s like spinning a line of people so the newest joins at the end but then we cycle the others to put the new one first!

Detailed Approach

1. Initialization: Create one queue using deque.
2. Push(x):
   • Add x to the end.
   • Rotate: For (size-1) times, remove front and add to end (moves old elements behind new x).
3. Pop(): Remove and return front.
4. Top(): Return front without removing.
5. Empty(): Check if queue is empty.
6. Why Optimal?: Uses only one queue (less space), push is O(n), pop/top O(1). Good for space-constrained scenarios.

Code

from collections import deque

class MyStack:
    def __init__(self):
        self.queue = deque()  # Single queue
    
    def push(self, x: int) -> None:
        self.queue.append(x)  # Add to end
        # Rotate: move front elements to end (len-1 times)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())
    
    def pop(self) -> int:
        return self.queue.popleft()  # Remove front (top)
    
    def top(self) -> int:
        return self.queue[0]  # Peek front
    
    def empty(self) -> bool:
        return len(self.queue) == 0  # Check if empty

Code Explanation

The single queue stores elements with front as top. Push adds x to end, then rotates by popping front and appending to end (len-1 times), which cycles old elements behind x, making x the new front. Pop and top use the front directly (O(1)). Empty checks length.

Time and Space Complexity

• push(): O(n) – Rotating n-1 elements
• pop(): O(1)
• top(): O(1)
• empty(): O(1)
• Space: O(n) – Single queue

Simplifying It

This is like a single line where you add the new person at the end, then have everyone in front step to the back one by one until the new person is first. No extra line needed, but still involves moving people when adding!

Summary

Both approaches achieve stack behavior using queues, with O(n) time for push and O(1) for pop/top. The optimal (one queue) saves space by avoiding a second queue and is often preferred in interviews to show optimization. If pops are more frequent than pushes, these are good (since pop is fast).

Key Takeaways

• Stacks (LIFO) can be made from queues (FIFO) by reversing order during operations.
• Tradeoff: Make push slow (O(n)) to keep pop fast (O(1)), or vice versa.
• In interviews, explain why you chose one vs. two queues (space vs. simplicity).
• Practice: Try implementing the reverse (queue using stacks) or add more methods like size!

This should make implementing stack with queues clear and easy to remember!

For any changes to the article, kindly email at code@codeanddebug.in or contact us at +91-9712928220.