LeetCode Link: 225. Implement Stack using Queues

Problem Definition

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

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.

Approach

This problem is more about understanding the properties of stacks and queues rather than its direct application. Here, we need to reverse the first-in-first-out (FIFO) nature of a queue to mimic the last-in-first-out (LIFO) behavior of a stack.

Using Two Queues

We can use two queues to implement a stack. The idea is as follows:

  1. Use one queue (queue1) as the main storage for elements.
  2. Use another queue (queue2) as a temporary backup.
  3. When performing a pop or top operation, transfer all elements from queue1 to queue2 except the last one. This ensures the last element in queue1 mimics the top of the stack.
  4. Swap queue1 and queue2 to maintain the stack behavior.

This method has a time complexity of O(n) for pop and top operations.

Optimized Solution: Single Queue

Using a single queue, we can simulate stack behavior by rotating the elements within the queue itself:

  1. During the push operation, enqueue the element normally.
  2. Rotate the queue so that the newly added element comes to the front, maintaining the stack's LIFO order.
  3. For pop and top, the front element of the queue will directly represent the top of the stack.

This method reduces space usage and simplifies implementation.

Solution 1 - Using Two Queues

from collections import deque


class MyStack:

    def __init__(self):
        self.queue1 = deque()
        self.queue2 = deque()

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

    def pop(self) -> int:
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        result = self.queue1.popleft()
        self.queue1, self.queue2 = self.queue2, self.queue1
        return result

    def top(self) -> int:
        while len(self.queue1) > 1:
            self.queue2.append(self.queue1.popleft())
        result = self.queue1.popleft()
        self.queue2.append(result)
        self.queue1, self.queue2 = self.queue2, self.queue1
        return result

    def empty(self) -> bool:
        return not self.queue1

Solution 2 - Using a Single Queue (Optimized)

class MyStack:

    def __init__(self):
        self.queue = deque()

    def push(self, x: int) -> None:
        self.queue.append(x)
        for _ in range(len(self.queue) - 1):
            self.queue.append(self.queue.popleft())

    def pop(self) -> int:
        return self.queue.popleft() if not self.empty() else None

    def top(self) -> int:
        return self.queue[0] if not self.empty() else None

    def empty(self) -> bool:
        return not self.queue

Complexity Analysis

Two-Queue Solution

  • Time Complexity:
    • push: O(1)
    • pop and top: O(n) (due to transferring elements between queues)
  • Space Complexity: O(n) (for two queues)

Single-Queue Solution (Optimized)

  • Time Complexity:
    • push: O(n) (due to reordering elements after each push)
    • pop and top: O(1)
  • Space Complexity: O(n) (for the single queue)

Conclusion

The single-queue approach is more space-efficient and has a simpler implementation compared to the two-queue approach. However, it comes with the trade-off of increased time complexity for the push operation. Understanding both approaches is valuable as they demonstrate different problem-solving techniques for simulating one data structure using another.