C++无锁队列实现及测试代码

下面是一个基于C++11的无锁队列实现及测试代码：

#include <atomic>
#include <memory>

template <typename T>
class LockFreeQueue {
private:
    struct Node {
        std::shared_ptr<T> data;
        Node* next;

        Node() : next(nullptr) {}
    };

    std::atomic<Node*> head;
    std::atomic<Node*> tail;

public:
    LockFreeQueue() : head(new Node), tail(head.load()) {}

    LockFreeQueue(const LockFreeQueue&) = delete;
    LockFreeQueue& operator=(const LockFreeQueue&) = delete;

    ~LockFreeQueue() {
        while (Node* const old_head = head.load()) {
            head.store(old_head->next);
            delete old_head;
        }
    }

    void push(T new_value) {
        std::shared_ptr<T> new_data(std::make_shared<T>(std::move(new_value)));
        Node* new_node = new Node;
        Node* old_tail = tail.load();
        old_tail->data.swap(new_data);
        old_tail->next = new_node;
        tail.store(new_node);
    }

    std::shared_ptr<T> pop() {
        Node* old_head = head.load();
        while (old_head != tail.load()) {
            if (head.compare_exchange_weak(old_head, old_head->next)) {
                std::shared_ptr<T> res;
                res.swap(old_head->data);
                delete old_head;
                return res;
            }
        }
        return std::shared_ptr<T>();
    }
};

#include <iostream>
#include <thread>

int main() {
    LockFreeQueue<int> queue;

    std::thread t1([&queue]() {
        for (int i = 0; i < 10; ++i) {
            queue.push(i);
            std::this_thread::sleep_for(std::chrono::milliseconds(100));
        }
    });

    std::thread t2([&queue]() {
        for (int i = 0; i < 10; ++i) {
            auto val = queue.pop();
            if (val) {
                std::cout << "t2: " << *val << std::endl;
            } else {
                std::cout << "t2: queue is empty" << std::endl;
            }
        }
    });

    std::thread t3([&queue]() {
        for (int i = 0; i < 10; ++i) {
            auto val = queue.pop();
            if (val) {
                std::cout << "t3: " << *val << std::endl;
            } else {
                std::cout << "t3: queue is empty" << std::endl;
            }
        }
    });

    t1.join();
    t2.join();
    t3.join();

    return 0;
}

该无锁队列使用两个指针 head 和 tail 分别指向队列头和尾，使用 std::atomic 实现原子操作。push() 使用 std::shared_ptr 存储数据，同时创建新的节点并把 tail 指针指向新的节点。pop() 方法则从 head 开始遍历队列，如果 head 没有指向 tail，就尝试原子地更新 head 指针，将数据保存到 std::shared_ptr 中并返回。如果更新失败，则说明队列已经被其他线程修改，需要重新遍历。

测试代码中创建了三个线程，其中一个线程不断 push()，另外两个线程不断 pop()，当队列为空时输出提示信息。