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
| Operation | Complexity |
|---|---|
| Push | O(N) |
| Pop | O(1) |
| Top | O(1) |
Interview One-Liner
Insert element and rotate the queue so the newest element always stays at the front.