← Back to DevBytes
Developer Tutorial July 14, 2026 13 min read

Lock-Free Stacks: Implementation and Time Complexity Analysis

What Is a Lock-Free Stack?

A lock-free stack is a concurrent data structure that allows multiple threads to push and pop elements without using mutual exclusion locks (mutexes, spinlocks, etc.). Instead of locking, it relies on atomic hardware primitives—most notably compare-and-swap (CAS)—to coordinate access to shared memory. The canonical implementation is the Treiber stack, introduced by R. Kent Treiber in 1986, which uses a singly-linked list with an atomically updated top pointer.

At its core, a lock-free stack guarantees that at least one thread makes progress in a finite number of its own steps, regardless of how other threads are scheduled. This is a weaker guarantee than wait-free (where every thread makes progress in a bounded number of steps), but it is sufficient to avoid the pitfalls of lock-based synchronization: no thread can be indefinitely blocked by another thread that is preempted, crashed, or delayed while holding a lock.

Why Lock-Free Stacks Matter

🚀 Deploy your AI agent in 10 minutes

Managed Hermes hosting. Zero DevOps. 100M tokens/mo included.

Try it free →

The Lock Contention Problem

In a lock-based stack, every push and pop operation acquires a mutex. When contention is high, threads spend significant time blocked, waiting for the lock holder to complete. This leads to:

Advantages of Lock-Free Design

Lock-free stacks sidestep these problems entirely:

The trade-off is increased algorithmic complexity: developers must carefully handle the ABA problem, memory reclamation, and the subtleties of atomic ordering.

Core Implementation: The Treiber Stack

The Treiber stack is a singly-linked list where the top pointer (head) points to the most recently pushed node. All operations manipulate this top pointer atomically using CAS. Let's build it step by step.

The Node Structure

Each node holds a value and a pointer to the next node. For simplicity, we use a raw pointer here; production code would use something safer like std::atomic<Node*> or tagged pointers to combat the ABA problem.

template<typename T>
struct Node {
    T value;
    Node* next;
    
    Node(const T& val, Node* nxt = nullptr)
        : value(val), next(nxt) {}
};

Push Operation with CAS

The push operation creates a new node, sets its next pointer to the current top, and then atomically swings the top pointer to the new node. If another thread changed the top in the meantime, the CAS fails and we retry.

Here is the algorithm in pseudocode:

1. Create a new node with the value to push.
2. Read the current top pointer.
3. Set new_node.next = current top.
4. Atomically compare-and-swap top from current top to new_node.
5. If CAS fails (top changed), go back to step 2.

In C++ with std::atomic, this translates to:

template<typename T>
class LockFreeStack {
private:
    std::atomic<Node<T>*> top;
    
public:
    LockFreeStack() : top(nullptr) {}
    
    void push(const T& value) {
        Node<T>* new_node = new Node<T>(value);
        Node<T>* old_top = top.load(std::memory_order_acquire);
        
        do {
            new_node->next = old_top;
        } while (!top.compare_exchange_weak(
            old_top,          // expected — updated on failure
            new_node,         // desired
            std::memory_order_release,
            std::memory_order_relaxed
        ));
    }
};

A few critical details here:

Pop Operation with CAS

Pop is slightly trickier. We must atomically move the top pointer from the current head to the next node, but only if the stack is non-empty. The pseudocode:

1. Read the current top pointer.
2. If top is null, return empty / false.
3. Read top->next.
4. Atomically compare-and-swap top from current top to top->next.
5. If CAS fails, go back to step 1.
6. On success, extract the value from the old top node and delete it.

Here is the C++ implementation:

bool pop(T& result) {
    Node<T>* old_top = top.load(std::memory_order_acquire);
    
    do {
        if (old_top == nullptr) {
            return false;  // stack empty
        }
        Node<T>* new_top = old_top->next;
        
        if (top.compare_exchange_weak(
            old_top,          // expected
            new_top,          // desired
            std::memory_order_acquire,
            std::memory_order_relaxed
        )) {
            result = old_top->value;
            delete old_top;   // reclaim node
            return true;
        }
        // CAS failed: old_top was updated to the current top
    } while (true);
}

The acquire ordering on success ensures we correctly read the node's value and next pointer after taking ownership. Note that this naive implementation is vulnerable to the ABA problem, which we'll discuss shortly.

Complete Implementation Example

Below is a full, self-contained lock-free stack with both push and pop, along with a basic test harness that spawns multiple threads:

