#include <thread>
#include <atomic>
#include <deque>
#include <condition_variable>
#include <mutex>

using namespace std;

template<typename T>
class lock_free_queue {

    struct Node {
        atomic<Node*> next;
        T value;
        Node() { next = nullptr; }
        Node(T nvalue) : value(nvalue) { next = nullptr; }
        Node(T &&nvalue) : value(nvalue) {
            next = nullptr;
        }
    };

    atomic<Node *> head, tail, base_head;


public:
    lock_free_queue() {
        base_head = tail = head = new Node();
    }

    void enqueue(T v) {
        Node *new_node = new Node(v), *cur_tail, *cur_tail_next;
        while (true) {
            cur_tail = tail.load();
            cur_tail_next = cur_tail->next.load();
            if (!cur_tail_next) {
                if (tail.load()->next.compare_exchange_strong(cur_tail_next, new_node))
                    break;
            } else {
                tail.compare_exchange_strong(cur_tail, cur_tail_next);
            }
        }
        tail.compare_exchange_strong(cur_tail, new_node);
    }

    bool dequeue(T &result) {
        Node *cur_head, *cur_tail, *cur_head_next;
        while (true) {
            cur_head = head.load();
            cur_tail = tail.load();
            cur_head_next = cur_head->next.load();
            if (cur_head == cur_tail) {
                if (!cur_head_next) {
                    return false;
                } else {
                    tail.compare_exchange_strong(cur_head, cur_head_next);
                }
            } else {
                if (head.compare_exchange_strong(cur_head, cur_head_next)) {
                    result = cur_head_next->value;
                    //delete cur_head;
                    return true;
                }
            }
        }
    }

    ~lock_free_queue() {
        Node * ptr = nullptr;
        while (base_head.load() != nullptr) {
            ptr = base_head.load();
            base_head.exchange(base_head.load()->next);
            delete ptr;
        }
    }
};