在多线程编程环境下并发安全队列是不可或缺的一个重要工具类，为了实现并发安全可以有两种方式：一种是阻塞式的，例如：LinkedBlockingQueue；另一种即是我们将要探讨的非阻塞式，例如：ConcurrentLinkedQueue。相比较于阻塞式，非阻塞的最显著的优点就是性能，非阻塞式算法使用CAS来原子性的更新数据，避免了加锁的时间，同时也保证了数据的一致性。
简单介绍
ConcurrentLinkedQueue是一个基于链接节点的无界无锁线程安全队列，它采用先进先出的规则对节点进行排序，当我们添加一个元素的时候，它会添加到队列的尾部，当我们获取一个元素时，它会返回队列头部的元素。它采用了“wait－free”算法来实现，该算法在Michael & Scott算法上进行了一些修改。
ConcurrentLinkedQueue中的方法不多，其中最主要的两个方法是：offer(E)和poll()，分别实现队列的两个重要的操作：入队和出队。
方法
含义
offer(E)
插入一个元素到队列尾部
poll()
从队列头部取出一个元素
add(E)
同offer(E)
peek()
获取头部元素，但不删除
isEmpty()
判断队列是否为空
size()
获取队列长度(元素个数)
contains(Object)
判断队列是否包含指定元素
remove(Object)
删除队列中指定元素
toArray(T[])
将队列的元素复制到一个数组
iterator()
返回一个可遍历该队列的迭代器
为什么针对ConcurrentLinkedQueue的整个入队/出队/删除都是不需要锁的。
- 如果多个线程同时访问其中任一个方法（offer/poll/remove）都是无需加锁而且线程安全的
- 由于remove方法不修改ConcurrentLinkedQueue的结构，所以跟其他两个方法都不会有冲突
- 如果同时两个线程，一个入队，一个出队，在队列不为NULL的情况下是不会有任何问题的，因为一个操作tail，一个操作head，完全不相关。但是如果队列为NULL时还是会发生冲突的，因为tail==head。
- 如果出队线程发现tail的next不为NULL，那么就会感知到当前有一个线程在执行入队操作，所以出队线程就会帮助入队线程完成入队操作，而且每个操作都是通过CAS保证原子性更新，所以就算同时两个线程，一个入队，一个出队也不会发生冲突。
综上，ConcurrentLinkedQueue最终实现了无锁队列。
使用场景
ConcurrentLinkedQueue适合在对性能要求相对较高，同时对队列的读写存在多个线程同时进行的场景，即如果对队列加锁的成本较高则适合使用无锁的ConcurrentLinkedQueue来替代。下面我们来简单对比下ConcurrentLinkedQueue与我们常用的阻塞队列LinkedBlockingQueue的性能。
表1：入队性能对比
线程数
ConcurrentLinkedQueue耗时(ms)
LinkedBlockingQueue耗时(ms)
5
22
29
10
50
59
20
99
112
30
139
171
测试数据：N个线程，每个线程入队10000个元素。