#include <atomic>
#include <thread>
#include <vector>
#include <iostream>
#include <cassert>

template<typename T>
struct Node {
    T value;
    Node* next;
    Node(const T& v, Node* n = nullptr) : value(v), next(n) {}
};

template<typename T>
class LockFreeStack {
    std::atomic<Node<T>*> top;
    
public:
    LockFreeStack() : top(nullptr) {}
    
    ~LockFreeStack() {
        // drain remaining nodes
        Node<T>* curr = top.load();
        while (curr) {
            Node<T>* next = curr->next;
            delete curr;
            curr = next;
        }
    }
    
    void push(const T& value) {
        Node<T>* new_node = new Node<T>(value);
        Node<T>* old_top = top.load(std::memory_order_acquire);
        do {
            new_node->next = old_top;
        } while (!top.compare_exchange_weak(
            old_top,
            new_node,
            std::memory_order_release,
            std::memory_order_relaxed
        ));
    }
    
    bool pop(T& result) {
        Node<T>* old_top = top.load(std::memory_order_acquire);
        do {
            if (old_top == nullptr) return false;
            Node<T>* new_top = old_top->next;
            if (top.compare_exchange_weak(
                old_top,
                new_top,
                std::memory_order_acquire,
                std::memory_order_relaxed
            )) {
                result = old_top->value;
                delete old_top;
                return true;
            }
        } while (true);
    }
};

// Test: multiple producers, multiple consumers
void producer(LockFreeStack<int>& stack, int start, int count) {
    for (int i = start; i < start + count; ++i) {
        stack.push(i);
    }
}

void consumer(LockFreeStack<int>& stack, int expected_total, std::atomic<int>& sum) {
    int val;
    int local_sum = 0;
    int retrieved = 0;
    while (retrieved < expected_total) {
        if (stack.pop(val)) {
            local_sum += val;
            ++retrieved;
        }
    }
    sum.fetch_add(local_sum, std::memory_order_relaxed);
}

int main() {
    constexpr int NUM_THREADS = 8;
    constexpr int ITEMS_PER_THREAD = 100000;
    
    LockFreeStack<int> stack;
    std::atomic<int> total_sum{0};
    
    std::vector<std::thread> threads;
    
    // Launch producers
    for (int i = 0; i < NUM_THREADS / 2; ++i) {
        threads.emplace_back(producer, std::ref(stack), 
                             i * ITEMS_PER_THREAD, ITEMS_PER_THREAD);
    }
    
    // Launch consumers (each expects to consume half the total)
    int total_items = (NUM_THREADS / 2) * ITEMS_PER_THREAD;
    for (int i = 0; i < NUM_THREADS / 2; ++i) {
        threads.emplace_back(consumer, std::ref(stack),
                             total_items / (NUM_THREADS / 2),
                             std::ref(total_sum));
    }
    
    for (auto& t : threads) t.join();
    
    // Verify sum: sum of [0, total_items) = total_items*(total_items-1)/2
    int expected = (total_items * (total_items - 1)) / 2;
    std::cout << "Sum: " << total_sum.load() 
              << " Expected: " << expected << std::endl;
    assert(total_sum.load() == expected);
    
    return 0;
}

This example demonstrates a working lock-free stack with multiple producers and consumers. The assertions verify correctness under concurrent access.

Time Complexity Analysis

Analyzing lock-free data structures requires a different lens than traditional big-O on a single thread. We must consider contention, CAS retries, and amortized behavior across threads.

Per-Operation Complexity (Ideal Case)

In the absence of contention (single thread or no conflicting CAS), both push and pop perform:

Thus, the uncontended time complexity is O(1) per operation. The constant factors are small: a few nanoseconds on modern hardware, comparable to a mutex-based stack's uncontended path.

CAS Retry Loop Analysis

Under contention, a CAS may fail because another thread successfully modified top between our load and our CAS attempt. Each failed CAS means we must reload top and retry. How many retries can we expect?

Let n be the number of concurrently contending threads. In the worst case, each thread's CAS fails because another thread's CAS succeeds, forcing a retry. However, each successful CAS represents progress for some thread. The key insight: the total number of CAS attempts across all threads to complete k operations is bounded by k + f, where f is the number of failed CAS attempts.

Empirically and analytically, under reasonable contention (n << operation duration), the expected number of retries per operation approaches O(1) amortized. Under extremely high contention (saturating the memory interconnect), retries can grow, but the system still makes forward progress—unlike lock-based approaches where a preempted lock holder can cause unbounded waiting.

