Queue Using Two Stacks
Enqueue onto an in stack; when the out stack is empty, pour everything across to reverse the order.
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.
What you will see
Items pour from one stack to the other, reversing; the pour is amortized O(1).
Cost
| Best | O(1) |
|---|---|
| Average | O(1) amortized |
| Worst | O(n) |
| Space | O(n) |
How you work with it here
play it through, step one change at a time, scrub to any step, run it on your own input, predict what happens next, try operations in any order.
Screen readers: Items announce position from the top or front and value; each step announces the operation and the new top or front.
Reduced motion: Items appear or disappear in place with a crossfade instead of sliding in or out.