A thread safe Q structure that uses lock free push an pop algorithms.

Lock Free Q

/// <summary>
/// A thread safe Q structure that uses lock free push an pop algorithms.
/// </summary>
/// <typeparam name="T">The type to store on the queue.</typeparam>
public class Q<T> 
{
    private Node _head;
    private Node _tail;
    
    /// <summary>
    /// Constructs an empty queue structure
    /// </summary>
    public Q()
    {
        _head = new Node();
        _tail = _head;
    }

    private bool SafeExchange(ref Node location, Node comparand, Node newValue)
    {
        return comparand == Interlocked.CompareExchange(ref location, newValue, comparand);
    }

    /// <summary>
    /// Push a value onto the queue.
    /// </summary>
    /// <param name="value">The value to push onto the queue.</param>
    public void Push(T value)
    {
        var node = new Node {Data = value};
       
        var updated = false;
        while (!updated)
        {
            var oldTail = _tail;
            var oldNext = oldTail.Next;

            if (_tail == oldTail)
            {
                if (oldNext == null)
                {
                    // Try to update the tails next field. If we can't update, then
                    // try again because some other tread updated the tail before we could.
                    updated = SafeExchange(ref _tail.Next, null, node);
                }
                else
                {
                    // Since the tails next field was not null, another thread
                    // is in the middle of enquing a new node, so try and advance
                    // the tail to point to its Next Node
                    SafeExchange(ref _tail, oldTail, oldNext);
                }
            }

            SafeExchange(ref _tail, oldTail, node);
        }
        
    }

    /// <summary>
    /// Pop a value off the queue.
    /// </summary>
    /// <returns>The value that was popped from the queue.</returns>
    public T Pop()
    {
        T result = default(T);

        // loop until we manage to advance the head, removing a node
        var haveAdvancedHead = false;
        while (!haveAdvancedHead)
        {
            var oldHead = _head;
            var oldTail = _tail;
            var oldHeadNext = oldHead.Next;

            //providing that the head field has not changed
            if (oldHead == _head)
            {
                if (oldHead == oldTail)
                {
                    if (oldHeadNext == null)
                    {
                        throw new QueueEmptyException();
                    }

                    // if the head's Next field is non-null and head was equal to the tail
                    // then we have a lagging tail: try and update it
                    SafeExchange(ref _tail, oldTail, oldHeadNext);

                }
                else
                {
                    // grab the item to dequeue, and then try to advance the head reference
                    result = oldHeadNext.Data;
                    haveAdvancedHead = SafeExchange(ref _head, oldHead, oldHeadNext);
                }

            }

            
        }

        return result;
    }
    
    #region [ Node ]

    private class Node
    {
        public Node Next;
        public T Data;

        public override string ToString()
        {
            if( Data != null )
                return Data.ToString();

            return "";
        }
    }

    #endregion
}