LeetCode 232 Implement Queue using Stacks - by using two stacks (Easy, Java)

232. Implement Queue using Stacks To implement a queue (FIFO) using two stacks, we need to simulate the first-in-first-out behavior. The key idea is to use one stack (stack1) for pushing elements and another stack (stack2) for popping/peeking. When we need to pop() or peek(), we transfer all elements from stack1 to stack2 if stack2 is empty, which reverses their order and allows us to access the front of the queue.

Approach

1. Push Operation (push(int x)):

   • Simply push the element onto stack1. This stack holds elements in the order they were pushed, but in reverse (LIFO) order.

2. Pop Operation (pop()):

   • If stack2 is empty, transfer all elements from stack1 to stack2. This reverses their order, so the oldest element (front of the queue) is now at the top of stack2.
   • Pop and return the top element from stack2.

3. Peek Operation (peek()):

   • Similar to pop(), but we just return the top element of stack2 without removing it.

4. Empty Check (empty()):

   • Return true if both stacks are empty, otherwise false.

Solution Code

import java.util.Stack;

class MyQueue {
    private Stack<Integer> stack1; // For push operations
    private Stack<Integer> stack2; // For pop/peek operations

    public MyQueue() {
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    public void push(int x) {
        stack1.push(x);
    }

    public int pop() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.pop();
    }

    public int peek() {
        if (stack2.isEmpty()) {
            while (!stack1.isEmpty()) {
                stack2.push(stack1.pop());
            }
        }
        return stack2.peek();
    }

    public boolean empty() {
        return stack1.isEmpty() && stack2.isEmpty();
    }
}

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

Explanation

• Push Operation: Elements are always pushed onto stack1. This maintains the order of insertion in a LIFO manner.
• Pop/Peek Operations: If stack2 is empty, all elements from stack1 are moved to stack2, reversing their order. This ensures the oldest element (front of the queue) is at the top of stack2, allowing us to perform pop() or peek() in O(1) time (amortized).
• Empty Check: The queue is empty only if both stacks are empty.

Time Complexity

• Push: O(1) since we just push onto stack1.
• Pop/Peek: Amortized O(1). In the worst case (when stack2 is empty), it takes O(n) time to transfer all elements from stack1 to stack2. However, each element is only moved once, so over n operations, the average time per operation is O(1).
• Empty: O(1) as it only checks if both stacks are empty.

This approach efficiently simulates a queue using two stacks while maintaining amortized constant time complexity for each operation.