1- ConcurrentLinkedQueue介绍
ConcurrentLinkedQueue是线程安全的无锁基于循环CAS算法的无界非阻塞队列
ConcurrentLinkedQueue的特点
- 无锁设计，用循环CAS来保证线程安全性，所以比使用锁的阻塞队列实现具有更高的性能。
- 基于链表实现的无界队列（含有一个head和tail节点）。
- 满足队列的特性，先入先出，当我们put一个元素时是将元素放入队列的尾部，当我们get一个元素是将head节点返回。
- 不允许插入的元素为null。
2- ConcurrentLinkedQueue的定义和结构
继承骨架AbstractQueue，实现了Queue和Serializable接口。
3- ConcurrentLinkedQueue构造函数
无参构造器，初始化一个空的队列，此时head和tail相等而且是一个元素内容为null的Node哨兵节点。
集合构造器，按照集合的顺序将集合所有元素put到队列中，注意当集合为null或者集合含有任何为null的元素都将抛出空指针异常
从上可以看出，在有元素添加时都不能为null，否则抛出异常；当使用集合构造器一定要保证集合及其元素都不能为null。
4- 内部Node类
需要注意的是CAS就有volatile的读写语义同时提供操作的原子性，但是将变量设置为volatile能保证后续操作的可见性。所以CAS和volatile一般在并发环境配合使用。
还需要注意的是，构造函数设置val的值使用的putObject普通写操作，主要是因为Node在方法内部被构造，在插入队列前不用也不应该保证对外可见性。由于next节点是volatile修饰的，当CASNext方法设置成功后，会将整个newNode对象刷新到主内存中，并且实现后续操作的可见性。
对象的字段偏移地址一般设置为对象内部的静态常量长整型。然后再将偏移地址传给Unsafe工具。
还需要注意的是在ConcurrentLinkedQueue实现中为了实现垃圾回收删除的节点，使用了一个小技巧就是将删除的节点的next连接自己，即自连接的节点，这个节点在ConcurrentLinkedQueue的实现中意味着这是一个超前head节点的离队节点，线程如果处于这个节点上将会重新获取新head节点，从head节点向后遍历。
从Node节点的定义可见，这是单向链表构成的队列。
5- 队列的head和tail节点
head节点不为null，但是其元素可以为null，而且保证了获取和删除first节点的时间复杂度为O(1)，由于两跳设置head节点，以及setHead方法不保证设置成功，所以head节点，可能为有效存活的第一个节点，也可能是元素为null的傀儡节点，第一个有效节点可以通过head.succ来到达。
tail节点不为null，但是其元素可以为null，而且保证了插入到尾部的时间复杂度为O(1)，但是通过head遍历到tail的时间复杂度为O(n)。
由于两跳设置tail节点，以及casTail方法不保证设置成功，所以tail节点，可能为有效存活的最后一个节点，也可能不是，最后一个有效节点可以通过tail.succ来到达。
6- offer方法详解
将指定非空元素插入到队列末尾，无界队列，此方法永远返回true，所以不能用返回值判断是否完成插入。
add方法只是简单的调用offer方法
理解offer方法的关键是理解casTail方法的两跳和不保证设置成功
- 即设置tail是同时跳两跳来设置
- casTail方法是CAS操作，但是不是死循环，当调用updateHead方法后不管是否成功都直接返回
以上两种情况将会导致tail节点并不是队列的最后一个元素，即tail节点有可能是最后一个元素也可能是倒数第N个元素，当是倒数第N个元素时需要在循环中向后遍历，保证能找到最后一个元素。
7- poll方法详解
移除队列的head节点，并返回head的item元素，如果队列为空则返回null
updateHead
CAS设置head为p，如果设置成功则将旧的head的next设置为自身引用，使其脱离队列，当有线程发现它和它的后继点节点则会从新的head节点从新检索，当所有线程都不持有此节点的引用时，接下来就会被GC。
返回p的后继节点，如果p.next == p则说明这个节点已经脱离队列了，则直接返回head节点
理解poll方法关键是要理解updateHead方法的两跳和不保证设置成功这个poll方法中updateHead方法是CAS操作，但是不是死循环，当调用updateHead方法后不管是否成功都直接返回，所以在没有其他线程干扰的情况下是会成功的，但是如果有其他线程干扰，则可能设置不成功，就会出现一个节点p，p.next ！= p 而且p.item == null 的情况，这种情况需要对p进行向后遍历p = p.next，直到找到一个p，使得p.item != null此时，此p即为新head。
8- peek方法详解
返回head节点item元素的值，但是不删除head
9- first方法详解
first方法是peek和poll的变种，实现原理和peek方法基本类似，不过first方法是返回head节点，如果head.item不为null，则返回head节点，如果为null则返回null
此方法没有使用peek方法做包装，主要是能减少一次volatile变量的读和一次可能的循环。
10- isEmpty方法
isEmpty方法是通过判断是否存在head节点来判断队列是否为空
11- size方法
返回队列中元素的数量，这只是粗略的估计，因为并不能保证在遍历链表的过程中没有其他线程修改队列，此方法会从head遍历到tail，所以此方法的时间复杂度为O(n)
此方法遍历整个队列统计元素的数量，由于返回值为int类型，所以在方法内部，将整数的最大值作为size的上限。
12- remove方法
删除队列中含有的第一个与指定对象相等的元素，是通过遍历的方法，时间复杂度为O(n)
在删除的过程中，有可能其他线程对队列进行修改。
13- addAll方法
将指定集合添加到队列的尾部
此方法是先在方法内部构建了一个局部的子链表，然后再通过循环CAS的方法添加到外部队列的尾部。
14- 出队节点的GC
出队节点是那种GCRoot（head以及tail ）不可到达的，因为每次并发offer、poll操作总有一个能使casHead或者casTail的CAS成功，虽然被移除的节点可能相互保存着引用（next），比如有移除节点p和q（q != p），则可能有p.next == q 而且p.item == null 的情况，但是对于GCRoot来说都是不可到达的，所以在GC的时候会被标记为垃圾，这也是JDK作者Doug Lea在文档中一直强调的这是在一个具有垃圾回收机制的环境的改进算法。
原文：
This is a modification of the Michael & Scott algorithm, adapted for a garbage-collected environment, with support for interior node deletion (to support remove(Object)). Forexplanation, read the paper.
15- 方法列表
16- 总结：
- ConcurrentLinkedQueue是使用循环CAS的非阻塞无界先入先出的队列，性能高于阻塞队列。
- 通过同时跳两跳来设置head和tail，来减少对volatile变量的写操作（volatile变量的写操作需要刷新CPU缓存，影响性能）来优化性能。
- 新建一个Node节点，使用putObject方法，而不是使用volatile变量写的方式，用一次普通对象写换取volatile变量写的性能提升。
- offer、poll、peek、first、isEmpty方法的时间复杂度为O(1)
- size、remove方法的时间复杂度为O(n)，而且是弱一致性的。
- iterator迭代器方法是弱一致性的。
- 不允许插入的元素为null。
