A lock-free stack
As noted in the introduction, lock-free algorithms are more complicated than equivalent lock-based ones. Essentially, the principle behind them is based on making atomic changes to a single variable while maintaining data consistency.
A last in, first out (LIFO) stack is a very common data structure in programming. We will use a singly linked list to represent the stack abstraction. Each node of the list holds a value and a pointer to the next node, if there is another one; otherwise, it will hold null. The pointer is an atomic reference.
Atomic references
AtomicReference is just like an AtomicInteger, where multiple threads can update the reference without causing any inconsistencies. To update such a reference, we use its compareAndSet method. This method internally uses a CAS (compare and swap) instruction. See chapter 3, More Threading Patterns, for a refresher on CAS if you need to jog your memory.
The following snippet shows an atomic reference in action:
public...
