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

Interview Guide: Lock-Free Stacks Problems and Solutions

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 traditional synchronization primitives like mutexes or semaphores. Instead, it relies on atomic operations—most notably compare-and-swap (CAS)—to achieve thread safety. The canonical implementation is the Treiber Stack, introduced by R. Kent Treiber in 1986. At its heart lies a singly linked list where the top pointer is atomically updated on every push or pop.

The term "lock-free" has a precise meaning in concurrency theory: at least one thread is guaranteed to make progress in a finite number of steps, even if other threads are suspended or delayed. This is stronger than "obstruction-free" (a thread makes progress if it runs in isolation) and weaker than "wait-free" (every thread makes progress in a bounded number of steps). Lock-free stacks sit in the sweet spot—they deliver high performance under contention without the complexity of wait-free designs.

Why Lock-Free Stacks Matter in Interviews

🚀 Deploy your AI agent in 10 minutes

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

Try it free →

Senior systems engineering interviews at companies like Google, Meta, Jump Trading, and Citadel frequently feature lock-free data structure questions. A lock-free stack is the classic "first test" because:

Mastering the lock-free stack gives you a framework to tackle harder problems like lock-free queues (Michael & Scott), concurrent hash tables, and epoch-based memory managers. The patterns—tagged pointers, hazard pointers, epoch reclamation—recur across all lock-free data structures.

The Core Challenges

Challenge 1: The ABA Problem

The ABA problem is the single most famous pitfall in lock-free programming. It arises because CAS compares memory values, not identities. Consider this sequence:

  1. Thread A reads the top pointer and sees Node X.
  2. Thread B pops Node X, pushes a new Node Y, then pushes Node X back (X is reused from a free list, for instance).
  3. Thread A's CAS succeeds because the top pointer looks like Node X—but the stack has changed beneath it.

The CAS cannot distinguish between "the original Node X" and "a recycled node that happens to occupy the same address." This corrupts the stack. The solution is to attach a generation counter or tag to the pointer, creating a tagged pointer (also called a "fat pointer"). On every modification, the counter is incremented, making the pointer value unique across reuses.

Challenge 2: Memory Reclamation

In a lock-free stack, you cannot simply delete a popped node. Why? Because after popping, another thread may still hold a reference to that node and is about to dereference it. Premature deletion causes a use-after-free. Solutions fall into three families:

Challenge 3: Memory Ordering

On modern architectures (x86, ARM, RISC-V), memory operations can be reordered by both the compiler and the CPU. Lock-free stacks demand precise fences. For push, you need a release store so the new node's contents are visible before the top pointer is updated. For pop, you need an acquire load so you see the previous push's data. Using memory_order_relaxed where you should use memory_order_release leads to subtle bugs that only manifest under stress on ARM chips.

Implementing a Lock-Free Stack

Basic Treiber Stack (Unsafe Deletion)

Let's build the simplest version first. This code is not production-ready because it ignores the ABA problem and memory reclamation, but it illustrates the core CAS loop.

#include <atomic>
#include <memory>

template <typename T>
class LockFreeStack {
    struct Node {
        T data;
        Node* next;
        Node(T val) : data(std::move(val)), next(nullptr) {}
    };

    std::atomic<Node*> top_{nullptr};

public:
    void push(T val) {
        Node* new_node = new Node(std::move(val));
        new_node->next = top_.load(std::memory_order_acquire);

        // CAS loop: try to swing top_ to new_node
        while (!top_.compare_exchange_weak(
                   new_node->next,    // expected: current top
                   new_node,           // desired: new node
                   std::memory_order_release,
                   std::memory_order_relaxed)) {
            // If CAS fails, new_node->next is reloaded with current top_
            // Just retry
        }
    }

    std::optional<T> pop() {
        Node* old_top = top_.load(std::memory_order_acquire);

        while (old_top != nullptr) {
            Node* next = old_top->next;

            if (top_.compare_exchange_weak(
                    old_top,   // expected
                    next,      // desired
                    std::memory_order_acquire,
                    std::memory_order_relaxed)) {
                // Successfully unlinked old_top
                T result = std::move(old_top->data);
                delete old_top;   // DANGEROUS: ABA + use-after-free!
                return result;
            }
            // CAS failed; old_top is reloaded, retry
        }
        return std::nullopt;  // stack empty
    }
};

This works correctly only if no nodes are ever reused and no thread holds a stale reference after a pop. In practice, both conditions break immediately under contention. The delete old_top is the ticking time bomb: a thread that just entered pop() with old_top pointing to this node will crash.

