AlgoScope

Queue Using Two Stacks

Enqueue onto an in stack. When the out stack is empty, pour everything across to reverse the order.

Stack and queue algorithms, algorithm, intermediate
Pouring 3 items from in to out.bottomtopinout539
Pouring 3 items from in to out.bottomtopinout539

Queue: Queue from two stacks

Decision, step 5 of 16

dequeue: the out stack is empty, so the front of the queue is buried at the bottom of in. Pour: pop every item off in and push it onto out, 5, 3, 9 in that order, which puts 5, the oldest, on top of out.

How queue works

Cost

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

Taught by the same lesson

Queue covers these too, in the same run.