Implement Stack Using Queues — Single Queue Rotation
Sanjeev SharmaAdvertisement
Problem 252 · Implement Stack Using Queues
Difficulty: Easy · Pattern: Queue Rotation Trick
Intuition
After pushing x, rotate all previous elements to the back. The new element is now at the front (LIFO).
Solutions
# Python — one queue
from collections import deque
class MyStack:
def __init__(self): self.q = deque()
def push(self, x):
self.q.append(x)
for _ in range(len(self.q)-1):
self.q.append(self.q.popleft())
def pop(self): return self.q.popleft()
def top(self): return self.q[0]
def empty(self): return not self.q
// Java — one queue
class MyStack {
Queue<Integer> q = new LinkedList<>();
public void push(int x) {
q.offer(x);
for (int i = 1; i < q.size(); i++) q.offer(q.poll());
}
public int pop() { return q.poll(); }
public int top() { return q.peek(); }
public boolean empty() { return q.isEmpty(); }
}
Complexity
- push: O(n)
- pop/top/empty: O(1)
Advertisement