Tagged Pointer Solution for ABA

We solve ABA by embedding a counter alongside the pointer. On 64-bit systems, we exploit the fact that addresses typically use only 48 bits (or 52 bits with 5-level paging). The top 16 bits can hold a tag. We pack and unpack using bitwise operations.

#include <atomic>
#include <cstdint>
#include <bit>

// On x86-64 with 48-bit virtual addresses, we can steal 16 bits for the tag.
// Adjust TAG_SHIFT if your platform uses more bits (e.g., 52-bit addresses).
constexpr uintptr_t TAG_MASK   = 0xFFFF'FFFF'FFFFULL;  // lower 48 bits for pointer
constexpr uintptr_t TAG_SHIFT  = 48;
constexpr int       TAG_INCR   = 1;

struct TaggedPointer {
    uintptr_t packed;  // bits 0-47: pointer, bits 48-63: tag

    static TaggedPointer make(Node* ptr, uint16_t tag) {
        return TaggedPointer{
            (reinterpret_cast<uintptr_t>(ptr) & TAG_MASK) |
            (static_cast<uintptr_t>(tag) << TAG_SHIFT)
        };
    }

    Node* ptr() const {
        return reinterpret_cast<Node*>(packed & TAG_MASK);
    }

    uint16_t tag() const {
        return static_cast<uint16_t>(packed >> TAG_SHIFT);
    }
};

template <typename T>
class TaggedLockFreeStack {
    struct Node {
        T data;
        TaggedPointer next;  // points to next node with tag
        Node(T val) : data(std::move(val)), next(TaggedPointer{0}) {}
    };

    // Atomic tagged pointer for the top of stack
    std::atomic<uintptr_t> top_packed_{0};

    TaggedPointer load_top(std::memory_order order) const {
        return TaggedPointer{top_packed_.load(order)};
    }

public:
    void push(T val) {
        Node* new_node = new Node(std::move(val));
        TaggedPointer old_top = load_top(std::memory_order_acquire);

        // Set new_node->next to point to current top (with its tag)
        new_node->next = old_top;

        // New tag = old tag + 1 (or any unique increment)
        TaggedPointer new_top = TaggedPointer::make(
            new_node, old_top.tag() + TAG_INCR);

        uintptr_t expected = old_top.packed;
        // CAS loop
        while (!top_packed_.compare_exchange_weak(
                    expected,
                    new_top.packed,
                    std::memory_order_release,
                    std::memory_order_relaxed)) {
            // Reload old_top from the failed expected value
            old_top = TaggedPointer{expected};
            new_node->next = old_top;
            new_top = TaggedPointer::make(new_node, old_top.tag() + TAG_INCR);
        }
    }

    std::optional<T> pop() {
        TaggedPointer old_top = load_top(std::memory_order_acquire);

        while (old_top.ptr() != nullptr) {
            Node* node = old_top.ptr();
            TaggedPointer next = node->next;  // read next with its tag

            TaggedPointer new_top = TaggedPointer::make(
                next.ptr(), old_top.tag() + TAG_INCR);

            uintptr_t expected = old_top.packed;
            if (top_packed_.compare_exchange_weak(
                    expected,
                    new_top.packed,
                    std::memory_order_acquire,
                    std::memory_order_relaxed)) {
                T result = std::move(node->data);
                // STILL UNSAFE: need hazard pointers or EBR for deletion
                // For now: leak or use a deferred reclamation scheme
                delete node;
                return result;
            }
            old_top = TaggedPointer{expected};
        }
        return std::nullopt;
    }
};

Notice the tagged pointer eliminates ABA because the tag changes on every push/pop. Even if a node is recycled at the same address, the tag differs, so the CAS fails. But we still have the reclamation problem—that delete node is unsafe under contention.

Hazard Pointers for Safe Deletion

Hazard pointers were introduced by Maged Michael in 2004. The idea: before accessing a shared node, a thread publishes a "hazard pointer" declaring "I am currently using this node." A reclaimer thread scans all hazard pointers and only frees nodes that no thread has hazarded.

#include <atomic>
#include <vector>
#include <thread>
#include <algorithm>

// Global hazard pointer array: one slot per thread (pre-allocated)
constexpr int MAX_THREADS = 128;
std::atomic<Node*> hazard_pointers[MAX_THREADS];

// Each thread gets a unique slot index at startup
thread_local int my_hp_slot = []() {
    static std::atomic<int> next_slot{0};
    return next_slot.fetch_add(1);
}();

