A concurrent LIFO stack: a singly linked list with an atomic head pointer. push and pop are CAS retry loops. Watch two threads race, a CAS retry, and the classic ABA corruption — then the tagged-pointer fix.
| Operation | Time | Space | Note |
|---|---|---|---|
push | O(1)* | O(1) | 1 CAS; * unbounded retries under contention |
pop | O(1)* | O(1) | 1 CAS; ABA hazard |
peek | O(1) | O(1) | single atomic load |
isEmpty | O(1) | O(1) | head==nil |
Lock-free = the system always makes progress even if a thread stalls (not the same as fast). ABA: head goes A→B→A, so a stale CAS sees the same bits and succeeds wrongly. Fix: a version tag on the head — every successful CAS bumps it, so a recycled pointer carries a fresh tag and the stale CAS fails.