How Do You Implement a Lock-Free Data Structure in C++?

Lock-free data structures allow concurrent access without using locks. They use atomic operations to ensure thread safety. Such structures, like lock-free stacks and queues, improve performance by avoiding lock overhead.

Example of a lock-free stack:

#include 
#include 
#include 

class LockFreeStack {
    struct Node {
        int data;
        Node* next;
    };

    std::atomic head;

public:
    LockFreeStack() : head(nullptr) {}

    void push(int value) {
        Node* newNode = new Node{value, head.load()};
        while (!head.compare_exchange_weak(newNode->next, newNode)) {
            // Retry if another thread updated the head
        }
    }

    bool pop(int& value) {
        Node* oldHead = head.load();
        while (oldHead && !head.compare_exchange_weak(oldHead, oldHead->next)) {
            // Retry if another thread updated the head
        }
        if (oldHead) {
            value = oldHead->data;
            delete oldHead;
            return true;
        }
        return false;
    }
};

int main() {
    LockFreeStack stack;
    std::thread t1([&stack]() {
        for (int i = 0; i < 1000; ++i) {
            stack.push(i);
        }
    });
    std::thread t2([&stack]() {
        int value;
        for (int i = 0; i < 1000; ++i) {
            if (stack.pop(value)) {
                std::cout << "Popped: " << value << std::endl;
            }
        }
    });
    t1.join();
    t2.join();
    return 0;
}