Implement Stack using Queue
Implement Stack Using Queues: implement LIFO push/pop/top using only queue operations.
- 1 <= x <= 9
- At most 100 calls will be made to push, pop, top, and empty.
- All the calls to pop and top are valid.
Intuition
To implement stack using queues you must produce LIFO behaviour from a structure that only ever hands back its oldest element. A stack needs the newest one, so the order has to be inverted somewhere.
Since a queue offers no way to reach the back, the inversion has to happen by rotation. Push the new element, then move every element that was already there to the back of the queue, one at a time. After the rotation the newest element sits at the front, exactly where the queue will serve it next.
That single decision shapes the whole design:
- Push does all the work at O(n); pop and top become trivial O(1) reads.
It is a deliberate trade. The alternative — a cheap push and an expensive pop — is equally valid and uses two queues, shuffling elements across on each removal. Neither can make both operations O(1), because reversing order costs a full pass no matter where you put it.
One queue is enough for the rotation. After enqueuing the new element, dequeue and re-enqueue the previous size elements; they cycle around and land behind the newcomer. The two-queue version performs the same dance with a spare container, which some find easier to picture but which uses more memory for no gain.
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.
Approach
Before reading on: price up what the direct approach costs here, then ask what unresolved thing you are holding, and what event finally resolves it. Aim for O(n) push, O(1) pop/top time and O(n) space.
Decide which operation pays the cost
Reversing a queue's order takes a full pass, so either push or pop must be O(n). Making push expensive keeps pop and top at O(1), which is usually the better trade since reads tend to outnumber writes in stack use.
Enqueue the new element first
Add the value to the back of the queue as normal. At this instant it is in the wrong place — it is the newest but sits last, which is precisely what the rotation is about to fix.
Rotate the older elements behind it
Record the size before enqueuing, then dequeue and re-enqueue that many elements. Each one cycles from front to back, passing behind the new element. When the rotation ends the newest value is at the front, and the rest follow in newest-to-oldest order.
Serve pop and top from the front
Because the invariant is maintained on every push, the front of the queue is always the stack's top. Pop dequeues it, top peeks at it — both single O(1) operations with no shuffling.
Cost of the design
Push is O(n) because of the rotation; pop, top and empty are O(1). Space is O(n) with a single queue. The two-queue variant swaps the costs — O(1) push, O(n) pop — and knowing why both exist is what the question is really testing.
Solution & live demo
Common pitfalls
Rotating the wrong number of times
for _ in range(len(self.q)):
self.q.append(self.q.popleft())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
i = 0
while i < len(self.q) - 1:
self.q.append(self.q.popleft()); i += 1for _ 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
self.q1, self.q2 = deque(), deque() # shuffle between them on every push
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.
Edge cases
Rotation of 0 elements — just enqueue.
Invariant (front = newest) is restored by every push, so pops always correct.