// 链表头节点

private transient volatile Node<E> head;

// 链表尾节点

private transient volatile Node<E> tail;

private static class Node<E> {

    volatile E item;

    volatile Node<E> next;

}

public ConcurrentLinkedQueue() {

    // 初始化头尾节点

    head = tail = new Node<E>(null);

}

public ConcurrentLinkedQueue(Collection<? extends E> c) {

    Node<E> h = null, t = null;

    // 遍历c，并把它元素全部添加到单链表中

    for (E e : c) {

        checkNotNull(e);

        Node<E> newNode = new Node<E>(e);

        if (h == null)

            h = t = newNode;

        else {

            t.lazySetNext(newNode);

            t = newNode;

        }

    }

    if (h == null)

        h = t = new Node<E>(null);

    head = h;

    tail = t;

}

public boolean add(E e) {

    return offer(e);

}

public boolean offer(E e) {

    // 不能添加空元素

    checkNotNull(e);

    // 新节点

    final Node<E> newNode = new Node<E>(e);

    // 入队到链表尾

    for (Node<E> t = tail, p = t;;) {

        Node<E> q = p.next;

        // 如果没有next，说明到链表尾部了，就入队

        if (q == null) {

            // CAS更新p的next为新节点

            // 如果成功了，就返回true

            // 如果不成功就重新取next重新尝试

            if (p.casNext(null, newNode)) {

                // 如果p不等于t，说明有其它线程先一步更新tail

                // 也就不会走到q==null这个分支了

                // p取到的可能是t后面的值

                // 把tail原子更新为新节点

                if (p != t) // hop two nodes at a time

                    casTail(t, newNode);  // Failure is OK.

                // 返回入队成功

                return true;

            }

        }

        else if (p == q)

            // 如果p的next等于p，说明p已经被删除了（已经出队了）

            // 重新设置p的值

            p = (t != (t = tail)) ? t : head;

        else

            // t后面还有值，重新设置p的值

            p = (p != t && t != (t = tail)) ? t : q;

    }

}

public E remove() {

    E x = poll();

    if (x != null)

        return x;

    else

        throw new NoSuchElementException();

}

public E poll() {

    restartFromHead:

    for (;;) {

        // 尝试弹出链表的头节点

        for (Node<E> h = head, p = h, q;;) {

            E item = p.item;

            // 如果节点的值不为空，并且将其更新为null成功了

            if (item != null && p.casItem(item, null)) {

                // 如果头节点变了，则不会走到这个分支

                // 会先走下面的分支拿到新的头节点

                // 这时候p就不等于h了，就更新头节点

                // 在updateHead()中会把head更新为新节点

                // 并让head的next指向其自己

                if (p != h) // hop two nodes at a time

                    updateHead(h, ((q = p.next) != null) ? q : p);

                // 上面的casItem()成功，就可以返回出队的元素了

                return item;

            }

            // 下面三个分支说明头节点变了

            // 且p的item肯定为null

            else if ((q = p.next) == null) {

                // 如果p的next为空，说明队列中没有元素了

                // 更新h为p，也就是空元素的节点

                updateHead(h, p);

                // 返回null

                return null;

            }

            else if (p == q)

                // 如果p等于p的next，说明p已经出队了，重试

                continue restartFromHead;

            else

                // 将p设置为p的next

                p = q;

        }

    }

}

// 更新头节点的方法

final void updateHead(Node<E> h, Node<E> p) {

    // 原子更新h为p成功后，延迟更新h的next为它自己

    // 这里用延迟更新是安全的，因为head节点已经变了

    // 只要入队出队的时候检查head有没有变化就行了，跟它的next关系不大

    if (h != p && casHead(h, p))

        h.lazySetNext(h);

}