// Announce that we are accessing a node
void set_hazard(Node* node) {
    hazard_pointers[my_hp_slot].store(node, std::memory_order_release);
}

// Clear our hazard pointer
void clear_hazard() {
    hazard_pointers[my_hp_slot].store(nullptr, std::memory_order_release);
}

// Check if any thread has hazarded a given node
bool is_hazarded(Node* node) {
    for (int i = 0; i < MAX_THREADS; ++i) {
        if (hazard_pointers[i].load(std::memory_order_acquire) == node) {
            return true;
        }
    }
    return false;
}

// Retire a node: add to a thread-local retire list, batch-free when safe
thread_local std::vector<Node*> retire_list;
constexpr int RETIRE_THRESHOLD = 64;

void retire_node(Node* node) {
    retire_list.push_back(node);
    if (retire_list.size() >= RETIRE_THRESHOLD) {
        // Attempt to free nodes that no thread has hazarded
        std::vector<Node*> survivors;
        for (Node* n : retire_list) {
            if (is_hazarded(n)) {
                survivors.push_back(n);  // still in use, keep it
            } else {
                delete n;  // safe to free
            }
        }
        retire_list = std::move(survivors);
    }
}

Now integrate hazard pointers into the pop operation:

std::optional<T> pop_safe() {
    TaggedPointer old_top = load_top(std::memory_order_acquire);

    while (old_top.ptr() != nullptr) {
        Node* node = old_top.ptr();

        // Publish hazard pointer BEFORE dereferencing node->next
        set_hazard(node);

        // Fence to ensure hazard pointer is visible before we read node->next
        std::atomic_thread_fence(std::memory_order_seq_cst);

        // Re-read top after publishing hazard (defense against race)
        TaggedPointer current_top = load_top(std::memory_order_acquire);
        if (current_top.packed != old_top.packed) {
            // Top changed; retry from the new top
            clear_hazard();
            old_top = current_top;
            continue;
        }

        TaggedPointer next = node->next;
        TaggedPointer new_top = TaggedPointer::make(
            next.ptr(), old_top.tag() + TAG_INCR);

        uintptr_t expected = old_top.packed;
        if (top_packed_.compare_exchange_weak(
                expected,
                new_top.packed,
                std::memory_order_acquire,
                std::memory_order_relaxed)) {
            T result = std::move(node->data);

            // Node is unlinked; clear hazard and retire for deferred deletion
            clear_hazard();
            retire_node(node);
            return result;
        }

        // CAS failed; clear hazard, update old_top, retry
        clear_hazard();
        old_top = TaggedPointer{expected};
    }
    clear_hazard();
    return std::nullopt;
}

The critical sequence is: hazard → fence → re-validate → dereference. The fence prevents the CPU from reordering the hazard store after the node->next load. Without it, another thread could see an empty hazard pointer while we're already reading through the node. The re-validation (current_top check) closes a tiny window where the node could have been popped and freed between our initial load and the hazard publication.

Epoch-Based Reclamation (EBR) — The High-Performance Alternative

Hazard pointers require a store and fence on every access. EBR amortizes this cost. Threads operate in a global epoch (0, 1, 2...). A thread announces its current epoch. Objects are tagged with the epoch when they were retired. When all active threads have advanced past a given epoch, objects from that epoch can be freed. The overhead per operation is just a few loads and stores—no expensive fences.

// Simplified EBR sketch (full implementation requires careful state machine)
class EpochManager {
    std::atomic<uint64_t> global_epoch_{0};
    std::atomic<int> active_threads_in_epoch_[3] = {};

public:
    uint64_t enter_epoch() {
        // Announce we are active in the current epoch
        uint64_t e = global_epoch_.load(std::memory_order_acquire);
        active_threads_in_epoch_[e % 3].fetch_add(1, std::memory_order_relaxed);
        // Ensure our epoch announcement is visible
        std::atomic_thread_fence(std::memory_order_seq_cst);
        // Re-read: if epoch changed, we may need to adjust
        return global_epoch_.load(std::memory_order_relaxed);
    }

    void leave_epoch(uint64_t epoch) {
        active_threads_in_epoch_[epoch % 3].fetch_sub(1, std::memory_order_release);
    }

    bool can_free(uint64_t retired_epoch) {
        // An object can be freed if its retirement epoch is two epochs behind
        // the current global epoch AND no threads remain in that epoch.
        uint64_t current = global_epoch_.load(std::memory_order_acquire);
        if (current - retired_epoch < 2) return false;
        return active_threads_in_epoch_[retired_epoch % 3].load(std::memory_order_acquire) == 0;
    }

