Async Queue

┌───────────────┐     ┌───────────────┐     ┌───────────────┐
│  Node (T=0)   │  ┌─►│  Node (T=1)   │  ┌─►│  Node (T=2)   │
├───────┬───────┤  │  ├───────┬───────┤  │  ├───────┬───────┤
│ queue │ [x,y] │  │  │ queue │ [z]   │  │  │ queue │ [w]   │
│  done │ false │  │  │  done │ true  │  │  │  done │ false │
│  next │   ────┼──┘  │  next │   ────┼──┘  │  next │ null  │
└───────┴───────┘     └───────┴───────┘     └───────┴───────┘

────────────────────────────time────────────────────────────►

What is it?

This data structure aims to solve the problem of relative ordering of events running on separate threads.

Imagine you're running an expensive computation that you want to split across threads. We want to compute $f(x)$ for all integers $x$ in the range $[0..1000]$ and print the results in order.

If we just print within each thread, the results will almost certainly be interleaved.