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.
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...