    void try_advance_epoch() {
        // If the current epoch has no active threads, advance global_epoch_
        uint64_t e = global_epoch_.load(std::memory_order_relaxed);
        if (active_threads_in_epoch_[e % 3].load(std::memory_order_acquire) == 0) {
            global_epoch_.compare_exchange_strong(e, e + 1, std::memory_order_release);
        }
    }
};

In practice, production EBR implementations (like folly::RCU or libcds) combine epochs with grace periods and batch deletion for extremely high throughput. The key insight for interviews: you don't need to implement a full EBR system from scratch, but you should be able to explain the trade-offs—EBR gives higher throughput but can cause memory to accumulate if a thread stalls in an epoch indefinitely, whereas hazard pointers are more predictable but have higher per-operation overhead.

Common Interview Questions & Solutions

Q1: "Implement a lock-free stack from scratch."

What they're testing: Can you write a correct CAS loop under pressure? Do you naturally reach for compare_exchange_weak? Do you use proper memory ordering?

Solution approach: Start with the Treiber stack skeleton. Write the Node struct, the atomic top, and the push/pop CAS loops. Use compare_exchange_weak in a loop (it may spuriously fail on some architectures, which is fine because you retry). Explicitly state your memory order choices. Then say: "This basic version has two problems—ABA and safe deletion. Let me address them."

Q2: "Explain the ABA problem and how you'd solve it."

What they're testing: Do you truly understand CAS semantics, or did you just memorize the pattern?

Solution approach: Give the concrete three-step example (Thread A reads X, Thread B pops/pushes/reuses X, Thread A's CAS succeeds incorrectly). Then explain tagged pointers: "We pack a monotonic counter into the unused bits of the pointer. Every push increments the counter, so even if the same address reappears, the CAS fails because the packed value differs." Show the bit layout and mention platform-specific constraints (48-bit addresses on x86-64).

Q3: "How do you safely delete nodes in a lock-free stack?"

What they're testing: Knowledge of the memory reclamation taxonomy and practical experience with hazard pointers or EBR.

Solution approach: Enumerate the options. "There are three standard approaches: hazard pointers, epoch-based reclamation, and reference counting with atomic shared_ptr. Hazard pointers are the simplest to explain—each thread publishes which node it's currently accessing. Before freeing a node, we scan all hazard pointers. EBR is faster but more complex, grouping deletions by epoch. For an interview, I'd implement hazard pointers." Then sketch the hazard pointer integration into pop.

Q4: "What memory order do you use and why?"

What they're testing: Understanding of the C++ memory model, not just cargo-culting memory_order_seq_cst.

Solution approach: "For push: the store to new_node->next must be visible before we publish new_node via CAS, so the CAS uses memory_order_release. For pop: the load of top_ must synchronize with that release to see the full node chain, so we use memory_order_acquire. The failure path in CAS can be memory_order_relaxed because we just retry. I only use seq_cst fences in the hazard pointer integration to prevent reordering of the hazard store and the node dereference."

Q5: "What happens if a thread stalls while holding a hazard pointer?"

What they're testing: Understanding of liveness vs. safety trade-offs.

Solution approach: "Hazard pointers are lock-free but not wait-free for reclamation. If a thread stalls (e.g., descheduled by the OS) while holding a hazard pointer, the node it references cannot be freed. This causes retire list inflation—the reclaimer accumulates garbage. However, the stack operations themselves remain lock-free; other threads can still push and pop. The stalled thread does not block progress, it only delays memory reclamation. EBR has a similar issue: a stalled thread in an old epoch prevents freeing all objects retired in that epoch. This is why production systems combine reclamation with timeouts or fallback mechanisms."

Best Practices

Conclusion

The lock-free stack is a microcosm of concurrent systems engineering. In a compact, interview-friendly package, it touches atomic operations, memory ordering, the ABA problem, memory reclamation strategies, and the delicate balance between performance and correctness. Walking through a complete implementation—from the naive Treiber stack to a tagged-pointer, hazard-pointer-equipped version—demonstrates not just knowledge of lock-free programming but the judgment to know which problems matter and how to solve them systematically. Whether you're preparing for a systems interview or building a high-throughput trading engine, the patterns you internalize here—CAS loops, tagged pointers, deferred reclamation—will recur across every lock-free data structure you encounter. Master the lock-free stack, and you've mastered the foundation.

🚀 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