Implement Stack using Queue
Implement LIFO push/pop/top using only queue operations.
02
Intuition
A queue gives you the oldest element; a stack wants the newest. Trick: after enqueuing a new element, rotate the whole queue behind it — dequeue and re-enqueue everything that was there before. The queue's front is then always the stack's top.
03
Approach
1
Make push expensive, pop free
On push, enqueue x then rotate the previous n elements to the back. Front = newest = top.
2
Pop and top are trivial
Both just read/remove the queue's front — O(1).
3
One queue suffices
The rotation happens in-place in the same queue; the classic two-queue version does the same dance with a spare.
04
Solution & live demo
python
▶1from collections import deque
▶2
▶3class MyStack:
▶4 def __init__(self):
▶5 self.q = deque()
▶6
▶7 def push(self, x):
▶8 self.q.append(x)
▶9 for _ in range(len(self.q) - 1): # rotate old elements behind x
▶10 self.q.append(self.q.popleft())
▶11
▶12 def pop(self): return self.q.popleft()
▶13 def top(self): return self.q[0]
▶14 def empty(self): return not self.q
05
Edge cases
push on empty
Rotation of 0 elements — just enqueue.
Alternating push/pop
Invariant (front = newest) is restored by every push, so pops always correct.
06
Complexity
Time
O(n) push, O(1) pop/top
Space
O(n)
Rotation cost paid on push.