LeetCode #225 Medium

Implement Stack using Queue

Implement LIFO push/pop/top using only queue operations.

stackqueuedesign

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.

How to spot this pattern

Design problems like this are about where you pay. A queue gives FIFO; you need LIFO. You can either make push expensive (rotate the new element to the front) or pop expensive — but not both cheap. Deciding which operation absorbs the cost, and defending that choice, is the actual interview question.

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

▶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

Common pitfalls

Rotating the wrong number of times

✗ Wrong

for _ in range(len(self.q)):
    self.q.append(self.q.popleft())

✓ Right

for _ in range(len(self.q) - 1):
    self.q.append(self.q.popleft())

A full rotation returns the queue to its original order, leaving the new element at the back — exactly what you were trying to avoid. Rotating one fewer time stops with the newest element at the front.

Reading the length inside the loop

✗ Wrong

i = 0
while i < len(self.q) - 1:
    self.q.append(self.q.popleft()); i += 1

✓ Right

for _ in range(len(self.q) - 1):

Each iteration pops and pushes, so the length never changes and the bound stays satisfied — the loop spins forever. Capture the count once, before the rotation starts.

Using two queues when one suffices

✗ Wrong

self.q1, self.q2 = deque(), deque()
# shuffle between them on every push

✓ Right

self.q = deque()
# rotate in place

The two-queue version is the textbook answer but moves the same elements between containers for no gain. Rotating a single queue is the same complexity with half the state to keep consistent.

06

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.

07

Complexity

Time

O(n) push, O(1) pop/top

Space

O(n)

Rotation cost paid on push.