Implement Stack using Queues
Rotate-on-push turns one queue into a LIFO
A plain queue always serves its oldest item first — the opposite of what a stack needs. Fix it at push time instead of read time: enqueue the new value at the back, then rotate the queue by dequeuing-and-re-enqueuing every OLDER element exactly (size-1) times. That walks every old item around to the back, leaving the just-pushed value sitting at the front — so the queue's front always matches the stack's top.
Details
Animated on: Build a LIFO stack (push, top, pop, empty) using only one FIFO queue.
Problem:Implement Stack using QueuesEasy
Rotate-on-push turns one queue into a LIFO
step 1 / 8
Start with one empty queue. A single rotation trick on every push will make it behave like a LIFO stack.
1MyStack: keep a single FIFO queue2 the queue is initially empty3 push(x):4 add x at the back of the queue5 repeat (queue size - 1) times: remove the front and add it back at the back6 top(): return the front of the queue7 pop(): remove and return the front of the queue8 empty(): return whether the queue is empty
← / → step · space play · Home restart
Every step in words
Show all 8 steps
- Start with one empty queue. A single rotation trick on every push will make it behave like a LIFO stack.
- push(1): enqueue 1. queue = [1]. Only one element, so no rotation is needed.
- push(2): enqueue 2 at the back. queue = [1,2] — not yet rotated.
- Rotate once (size-1 = 1 time): dequeue the old front (1) and re-enqueue it. queue = [2,1] — the newest push (2) is now at the front.
- top(): read the front of the queue = 2 — exactly the last value pushed.
- pop(): dequeue the front = 2. That's the top of the stack, removed.
- queue is now [1] — the only remaining element sits at the front.
- empty(): queue = [1], not empty — empty() returns false.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.