LeetCode 225: Implement Stack using Queues

Explanation

To implement a stack using two queues, we can use the following approach:

• Use two queues, queue1 and queue2, where queue1 will be the main queue for storing elements in the stack.
• For push operation, we always add the new element to the empty queue2, then move all elements from queue1 to queue2, and finally swap the names of queue1 and queue2.
• For pop operation, we simply remove and return the front element from queue1.
• For top operation, we return the front element from queue1.
• For empty operation, we check if queue1 is empty.

This approach allows us to maintain the stack properties using two queues efficiently.

Time Complexity:

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

Space Complexity:

• O(n) where n is the number of elements in the stack.

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

class MyStack {
    private Queue<Integer> queue1;
    private Queue<Integer> queue2;

    public MyStack() {
        queue1 = new LinkedList<>();
        queue2 = new LinkedList<>();
    }

    public void push(int x) {
        queue2.offer(x);
        while (!queue1.isEmpty()) {
            queue2.offer(queue1.poll());
        }
        Queue<Integer> temp = queue1;
        queue1 = queue2;
        queue2 = temp;
    }

    public int pop() {
        return queue1.poll();
    }

    public int top() {
        return queue1.peek();
    }

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