Amortized Analysis of Push

Consider m push operations across n threads. Each push allocates a node (heap allocation, typically O(log m) for the allocator but treated as O(1) amortized with modern allocators), then enters the CAS loop.

The CAS loop itself:

Amortized Analysis of Pop

Pop follows the same CAS retry pattern. The additional step is deleting the node after a successful CAS. Deallocation (calling delete) is O(1). However, a subtlety arises: if many threads are popping simultaneously, the memory allocator itself may become a bottleneck (contention in malloc/free). This is not a property of the stack algorithm but of the allocator.

In summary, both push and pop have amortized O(1) time complexity per operation, with constant factors influenced by:

Comparison with Lock-Based Stacks

A mutex-based stack also offers O(1) per operation in the uncontended case. But under contention, the lock approach suffers from:

The lock-free stack avoids these unbounded delays entirely. While individual CAS retries burn CPU cycles (spinning), the total wall-clock latency per operation remains low and predictable. This makes lock-free stacks ideal for low-latency systems like trading engines, real-time audio processing, and operating system kernels.

Memory Management and the ABA Problem

Understanding ABA

The naive implementation above suffers from the ABA problem. Consider this scenario:

1. Thread A reads top = Node_X, and top->next = Node_Y.
2. Thread A is preempted.
3. Thread B pops Node_X, pops Node_Y, pushes Node_X back (or a new node
   that happens to be allocated at the same address as Node_X).
4. Thread A resumes. Its CAS compares top (still Node_X) — it matches!
   But top->next is now different (not Node_Y anymore, maybe Node_Z).
5. Thread A's CAS succeeds, setting top to its new node, whose next
   pointer still points to the stale Node_Y. Node_Y has been freed
   and possibly reused. The stack is now corrupted.

The ABA problem arises because the CAS only checks pointer values, not identity over time. A pointer can be reused and the CAS cannot distinguish the original Node_X from a recycled one.

Solutions: Tagged Pointers and Safe Memory Reclamation

Two common approaches mitigate ABA:

Here is a sketch of a tagged-pointer push operation:

// On 64-bit: lower 48 bits = pointer, upper 16 bits = tag
using TaggedPtr = uint64_t;

TaggedPtr pack(Node<T>* ptr, uint16_t tag) {
    return (uint64_t)(ptr) | ((uint64_t)(tag) << 48);
}

Node<T>* unpack_ptr(TaggedPtr packed) {
    return (Node<T>*)(packed & 0xFFFFFFFFFFFFULL);
}

uint16_t unpack_tag(TaggedPtr packed) {
    return (uint16_t)(packed >> 48);
}

void push(const T& value) {
    Node<T>* new_node = new Node<T>(value);
    TaggedPtr old_top_packed = top.load(std::memory_order_acquire);
    Node<T>* old_top_ptr = unpack_ptr(old_top_packed);
    uint16_t old_tag = unpack_tag(old_top_packed);
    
    do {
        new_node->next = old_top_ptr;
        TaggedPtr new_packed = pack(new_node, old_tag + 1);
        // CAS on the full 64-bit tagged value
    } while (!top.compare_exchange_weak(
        old_top_packed,
        new_packed,
        std::memory_order_release,
        std::memory_order_relaxed
    ));
}

This tagged-pointer scheme eliminates ABA because the tag increments on every push, making recycled addresses distinguishable.

Best Practices

Conclusion

Lock-free stacks, epitomized by the Treiber stack, offer a compelling alternative to mutex-based concurrency for LIFO data structures. Their implementation hinges on atomic compare-and-swap operations and careful management of the ABA problem. The time complexity is O(1) amortized per operation, even under contention, with the key advantage being the elimination of unbounded blocking and deadlock risks. While they demand greater attention to memory ordering, pointer tagging, and safe reclamation, the payoff is a highly responsive, predictable data structure suitable for the most demanding low-latency and high-throughput systems. By following the patterns and best practices outlined here—correct CAS loops, ABA mitigation via tagged pointers, and rigorous stress testing—you can confidently deploy lock-free stacks in production environments where traditional locks would become the limiting factor.

🚀 Need a reliable AI agent for your project?

Deploy Hermes Agent in 10 minutes. Managed hosting, zero DevOps.

Get Started — $23.99/mo
← Back to all articles