Concurrent Stack Implementations
You'll learn how to build thread-safe stacks using both lock-based synchronization and lock-free algorithms like Treiber's.
The Core Challenge
A stack is conceptually simple: push items onto the top, pop them off the top (LIFO). But when multiple threads try to push or pop simultaneously, you face race conditions. Two threads might read the same "top" pointer, both try to update it, and one update gets lost—corrupting your stack.
Lock-Based Approach
The straightforward solution wraps a regular stack with a mutex (lock). Every push or pop operation acquires the lock, modifies the stack, then releases it. This guarantees mutual exclusion—only one thread modifies the structure at a time.
Pros: Simple to reason about, guaranteed correctness.
Cons: Lock contention creates bottlenecks; threads wait even when operations wouldn't actually conflict.
Treiber's Lock-Free Stack
The elegant alternative is Treiber's algorithm, which uses atomic compare-and-swap (CAS) operations:
- Push: Read current
toppointer, create a new node pointing to it, then CAStopto your new node (retry if someone else changedtopfirst) - Pop: Read
top, read itsnextpointer, then CAStoptonext(retry on conflict)
No locks needed! Threads make optimistic attempts and retry on collision. This eliminates lock overhead but introduces ABA problem risks (requiring hazard pointers or epoch-based reclamation for safe memory management).
Choosing Your Approach
Lock-based is simpler and sufficient for moderate contention. Lock-free shines under high contention where avoiding blocking matters—but adds complexity around memory reclamation.
Key Takeaway: Thread-safe stacks can be built with locks for simplicity or lock-free CAS operations (Treiber's algorithm) for better scalability, each trading off implementation complexity against contention performance.