Implement Stack using Queues

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.

For example:

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

Can you implement the stack using only one queue?

## Implementing a Stack using Two Queues

This problem challenges us to implement a stack data structure, which follows the Last-In-First-Out (LIFO) principle, using only two queues. This means we can only use the standard queue operations: `push to back`, `peek/pop from front`, `size`, and `is empty`.

### 1. Naive Approach (Inefficient `push`)

One way to implement this is to use one queue (`q1`) for storing the stack elements and another queue (`q2`) as a temporary buffer during the `push` operation.  The `push` operation becomes less efficient in this approach.

**Code (Python):**

```python
class MyStack:
    def __init__(self):
        self.q1 = []  # Main queue
        self.q2 = []  # Temporary queue

    def push(self, x: int) -> None:
        # Move all elements from q1 to q2
        while self.q1:
            self.q2.append(self.q1.pop(0))

        # Add the new element to q1
        self.q1.append(x)

        # Move all elements back from q2 to q1
        while self.q2:
            self.q1.append(self.q2.pop(0))

    def pop(self) -> int:
        if self.q1:
            return self.q1.pop(0)
        else:
            return None  # Or raise an exception

    def top(self) -> int:
        if self.q1:
            return self.q1[0]
        else:
            return None  # Or raise an exception

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

Explanation:

• push(x): This is the least efficient operation. We move all elements from q1 to q2, add the new element x to q1, and then move everything back from q2 to q1. This ensures that the latest element is always at the front of q1.
• pop(): We simply remove and return the element at the front of q1.
• top(): We return the element at the front of q1 without removing it.
• empty(): We check if q1 is empty.

2. Optimal Approach (Efficient push)

A more efficient approach is to make the push operation O(1) and the pop operation O(n). We maintain the stack elements in q1. When pushing a new element, we simply enqueue it to q1. When popping, we move all elements from q1 to q2 except the last one (which is the top of the stack), then we swap the names of q1 and q2 so that q1 becomes the queue with the remaining elements.

Code (Python):

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

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

    def pop(self) -> int:
        if not self.q1:  # Handle empty stack
            return None

        # Move all elements except the last one to q2
        while len(self.q1) > 1:
            self.q2.append(self.q1.pop(0))

        # The last element in q1 is the top
        top = self.q1.pop(0)

        # Swap q1 and q2 so q2 becomes q1 for next operations
        self.q1, self.q2 = self.q2, self.q1

        return top

    def top(self) -> int:
        # Optimized top to use pop and push.
        top = self.pop()
        if top is not None:
            self.push(top)
        return top

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

Explanation:

• push(x): We simply add the new element to the rear of q1. This is O(1).
• pop(): We move all elements except the last one from q1 to q2. The last element is the top of the stack, so we remove and return it. Then, we swap q1 and q2 to maintain the invariant. This is O(n).
• top(): To get the top, call pop, store the value, push it back and then return. This utilizes existing functions and maintains stack properties.
• empty(): We check if q1 is empty.

3. Big O Runtime Analysis

• push(x): O(1) - Constant time because we simply enqueue to q1.
• pop(): O(n) - Linear time because we have to move n-1 elements from q1 to q2.
• top(): O(n) - Linear time because it calls pop, which is O(n), and push, which is O(1), but pop dominates.
• empty(): O(1) - Constant time to check if the queue is empty.

4. Big O Space Usage Analysis

• O(n) - We use two queues, but in the worst-case scenario, one queue can hold up to n elements, where n is the number of elements in the stack. Therefore, the space complexity is O(n).

5. Edge Cases

• Empty Stack: Handle cases where pop() or top() are called on an empty stack. The code includes a check for if not self.q1: in pop() and top() and returns None. Alternatively, you could raise an exception.
• Pushing Null/None: Decide how to handle push(None). You could either allow it (treating None as a valid value) or raise an exception.
• Integer Overflow: If the stack is intended to hold a very large number of integers and memory is a concern, consider using a more memory-efficient data type, if applicable in the language. However, the problem statement specifies 1 <= x <= 9, so this is not a concern here.

Follow-up: Implementing a Stack using Only One Queue

Yes, it's possible to implement a stack using only one queue. The key is to, during the push operation, enqueue the new element and then move all the existing elements to the back of the queue. This effectively puts the new element at the front of the queue, simulating the stack's LIFO behavior.

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:
        if self.q:
            return self.q.pop(0)
        else:
            return None

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

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

In this single queue implementation:

• push(x): O(n), as we need to rotate the elements after adding the new element.
• pop(): O(1), as we remove from the front.
• top(): O(1), as we peek at the front.
• empty(): O(1).

Space complexity is O(n).