ConcurrentLinkedQueue

在JAVA多线程应用中，队列的使用率很高，多数生产者和消费者的首选数据结构就是队列（先进先出）。JAVA提供的线程安全队列分为阻塞队列和非阻塞队列，其中阻塞队列的典型例子就是BlockingQueue，而非阻塞队列的典型例子就是ConcurrentLinkedQueue，在实际应用中要根据实际需要来选取。

　　使用阻塞算法的队列可以用一个锁（入队和出队用同一把锁）或两个锁（入队和出队用不同的锁）等方式来实现；非阻塞的实现方式则可以使用循环CAS的方式来实现。

ConcurrentLinkedQueue是一个不限制大小的非阻塞队列，保存了当前链表的头指针head和尾指针tail。每个节点Node由节点元素item和指向下一个节点的引用next组成。节点之间通过next关联起来，从而组成一张链表结构的队列。链表中最后加入的节点称为尾节点。

private transient volatile Node<E> head = new Node<E>(null, null);

 /** Pointer to last node on list **/
 private transient volatile Node<E> tail = head;

1、头指针head不允许为空，数据内容永远是null。链表的第一个有效元素是最早入队的元素，即head.next。

2、尾指针tail并不一定指向尾指针，所以两者之间还是有区别的。

入队列

入队列就是将入队节点添加到队列的尾部

通过快照观察，入队其实只是做了两件事情：
一是将入队节点设置成当前队尾节点的下一个节点。
二是更新tail节点，如果tail节点的next节点为null，则将入队节点设置成tail的next节点，如果tail节点的next节点不为空，则将入队节点设置为tail节点。

public boolean offer(E e) {
        if (e == null) throw new NullPointerException();
　　　　　//入队前，创建入队节点
        Node<E> n = new Node<E>(e, null);
        //死循环，入队不成功则反复入队
        for (;;) {
            Node<E> t = tail;
            //tail的next节点
            Node<E> s = t.getNext();
            if (t == tail) {
　　　　　　　　　//tail的next节点为空
                if (s == null) {
　　　　　　　　　　　　//表示t是尾节点，将t的next节点指向入队节点
                    if (t.casNext(s, n)) {
　　　　　　　　　　　　　　更新tail节点，允许失败
                        casTail(t, n);
                        return true;
                    }
                } else {
                    casTail(t, s);
                }
            }
        }
    }

从源码的角度来看：入队过程主要就是定位出尾节点，然后使用CAS算法将入队节点设置成尾节点的next节点，如不成功则重试。

设置tail节点所使用的CAS算法：

private boolean casTail(Node<E> cmp, Node<E> val) {
        return tailUpdater.compareAndSet(this, cmp, val);
    }