Multithreaded lock-free queue implementation My partner and I are beginning to believe there could be a desync possibility in the lock free queue we have written, but we would like some fresh eyes on the subject. What are your thoughts on our design?

// nolockqueue.hpp:
#ifndef NOLOCKQUEUE_HPP
#define NOLOCKQUEUE_HPP

template&lt;typename T&gt;
class noLockQueue {
public:
    noLockQueue();
    ~noLockQueue();
    void push(const T dataVar);
    bool pop(T &amp;dataVar);

private:
    struct node {
        node(T dataPassed) : dataVar(dataPassed), next(NULL) {};
        T dataVar;
        node* next;
    };

    node* topOfList;
    node* bottomOfList;
};

template&lt;typename T&gt;
noLockQueue&lt;T&gt;::noLockQueue() {
    topOfList = NULL;
    bottomOfList = NULL;
}

template&lt;typename T&gt;
noLockQueue&lt;T&gt;::~noLockQueue() {
    node* temp;

    while (topOfList != NULL) {
        temp = topOfList-&gt;next;
        delete topOfList;
        topOfList = temp;
    }

    if (bottomOfList != NULL)
        throw("Not All Nodes Deleted - nolockqueue/38/.cpp"); // TODO: Strange error to throw.
}

template&lt;typename T&gt;
void noLockQueue&lt;T&gt;::push(const T dataVar) {
    if (topOfList == NULL) {
        topOfList = bottomOfList = new node(dataVar);
        return;
    } else {
        bottomOfList-&gt;next = new node(dataVar);
        bottomOfList = bottomOfList-&gt;next;
    }
}

template&lt;typename T&gt;
bool noLockQueue&lt;T&gt;::pop(T &amp;dataVar) {
    if (topOfList == NULL)
        return false;

    dataVar = topOfList-&gt;dataVar;
    node* temp = topOfList-&gt;next;
    delete topOfList;
    topOfList = temp;
    return true;
}

#endif


// main.cpp (purely a test unit):
#include &lt;iostream&gt;
#include &lt;thread&gt;

#include "nolockqueue.hpp"
#include &lt;windows.h&gt; // For Sleep().

noLockQueue&lt;int&gt; queue;

void threadFunc() {
    int var = 0;
    Sleep(10);
    while (queue.pop(var)) {
        std::cout &lt;&lt; "\nPopped: " &lt;&lt; var;
        Sleep(1);
    }
}

int main(int argc, char* argv[]) {
    std::thread myThread(threadFunc);

    for (int i = 0; i &lt; 1000; ++i) {
        queue.push(i);
        std::cout &lt;&lt; "\nPushed: " &lt;&lt; i;
        Sleep(1);
    }

    myThread.join();

    std::cin &gt;&gt; argc;
    return 0;
}
This is not a lock-free queue, but a locking-agnostic queue. That means, it is not safe to use on multiple threads. The reason this works in your implementation is because the push calls alter the end of the queue and the pop calls alter the beginning (so conflicts are more or less, avoided).

If you tried adding elements from multiple threads at the same time (for example), you would leak elements.

Since bottomOfList is never changed in the destructor, if it is initialized, you will always get to throw the exception.

Consider splitting pop into a const T&amp; top() const and a void pop(); This would allow for an exception-safe implementation of the operations.