Implement Queue using Stacks

leetcode.com

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

Very expensive.

Moving Towards the Optimal Approach

Use:

st1 → Incoming Elements

st2 → Outgoing Elements

Whenever:

st2 becomes empty

Move everything from:

st1 → st2

This reverses order automatically.

Pattern Recognition

Queue
+
Stack

=> Two Stack Reversal

Key Observation

Input:

1 2 3 4

Stored:

st1

4
3
2
1

Transfer:

st2

1
2
3
4

Now Queue order appears.

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)

Stacks:

st1

3
2
1

Need dequeue.

Transfer:

st2

1
2
3

Pop:

1 removed

Queue order maintained.

Complexity Analysis

Interview One-Liner

Use one stack for insertion and another for removal. Transfer only when the output stack becomes empty.

Pattern Learned

Stack Using Queue
→ Rotation

Queue Using Stack
→ Reversal

Stack Using Array
→ Top Pointer

Queue Using Array
→ Front/Rear Management