An interactive FIFO queue: a singly linked list with a dummy node, atomic head and tail pointers, enqueue/dequeue via CAS, the two-step tail update with a helping advance, and a contention retry.
| Operation | Time | Space | Notes |
|---|---|---|---|
| Enqueue | O(1) | O(1) | link CAS + tail advance |
| Dequeue | O(1) | O(1) | read next.value, head CAS |
| Peek front | O(1) | O(1) | head.next.value |
| IsEmpty | O(1) | O(1) | head==tail && next==null |
| Search / index | O(n) | O(1) | not a queue op |
| Contended op | O(1)* | O(1) | amortized; retries are O(1) each |
The orange arrow marks a lagging tail (tail behind the real last node). Any thread that sees it helps by CAS-advancing tail.