#include <queue>
#include <mutex>
#include <condition_variable>

template <typename T>
class LockedQueue {
private:
    std::queue<T> queue_;
    mutable std::mutex mutex_;
    std::condition_variable cond_;

public:
    // 插入元素（線程安全）
    void push(T value) {
        {
            std::lock_guard<std::mutex> lock(mutex_);
            queue_.push(std::move(value));
        }  // 自動(dòng)解鎖作用域
        cond_.notify_one();  // 通知等待線程
    }

    // 非阻塞彈出（立即返回）
    bool try_pop(T& value) {
        std::lock_guard<std::mutex> lock(mutex_);
        if (queue_.empty()) return false;
        value = std::move(queue_.front());
        queue_.pop();
        return true;
    }

    // 阻塞式彈出（等待元素）
    void wait_and_pop(T& value) {
        std::unique_lock<std::mutex> lock(mutex_);
        // 條件等待：防止虛假喚醒
        cond_.wait(lock, [this] { return !queue_.empty(); });
        value = std::move(queue_.front());
        queue_.pop();
    }

    // 可選：隊(duì)列大?。ǚ蔷_值）
    size_t size() const {
        std::lock_guard<std::mutex> lock(mutex_);
        return queue_.size();
    }
};

#include <atomic>
#include <memory>
#include <vector>

template <typename T>
class LockFreeSPSCQueue {
private:
    struct Node {
        std::atomic<Node*> next;
        T data;
        Node() : next(nullptr) {}  // Dummy node
        Node(T val) : data(std::move(val)), next(nullptr) {}
    };

    // 緩存行對(duì)齊（64字節(jié)）防止偽共享
    alignas(64) std::atomic<Node*> head_;
    alignas(64) std::atomic<Node*> tail_;

    // 預(yù)分配節(jié)點(diǎn)池（減少內(nèi)存分配開銷）
    std::vector<std::unique_ptr<Node>> node_pool_;

    Node* alloc_node(T value = T{}) {
        node_pool_.push_back(std::make_unique<Node>(std::move(value)));
        return node_pool_.back().get();
    }

public:
    LockFreeSPSCQueue() {
        Node* dummy = alloc_node();  // 創(chuàng)建虛擬節(jié)點(diǎn)
        head_.store(dummy, std::memory_order_relaxed);
        tail_.store(dummy, std::memory_order_relaxed);
    }

    ~LockFreeSPSCQueue() {
        // 自動(dòng)清理通過 unique_ptr 管理
    }

    // 生產(chǎn)者操作
    void push(T value) {
        Node* new_node = alloc_node(std::move(value));
        Node* old_tail = tail_.exchange(new_node, std::memory_order_acq_rel);
        
        // 關(guān)鍵：先設(shè)置 tail 再連接 next
        old_tail->next.store(new_node, std::memory_order_release);
    }

    // 消費(fèi)者操作
    bool pop(T& value) {
        Node* old_head = head_.load(std::memory_order_relaxed);
        Node* next_ptr = old_head->next.load(std::memory_order_acquire);

        if (!next_ptr) return false;  // 空隊(duì)列
        
        // 移動(dòng)數(shù)據(jù)并更新頭節(jié)點(diǎn)
        value = std::move(next_ptr->data);
        head_.store(next_ptr, std::memory_order_release);
        
        // 回收舊頭節(jié)點(diǎn)（實(shí)際由 node_pool_ 統(tǒng)一管理）
        old_head->next.store(nullptr, std::memory_order_relaxed);
        return true;
    }
};

// 使用帶標(biāo)記指針的原子操作
struct TaggedPtr {
    Node* ptr;
    uintptr_t tag;  // 操作計(jì)數(shù)器
};

std::atomic<TaggedPtr> head_;

bool pop(T& value) {
    TaggedPtr old_head = head_.load();
    while (true) {
        Node* next = old_head.ptr->next.load();
        if (!next) return false;
        TaggedPtr new_head{next, old_head.tag + 1};
        if (head_.compare_exchange_weak(old_head, new_head)) {
            value = next->data;
            return true;
        }
    }
}