Problem Statement

Implement a Queue using Stack operations only.

Support:

push()
pop()
peek()
empty()

Brute Force Intuition

Use one stack.

For dequeue:

Reverse stack
Remove front
Reverse again

This approach is very expensive.

Moving Towards the Optimal Approach

Use two stacks:

st1 → Incoming Elements
st2 → Outgoing Elements

Whenever st2 becomes empty, move everything from st1 to st2. This reverses the order automatically.

Pattern Recognition

Queue
+
Stack

=> Two Stack Reversal

Key Observation

Input:

1 2 3 4

Stored in st1 (top to bottom):

4
3
2
1

After transfer to st2 (top to bottom):

1
2
3
4

Now queue order appears — the first element pushed is at the top of st2, ready to be popped first.

Optimal Java Solution

class MyQueue {

    Stack<Integer> st1;
    Stack<Integer> st2;

    public MyQueue() {
        st1 = new Stack<>();
        st2 = new Stack<>();
    }

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

    private void transfer() {
        if (st2.isEmpty()) {
            while (!st1.isEmpty()) {
                st2.push(st1.pop());
            }
        }
    }

    public int pop() {
        transfer();
        return st2.pop();
    }

    public int peek() {
        transfer();
        return st2.peek();
    }

    public boolean empty() {
        return st1.isEmpty() && st2.isEmpty();
    }
}

Dry Run

push(1)
push(2)
push(3)

State of st1 (top to bottom):

3
2
1

On dequeue, transfer to st2 (top to bottom):

1
2
3

Calling pop() now returns 1, which is the correct front-of-queue element, confirming that the two-stack reversal produces proper FIFO behavior.