jdk1.7.0_79
队列是一种非常常用的数据结构，一进一出，先进先出。
在Java并发包中提供了两种类型的队列，非阻塞队列与阻塞队列，当然它们都是线程安全的，无需担心在多线程并发环境所带来的不可预知的问题。为什么会有非阻塞和阻塞之分呢？这里的非阻塞与阻塞在于有界与否，也就是在初始化时有没有给它一个默认的容量大小，对于阻塞有界队列来讲，如果队列满了的话，则任何线程都会阻塞不能进行入队操作，反之队列为空的话，则任何线程都不能进行出队操作。而对于非阻塞无界队列来讲则不会出现队列满或者队列空的情况。它们俩都保证线程的安全性，即不能有一个以上的线程同时对队列进行入队或者出队操作。
非阻塞队列：ConcurrentLinkedQueue
阻塞队列：ArrayBlockingQueue、LinkedBlockingQueue、……
本文介绍非阻塞队列——ConcurentLinkedQueue。
首先查看ConcurrentLinkedQueue默认构造函数，观察它在初始化时做了什么操作。
//ConcurrentLinkedQueue public ConcurrentLinkedQueue() { head = tail = new Node (null); } 可以看到ConcurrentLinkedQueue在其内部有一个头节点和尾节点，在初始化的时候指向一个节点。
对于入队（插入）操作一共提供了这么2个方法（实际上是一个）：
|
|
|
|
| 入队（插入） | add(e)（其内部调用offer方法，） | offer(e)（插入到队列尾部，当队列无界将永远返回true） |
1 //ConcurrentLinkedQueue#offer 2 public boolean offer(E e) { 3 checkNotNull(e); //入队元素是否为空，不允许Null值入队 4 final Node newNode = new Node (e); //将入队元素构造为Node节点 5 /*tail指向的是队列尾节点，但有时tail.next才是真正指向的尾节点*/ 6 for (Node t = tail, p = t;;) { 7 Node q = p.next; 8 if (q == null) { //此时p指向的就是队列真正的尾节点 9 if(p.casNext(null, newNode)) { //cas算法,p.next = newNode10 if (p != tail) //将tail指向队列尾节点11 casTail(t, newNode);12 return true;13 }14 }15 else if (p == q) 16 p = (t != (t = tail)) ? t : head;17 else18 p = (p != t && t != (t = tail)) t : q;19 }20 } offer入队过程如下图所示：
① 队列中没有元素，第一次入队操作： 进入循环体： t = tail; p = tail; q = p.next = null;
判断尾节点的引用p是否指向的是尾节点（if(q == null)）->是：
CAS算法将入队节点设置成尾节点的next节点（p.casNext(null, newNode)） 判断tail尾节点指针的引用p是否大于等于1个next节点（if (p != t)）->否 返回true
② 队列中有元素，进行入队操作：
1) 第一次循环：
t = tail; p = tail; q = p.next = Node1;
判断tail尾节点指针的引用p是否指向的是尾节点（if(q == null)）->否
判断tail尾节点指针的引用p是否指向的是尾节点（else if (p == q)）->否 将tail尾节点指针的引用p向后移动（p = (p != t && t != (t = tail)) ? t : q;）->p = Node1
2) 第二次循环：
t = tail; p = Node1; q = p.next = null;
判断tail尾节点指针的引用p是否指向真正的尾节点（if(q == null)）->是：
CAS算法将入队节点设置成尾节点的next节点（p.casNext(null, newNode)） 判断tail尾节点指针的引用p是否大于等于1个next节点(if (p != t))->是： 更新tail节点（casTail(t, nextNode)） 返回true
入队的操作都是由CAS算法完成，显然是为了保证其安全性。整个入队过程首先要定位出尾节点，其次使用CAS算法将入队节点设置成尾节点的next节点。整个入队过程首先要定位队列的尾节点，如果将tail节点一直指向尾节点岂不是更好吗？每次即tail->next = newNode;tail = newNode;这样在单线程环境来确实没问题，但是，在多线程并发环境下就不得不要考虑线程安全，每次更新tail节点意味着每次都要使用CAS更新tail节点，这样入队效率必然降低，所以ConcurrentLinkedQueue的tail节点并不总是指向队列尾节点的原因就是减少更新tail节点的次数，提高入队效率。
对于出队（删除）操作一共提供了这么1个方法：
1 //ConcurrentLinkecQueue#poll 2 public E poll() { 3 restartFromHead: 4 for (;;) { 5 for (Node h = head, p = h, q;;) { 6 E item = p.item; 7 if (item != null && p.casItem(item, null)) { 8 if (p != h) 9 updateHead(h, ((q = p.next) != null) ? q : p);10 return item;11 } 12 else if ((q = p.next) == null) {13 updateHead(h, p);14 return null;15 }16 else if (p == q)17 continue restartFromHead;18 else19 p = q;20 }21 }22 } 以上面队列中有两个元素为例：(注意，初始时，head指向的是空节点)
出队（删除）：
1） 第一次循环： h = head; p = head; q = null; item = p.item = null; 
判断head节点指针的引用是否不是空节点（if (item != null)）->否，即是空节点
判断（暂略） 判断（暂略） 将head节点指针的引用p向后移动（p = q）2） 第二次循环：
h = head; p = q = Node1; q = Node1; item = p.item = Node1.item;
判断head节点指针的引用p是否不是空节点（if (item != null)）->是，即不是空节点：
判断head节点指针与p是否指向同一节点（if (p != h)）->否： 更新头节点（updateHead(h, ((q = p.next) != null) ? q : p)） 返回item
实际上继续出队会发现，出队和入队类似，不会每次出队都会更新head节点，原理也和tail一样。
对于ConcurrentLinkedQueue#size方法将会遍历整个队列，可想它的效率并不高，如果一定需要调用它的size方法，特别是for循环时，我建议一下写法：for (int i = 0, int size = concurrentLinkedQueue.size(); i < size;i++)
因为这能保证不用每次循环都调用一次size方法遍历一遍队列。