AlgoScope

Stack Using Queues

Rotate the queue after each push so the newest item sits at the front.

Stack and queue algorithms, algorithm, intermediate
1 rotations needed.frontbackqueue53
1 rotations needed.frontbackqueue53

Stack: Built from one queue: rotate after each push

Decision, step 4 of 18

3 is behind 1 older item. Each rotation dequeues the front and enqueues it at the back, so after 1 rotations every older item has gone round once and 3 is at the front.

How stack works

Cost

Best
O(1)
Average
O(n)
Worst
O(n)
Space
O(n)

Push is O(n) pop O(1) in this variant.

Taught by the same lesson

Stack covers these too, in the same run.