Implement Stack using Queue (using single queue)

leetcode.com

Problem Statement

Implement a Stack using only Queue operations.

Support:

push()
pop()
top()
empty()

Brute Force Intuition

Use two queues.

Push into first queue.

During pop:

Move n-1 elements

to second queue.

Remove last element.

Works but push becomes easy and pop expensive.

Moving Towards the Optimal Approach

Can we use:

Only One Queue ?

Yes.

Whenever a new element arrives:

queue.add(x)

Rotate all older elements behind it.

This makes newest element appear at front.

Pattern Recognition

Stack
+
Queue

=> Rotation Trick

Key Observation

After inserting:

1
2
3

Queue becomes:

3 2 1

Front always behaves like Stack top.

Optimal Java Solution

class MyStack {

    Queue<Integer> mainQ;

    public MyStack() {

        mainQ = new ArrayDeque<>();
    }

    public void push(int x) {

        int size = mainQ.size();

        mainQ.add(x);

        for (int i = 0; i < size; i++) {

            int rem = mainQ.remove();

            mainQ.add(rem);
        }
    }

    public int pop() {

        if (!empty())
            return mainQ.poll();

        return -1;
    }

    public int top() {

        if (!empty())
            return mainQ.peek();

        return -1;
    }

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

Dry Run

push(1)

Queue:
1



push(2)

Queue:

2 1



push(3)

Queue:

3 2 1

Top:

3

Pop:

3 removed

Complexity Analysis

Interview One-Liner

Insert element and rotate the queue so the newest element always stays at the front.