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

What is the time and space complexity of your solution? Can you implement the stack using only one queue?

## Implementing a Stack using Two Queues

This problem requires us to simulate a stack's behavior (LIFO) using only the standard operations of queues (FIFO). We'll use two queues to achieve this.

### Naive Approach

A straightforward, though not optimal, approach could involve using one queue as the primary storage and the other as a temporary buffer during pop operations.  However, this might lead to inefficiency in certain scenarios.

### Optimal Approach

We can use two queues, `q1` and `q2`. The `push` operation will add the new element to `q1`. The `pop` operation will transfer all elements from `q1` to `q2` except the last element, which will be the top of the stack. Then we swap the names of `q1` and `q2` so `q1` always holds the stack elements.

```java
import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();

    public MyStack() {

    }

    public void push(int x) {
        q1.offer(x);
    }

    public int pop() {
        if (empty()) return -1; // Or throw exception
        // Move all elements from q1 to q2 except the last one
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }
        int top = q1.poll(); // The last element in q1 is the top

        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;

        return top;
    }

    public int top() {
        if (empty()) return -1; // Or throw exception

        // Move all elements from q1 to q2 except the last one
        while (q1.size() > 1) {
            q2.offer(q1.poll());
        }

        int top = q1.peek(); // The last element in q1 is the top
        q2.offer(q1.poll()); // Move top element to q2

        // Swap q1 and q2
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;

        return top;
    }

    public boolean empty() {
        return q1.isEmpty();
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */

Big(O) Run-time Analysis

• push(x): O(1) - Adding an element to the queue takes constant time.
• pop(): O(n) - Moving n-1 elements from q1 to q2.
• top(): O(n) - Moving n-1 elements from q1 to q2 to find the top element.
• empty(): O(1) - Checking if a queue is empty takes constant time.

Big(O) Space Usage Analysis

• O(n) - In the worst-case scenario, the stack can contain n elements, all stored in one of the queues. The other queue is used only as temporary storage during pop and top operations and does not increase the overall space complexity.

Edge Cases

• Empty Stack: Handle cases where pop() or top() are called on an empty stack. The code includes a check for empty() and returns -1 (or you could throw an exception).
• Pushing Null: The code assumes valid integer inputs. You might want to add checks to handle null values or other invalid inputs, depending on the problem's requirements.

Follow-up: Implementing Stack with One Queue

Yes, it's possible to implement a stack using a single queue. The idea is to, for every push operation, add the new element to the queue and then move all the existing elements to the back of the queue, effectively making the newly added element the front of the queue, which behaves like the top of the stack.

import java.util.LinkedList;
import java.util.Queue;

class MyStack {
    private Queue<Integer> q = new LinkedList<>();

    public MyStack() {

    }

    public void push(int x) {
        q.offer(x);
        int size = q.size();
        for (int i = 1; i < size; i++) {
            q.offer(q.poll());
        }
    }

    public int pop() {
        if (empty()) return -1;
        return q.poll();
    }

    public int top() {
        if (empty()) return -1;
        return q.peek();
    }

    public boolean empty() {
        return q.isEmpty();
    }
}

• push(x): O(n) - We need to move all existing elements to the back of the queue after adding a new element.

• pop(): O(1) - Removing the front element takes constant time.

• top(): O(1) - Peeking at the front element takes constant time.

• empty(): O(1) - Checking if a queue is empty takes constant time.

• Space complexity is O(n) as the stack can hold up to n elements in the queue.