Implementing a Stack Using Two Queues

Problem Description

The task is to implement a Last-In-First-Out (LIFO) stack data structure using only two queues. The implemented stack should support the standard stack operations: push, pop, top, and empty. We are restricted to using only standard queue operations: push to back, peek/pop from front, size, and is empty.

Naive Approach

A naive approach is not distinctly different from the optimal one in this case, given the constraints.

Optimal Approach

The key idea is to use two queues, let's call them q1 and q2. When pushing an element onto the stack, we always add it to q1. When we need to perform a pop or top operation, we transfer all elements from q1 to q2 except for the last element, which will be the top of the stack. Then we return (or pop) that last element. After this operation, we swap the names of q1 and q2 so that q1 is always the queue to which we add new elements.

Detailed Steps:

1. Push(x): Add element x to q1.
2. Pop():
   • Move all elements from q1 to q2 except the last element.
   • Remove and return the last element from q1 (which is the top of the stack).
   • Swap q1 and q2.
3. Top():
   • Move all elements from q1 to q2 except the last element.
   • Return the last element from q1 (which is the top of the stack).
   • Move the last element from q1 to q2.
   • Swap q1 and q2.
4. Empty(): Return true if q1 is empty.

Example:

push(1)
push(2)
top()   // returns 2
pop()   // returns 2
empty() // returns false

Code Implementation (Python)

class MyStack:
    def __init__(self):
        self.q1 = []
        self.q2 = []

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

    def pop(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.pop(0))
        top = self.q1.pop(0)
        self.q1, self.q2 = self.q2, self.q1
        return top

    def top(self) -> int:
        while len(self.q1) > 1:
            self.q2.append(self.q1.pop(0))
        top = self.q1[0]
        self.q2.append(self.q1.pop(0))
        self.q1, self.q2 = self.q2, self.q1
        return top

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

Time Complexity

• push(x): O(1)
• pop(): O(n), where n is the number of elements in the stack.
• top(): O(n), where n is the number of elements in the stack.
• empty(): O(1)

Space Complexity

O(n), where n is the maximum number of elements in the stack, because we are using two queues to store the elements.

Edge Cases

• Empty Stack: When pop() or top() are called on an empty stack, the problem statement says that the calls are valid which means the empty stack scenario does not need to be handled.

Follow-up: Implementation Using One Queue

We can implement the stack using a single queue. For the push operation, we enqueue the element and then rotate the queue so that the newly added element becomes the front of the queue. This ensures LIFO behavior.

Detailed Steps:

1. Push(x):
   • Enqueue element x to the queue.
   • Rotate the queue size - 1 times by dequeuing from the front and enqueuing to the back.
2. Pop(): Dequeue and return the front element.
3. Top(): Return the front element.
4. Empty(): Return true if the queue is empty.

Code Implementation (Python):

class MyStack:
    def __init__(self):
        self.q = []

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

    def pop(self) -> int:
        return self.q.pop(0)

    def top(self) -> int:
        return self.q[0]

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

Time Complexity (Single Queue)

• push(x): O(n), where n is the number of elements in the stack.
• pop(): O(1)
• top(): O(1)
• empty(): O(1)

Space Complexity (Single Queue)

O(n), where n is the maximum number of elements in the stack, as we are using a single queue to store the elements.