Java ~ Executor ~ LinkedBlockingQueue【源码】
一 LinkedBlockingQueue（链接阻塞队列）类源码及机制详解
类
LinkedBlockingQueue（链接阻塞队列）类是BlockingQueue（阻塞队列）接口的主要实现类之一，也是Executor（执行器）框架最常搭配使用的实现之一，采用链表的方式实现。相比基于数组的实现，基于链表的实现有着更高的并发量，但是在绝大多数的并发应用中其性能的可预见性较差（即难以预测性能可以达到什么程度）。由于需要额外创建节点（节点是元素的容器，也是队列的组成单位）用于容纳元素的原因，在需要长时间高效并发地处理大批量数据时，对于GC可能存在较大影响（多出了分配内存创建节点以及回收节点的消耗）。LinkedBlockingQueue（链接阻塞队列）类是一个标准的FIFO队列，新元素会从队列的尾部插入/放置（即尾插法），而元素的移除/拿取则会在队列的头部进行。
LinkedBlockingQueue（链接阻塞队列）类不允许存null值，或者说BlockingQueue（阻塞队列）接口的所有的实现类都不允许存null值。null被作为poll()及peek()方法（两个方法由Queue（队列）接口定义）作为队列不存在元素的标记值，因此所有的BlockingQueue（阻塞队列）接口实现类都不允许存null值。
LinkedBlockingQueue（链接阻塞队列）类不同于我们常规使用的Collection（集）接口的实现类，没有扩容的说法，即其容量会在创建时确定，之后不会再发生改变。如此一来，其内部的实现结构便相对来说简洁的多。但这就使得我们必须根据业务的实际情况及资源的硬性限制来选择具体的容量…可一个很现实的问题是早期选定的容量又往往很难支持后期的发展（不论是业务还是资源）…这也算是个令人很头疼的问题了。
LinkedBlockingQueue（链接阻塞队列）类可同时作为有界及无界队列使用。如果在创建LinkedBlockingQueue（链接阻塞队列）类对象（下文简称队列）时没有指定具体的容量，那其就是一个无界队列。话虽如此，但实际上不存在真正意义上的无界队列。所谓的无界队列其实是在未指定具体容量时默认赋予一个最大容量，在LinkedBlockingQueue（链接阻塞队列）类的实现中这个值是int类型的最大值，即Integer.MAX_VALUE（2 ^ 31 - 1）。我们并不推荐使用无界队列，因为它的容量实在太大了，一旦元素的移除/拿取速率低于元素的插入/放置速率，则很容易导致元素堆积从而造成OOM。因此在实际的开发中，还是推荐指定容量的有界队列用法，并根据业务的实际场景及资源的硬性限制选择合适的容量大小。
LinkedBlockingQueue（链接阻塞队列）类是线程安全的，或者说BlockingQueue（阻塞队列）接口的所有的实现类都是线程安全的（接口的定义中强制要求实现类必须线程安全）。LinkedBlockingQueue（链接阻塞队列）类采用一种被称为双锁的线程安全机制（下文简称双锁机制）来保证同步，通俗的讲就是LinkedBlockingQueue（链接阻塞队列）类在内部创建了放置与拿取两把ReentrantLock（可重入）类对象锁分别用于管理插入/放置及移除/拿取两类方法的同步（即插入/放置方法只会受放置锁的保护，而移除/拿取方法只会受拿取锁的保护），从而在保证线程安全的同时有效的提高并发，该知识点的详细内容会在下文详述。
LinkedBlockingQueue（链接阻塞队列）类的迭代器是弱一致性（即可能迭代到已经队列移除的元素）。弱一致性迭代器可以有效兼容并发的使用环境，使得插入/放置及移除/拿取方法的执行不会导致迭代的中断，该知识点的详细内容会在下文详述。
LinkedBlockingQueue（链接阻塞队列）类虽然与BlockingQueue（阻塞队列）接口一样都被纳入Executor（执行器）框架的范畴，但同时是Collection（集）框架的成员。
/**
* An optionally-bounded {@linkplain BlockingQueue blocking queue} based on linked nodes. This queue orders elements FIFO (first-in-first-out).
* The <em>head</em> of the queue is that element that has been on the queue the longest time. The <em>tail</em> of the queue is that element
* that has been on the queue the shortest time. New elements are inserted at the tail of the queue, and the queue retrieval operations obtain elements
* at the head of the queue. Linked queues typically have higher throughput than array-based queues but less predictable performance in most
* concurrent applications.
* 可选择边界BlockingQueue的基础在于链接节点（即该队列是用链表实现的）。这个队列排序元素FIFO（先入先出）（标准的队列实现）。队列的
* head（即头节点）是队列中存在时间最长的元素。队列的tail（即尾节点）是队列中存在时间最短的元素。新元素从队列的尾部插入，并且队列检索
* 操作获取队列头部的元素。链表队列通常拥有相比数组基础队列更高的并发量，但是在绝大多数的并发应用中其性能的可预见性较差。
* <p>
* The optional capacity bound constructor argument serves as a way to prevent excessive queue expansion. The capacity, if unspecified, is equal to
* {@link Integer#MAX_VALUE}. Linked nodes are dynamically created upon each insertion unless this would bring the queue above capacity.
* 可选容量边界构造器参数用于（充当）防止过度的的队列扩大的方式。该容量如果未指定则相当于int类型的最大值（因此本质上没有真正意义上的无
* 界链接，只是这个界限非常大而已）。链接节点会在每次插入后动态地创建，除非这会导致队列超过容量。
* <p>
* This class and its iterator implement all of the <em>optional</em> methods of the {@link Collection} and {@link Iterator} interfaces.
* 这个类和它的迭代器实现Collection和Iterator接口的全部可选方法（可选方法...什么意思？）。
* <p>
* This class is a member of the <a href="{@docRoot}/../technotes/guides/collections/index.html"> Java Collections Framework</a>
* 这个类是Java集框架的一个成员
*
* @param <E> the type of elements held in this collection 元素在这个集中持有的类型
* @author Doug Lea
* @Description: 链接阻塞队列类
* @since 1.5
*/
public class LinkedBlockingQueue<E> extends AbstractQueue<E> implements BlockingQueue<E>, java.io.Serializable {
private static final long serialVersionUID = -6903933977591709194L;
/*
* A variant of the "two lock queue" algorithm. The putLock gates entry to put (and offer), and has an associated condition for waiting puts. Similarly
* for the takeLock. The "count" field that they both rely on is maintained as an atomic to avoid needing to get both locks in most cases. Also, to minimize
* need for puts to get takeLock and vice-versa, cascading notifies are used. When a put notices that it has enabled at least one take, it signals taker.
* That taker in turn signals others if more items have been entered since the signal. And symmetrically for takes signalling puts. Operations such as
* remove(Object) and iterators acquire both locks.
* "两锁队列"算法的变种。放置锁把关条目的存入（put()及offer()方法），并存在一个等待放置的关联条件。拿取锁与之相似。它们（指两个锁）都依赖的
* count字段被维持为原子性，以避免在大部分情况中需要获取两个锁（意思是因为对count字段值的修改是原子操作，这样就不要同时在放置与拿取并发的
* 情况下同时获取两个锁来保持count字段的原子性）。此外，为了尽量少在放置时获取拿取锁，反之亦然（即为了尽量少的在拿取时获取放置锁），使用了
* 级联通知。当一次放置注意到它已经启用了至少一次取值时，它就向拿取者发出信号（即如果发现有线程调用了take()方法而被挂起，则对这些线程发送信
* 号，即唤醒后继续执行拿取）。如果更多的条目在信号之后进入，则拿取者转而对其它（拿取者）发送信号。并且拿取者会对称地向放置者发送信号。类似
* 于remove()及迭代器的操作会获取两把锁。
*
* Visibility between writers and readers is provided as follows:
* 读写之间的可见性如下所示：
* Whenever an element is enqueued, the putLock is acquired and count updated. A subsequent reader guarantees visibility to the enqueued Node by
* either acquiring the putLock (via fullyLock) or by acquiring the takeLock, and then reading n = count.get(); this gives visibility to the first n items.
* 每当元素入队时，获取放置锁并更新总数。随后拿取者要么通过获取放置锁（通过fullyLock()）（fullyLock()的作用是同时获取放置锁和拿取锁，因此本质
* 上都是获取拿取锁），要么通过获取拿取锁来保证入队节点的可见性（即确保入队的节点一定能被拿取者读取到...这点其实不用太在意，因为只要是正确的
* 使用锁都是能够保证可见性的），并通过n = count.get()读取当前队列节点的总数；这样就能够提供前n个条目的可见性（拿取和放置是两把锁，因此二者其
* 实是可以并发的（虽然可以并发，但同一时间最多只要一个拿取者和一个放置者），因此在拿取的时候，只能保证在一开始读取到的n个节点的可见性，对于
* 在拿取过程中新增的节点是无法保证可见性的）。
* To implement weakly consistent iterators, it appears we need to keep all Nodes GC-reachable from a predecessor dequeued Node. That would cause
* two problems:
* 为了实现弱一致的迭代器（如果是强一致性的迭代器，则应该是不允许出队/移除的，因为这可能会导致迭代的中断），看起来我们需要保持所有节点GC
* 都可以从一个前驱已出队节点可达。这会造成两个问题（即当前的实现存在这两种情况，并且没有解决或只解决了一部分）：
* - allow a rogue Iterator to cause unbounded memory retention
* - 允许非法迭代器造成无限制的内存保留（即一个已经出队/移除的节点短期/长期/永久（具体看迭代器的调用频率，频率高就是短期，低就是长期，不调用
* 就是永久，直至整个迭代器被回收）的保存在迭代器中）；
* - cause cross-generational linking of old Nodes to new Nodes if a Node was tenured while live, which generational GCs have a hard time dealing with,
* causing repeated major collections. However, only non-deleted Nodes need to be reachable from dequeued Nodes, and reachability does not necessarily
* have to be of the kind understood by the GC. We use the trick of linking a Node that has just been dequeued to itself. Such aself-link implicitly means
* to advance to head.next.
* - 如果节点在老年代中存活（即已被出队/移除节点还未被GC回收），会导致新老节点之间的跨带引用（即已出队/移除的老节点还依然引用着队列中的新节点（
* 队列是按顺序入队的，先入队的自然比较老，这不难理解）），这种代GC是很难处理的，会导致重复的老年代GC。此外，只有未删除节点（即还在队列中的节
* 点）需要从已出队节点可达，并且可达性也不一定必须是GC理解的类型。我们使用的技巧是将一个刚刚出队（不包含移除，只表示正常的队列出队）的节点链
* 接到它自己（这么做就断开了出队（只是出队，没有移除）节点与队列中节点的引用，保证了出队节点的正常回收，之所以不设置为null是因为null是尾节点的标
* 志位））。这种自我链接隐含的意思是前进到头部（即从队列的头部开始重新迭代，这与迭代器有关。但话虽如此，将后继节点的引用设置为自身只对正常出队
* 的节点有效，对于移除节点是没有这一步操作的，因为对于中途移除的节点为了保证迭代器的弱一致性不可以断开与后继节点的引用）。
*/
...
}
字段
capacity（容量） —— 用于记录队列的容量，如果在创建时未指定则默认为Integer.MAX_VALUE（2 ^ 31 - 1）。这种情况下的队列也被成为无界队列。该字段被final关键字修饰，因此可知队列的容量是不可变的。
/**
* The capacity bound, or Integer.MAX_VALUE if none
* 容量边界（即允许存放元素个数的最大值），如果在构造对象时没有传入则为int类型的最大值。
*/
private final int capacity;
count（总数） —— 用于记录队列已容纳的元素总数。该字段被设计为AtomicInteger（原子整数）类型，目的是为了使其值呈原子性变化（即对其的修改是原子性操作），而更为核心的原因则与LinkedBlockingQueue（链接阻塞队列）类的“双锁”线程安全机制有关。令count（总数）字段值的呈原子性变化可避免在绝大多数操作中同时获取两个锁，从而提高并发。
put()方法中存在对count（总数）字段的一段英文注释，其中首句翻译过来是“注意count应在等待/延缓保护中使用，即使不受锁的保护”。我的英文能力有限，不是很理解“等待/延缓保护”的含义。但通过结合上下文以及count（总数）字段自身的特性，个人猜测这句话的意思应该是“count应该在一个可以存在并发但并发情况不是很严重的环境中使用，即使没有锁的保护”。count（总数）虽然是AtomicInteger（原子整数）类型的字段，但AtomicInteger（原子整数）类内部使用的是乐观锁机制。众所周知乐观锁并不适合在并发很严重的环境中使用，会造成大量CPU资源的浪费，这也是为什么在整个LinkedBlockingQueue（链接阻塞队列）类中count（总数）字段都至少会在一个锁的保护下执行修改操作的原因。虽然因为LinkedBlockingQueue（链接阻塞队列）类的双锁机制，一个锁并无法完全的避免并发（插入/放置时不阻塞移除/拿取，拿取时不阻塞放置），但却大大降低了并发的程度，使得最多只会存在两个线程（放置者及拿取者各一个）同时操作count（总数）字段。
/**
* Current number of elements
* 当前元素数量
*/
private final AtomicInteger count = new AtomicInteger();
head（头） —— 用于持有队列头节点（元素的容器，也是链表的基本组成单位，其类结构会在下文详述）的引用。在LinkedBlockingQueue（链接阻塞队列）类中，无论是否存在元素，都会将一个空节点（即未容纳元素的节点）作为队列的头节点，目的是为了在插入/放置方法的逻辑代码的实现中免除头节点的判断（如果没有默认头节点的话，新增第一个元素的时候就要特殊处理）以减少if分支。在基于链表实现的API中这是一种很常见做法，例如AQS的阻塞队列也是如此。
/**
* Head of linked list.
* Invariant: head.item == null
* 链接列表的头节点。
* 不变量：头节点的item（项目）字段值为null（即永远为null）
*/
transient Node<E> head;
last（尾） —— 用于持有队列尾节点的引用。在LinkedBlockingQueue（链接阻塞队列）类中尾结点由于不存在后继节点，因此其不持有后继节点的引用，故而可将此作为当前节点是否是尾结点的判断依据。
/**
* Tail of linked list.
* 链接列表的尾结点。
* Invariant: last.next == null
* 不变量：尾结点的next（后继）字段值为null
*/
private transient Node<E> last;
takeLock（拿取锁） —— 用于持有一个ReentrantLock（可重入锁）类对象（下文简称拿取锁）的引用。拿取锁主要用于在队列执行移除/拿取操作时进行同步以确保线程安全。
/**
* Lock held by take, poll, etc
* 通过take()，poll()等方法持有的锁（即出队时持有的锁）
*/
private final ReentrantLock takeLock = new ReentrantLock();
notEmpty（非空） —— 用于持有一个Condition（条件）类对象（下文简称非空/拿取者条件）。非空/拿取者条件通过拿取锁创建得来，用于管理因为队列中不存在元素而无法执行移除/拿取操作的线程（下文简称拿取者）。
/**
* Wait queue for waiting takes
* 等待拿取的等待/条件队列
*/
private final Condition notEmpty = takeLock.newCondition();
takeLock（放置锁） —— 用于持有一个ReentrantLock（可重入锁）类对象（下文简称放置锁）的引用。放置锁主要用于在队列执行插入/放置操作时进行同步以确保线程安全。
/**
* Lock held by put, offer, etc
* 通过put()，offer()等方法持有的锁（即入队时持有的锁）
*/
private final ReentrantLock putLock = new ReentrantLock();
notFull（非满） —— 用于持有一个Condition（条件）类对象（下文简称非满/放置者条件）。非满/放置者条件通过放置锁创建得来，用于管理因为队列容量已满而无法执行插入/放置操作的线程（下文简称放置者）。
/**
* Wait queue for waiting puts
* 等待放置的等待/条件队列
*/
private final Condition notFull = putLock.newCondition();
构造方法
public LinkedBlockingQueue() —— 用于创建一个无界队列。虽说叫无界队列，但实际就是一个容量非常大的队列而已。在LinkedBlockingQueue（链接阻塞队列）类的实现中这个容量是int类型的最大值，即Integer.MAX_VALUE（2 ^ 31 - 1）。不推荐使用该构造方法创建队列，当元素的移除/拿取速率低于元素的插入/放置速率时很容易导致元素堆积而造成OOM。
/**
* Creates a {@code LinkedBlockingQueue} with a capacity of {@link Integer#MAX_VALUE}.
* 创建一个容量为int类型最大值的对象（也就是所谓的无限队列，实际上是一个长度非常大的队列罢了）。
*/
public LinkedBlockingQueue() {
this(Integer.MAX_VALUE);
}
public LinkedBlockingQueue(int capacity) —— 用于创建一个有界队列。推荐使用该方法创建队列，队列的容量应该根据程序的实际使用情况来指定。方法中会创建一个空节点作为队列的默认头/尾节点。
/**
* Creates a {@code LinkedBlockingQueue} with the given (fixed) capacity.
* 创建一个指定容量的链接阻塞队列
*
* @param capacity the capacity of this queue 队列的容量
* @throws IllegalArgumentException if {@code capacity} is not greater than zero 如果容量不比0大
*/
public LinkedBlockingQueue(int capacity) {
if (capacity <= 0) throw new IllegalArgumentException();
this.capacity = capacity;
// 创建一个空节点作为头节点和尾节点。
last = head = new Node<E>(null);
}
public LinkedBlockingQueue(Collection<? extends E> c) —— 用于创建一个含有初始元素的无界队列。该构造方法会在创建一个无界队列后将指定集中的元素尽数加入队列中，元素的入队顺序与集的迭代器顺序一致。
/**
* Creates a {@code LinkedBlockingQueue} with a capacity of {@link Integer#MAX_VALUE}, initially containing the elements of the given collection, added
* in traversal order of the collection's iterator.
* 创建一个容量为int最大值的链接阻塞队列，最初包含指定集的元素，按集的迭代器顺序新增（即按集的迭代器的顺序将元素添加到队列中）。
*
* @param c the collection of elements to initially contain 为了最初包含的元素集
* @throws NullPointerException if the specified collection or any of its elements are null 如果指定元素集中有任何元素为null
*/
public LinkedBlockingQueue(Collection<? extends E> c) {
// 容量为int类型的最大值。
this(Integer.MAX_VALUE);
// 加放置锁，将指定集中的所有元素都添加到队列中。
final ReentrantLock putLock = this.putLock;
putLock.lock(); // Never contended, but necessary for visibility
try {
int n = 0;
for (E e : c) {
if (e == null)
throw new NullPointerException();
// 如果队列满了，也要抛出异常。
if (n == capacity)
throw new IllegalStateException("Queue full");
enqueue(new Node<E>(e));
++n;
}
// 设置总数。
count.set(n);
} finally {
putLock.unlock();
}
}
我们可以在上述的源码中发现将指定集中的元素存入队列的整个过程是加了锁的，而源码给出的英文注释是“没有竞争，但为了可见性有必要（加锁）”。其中本人对可见性是可以理解的（如果理解没有错的话）：如果在过程中没有加锁，就会出现获取到节点但获取不到元素的情况（即节点中不包含元素）。为什么会出现这样的问题呢？这是因为在Java中对象的创建不是原子操作，整个过程按顺序大致可分为以下三部分：
- 实例化（分配内存）；
- 初始化（执行构造方法）；
- 引用赋值（令变量持有对象的引用）。
但现实中由于指令重排序的原因，具体在执行中顺序就可能变成：
- 实例化（分配内存）；
- 引用赋值（令变量持有对象的引用）；
- 初始化（执行构造方法）。
这就意味着加入到队列中的节点可能是个空节点（即还未完成初始化的过程）。如此一来，如果有线程在队列构造方法执行结束后获取元素，则其获取到的节点中元素完全可能是空的，因此整个过程必须在锁的保护下执行。锁的存在虽然无法避免同步块中的指令重排序，但可以避免其重排序到同步块外（这就使得节点的初始化一定会在同步块中完成），因此使得队列创建完成后进行获取的线程获取到的节点一定是完整的（存在元素的）。
如果上述我的理解都是对的，那就有一个讲不通的地方就是既然对象的创建不是原子操作，那完全可能存在有线程向一个未执行初始化（或未执行完初始化）的队列保存元素的可能，如此应该是可能存在竞争的，而不是英文注释中说的“没有竞争”，这也是我目前尚未完全理解的地方…当然，也可能是我对可见性的理解本就是错的，希望有懂的同学能在评论区不吝赐教，本人万分感谢。
方法
boolean offer(E e) —— 提供 —— 用于插入/放置一个元素。该方法是插入/放置操作“特殊值”形式的定义。当队列容量已满而无法容纳插入的元素时会返回false。当使用限定了容量的队列时更适合使用此方法，因为不会因为频繁的触及容量上限而不断抛出异常。
offer()方法会使用DCL（双重检查锁）机制进行两次判断，分别在非同步于同步两种唤醒下执行，以确定队列能否放置/插入（即容量是否已满）。之所以要进行两次判断是因为第一次非同步的判断能够过滤掉大部分线程，而只有少数通过了一级判断的线程才需要在同步的环境下再次判断并根据判断结果选择是否执行插入/放置。这种做法大大提高了offer()方法的并发性能。
所有的插入/放置方法中都包含了两步固定操作（这两步操作下文不会再提及）：一是当元素成功入队后，如果当前队列还有剩余容量，则从非满/放置者队列中唤醒一个放置者来执行插入/放置。该操作确保了当队列存在剩余容量时挂起的放置者会被持续唤醒；二是当元素成功入队后如果发现此次放置/插入操作执行前队列容量为0，则唤醒一个拿取者进行执行拿取。该操作保证了当队列存在元素时（此次放置/插入操作执行后会存在一个元素）挂起的拿取者会被持续唤醒。而之所以只在该条件下执行是因为当队列中存在元素的情况下拿取者是不会挂起的。
/**
* Inserts the specified element at the tail of this queue if it is possible to do so immediately without exceeding the queue's capacity, returning {@code true}
* upon success and {@code false} if this queue is full. When using a capacity-restricted queue, this method is generally preferable to method {@link BlockingQueue#add add},
* which can fail to insert an element only by throwing an exception.
* 如果可以在不超出队列容量的情况下立即执行，则在队列的尾部插入指定的元素，成功之后返回true，如果队列满了（插入前）则返回false。当只有一个容量
* 受限的队列，该方法相比add()方法更好，因为其（指add()方法）会在插入一个元素失败时抛出一个异常。
*
* @throws NullPointerException if the specified element is null 如果指定元素为null
*/
@Override
public boolean offer(E e) {
if (e == null) throw new NullPointerException();
final AtomicInteger count = this.count;
// 进行一次外判断，如果容量已满则直接返回false。
if (count.get() == capacity)
return false;
int c = -1;
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
// 如果满足条件则直接进行一次入队，并唤醒一个挂起的放置者。
if (count.get() < capacity) {
enqueue(node);
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
}
} finally {
putLock.unlock();
}
// 如果计数（快照）为0，意味着队列不再是空队列了，可以唤醒被阻塞的拿取者了。之所以只在为0的时候唤醒是因为其它数字意味着队列不为空，这
// 种情况下拿取者是不会被阻塞的的。
if (c == 0)
signalNotEmpty();
// 如果成功放置则返回true。
return c >= 0;
}
public void put(E e) —— 放置 —— 用于插入/放置一个元素。该方法是插入/放置操作“阻塞”形式的定义。当队列容量已满而无法容纳插入/放置的元素时会挂起，直至队列空出容量后执行。具体的做法是在放置锁的保护下判断当前队列的容量是否已满，是则将当前放置者挂起（通过调用非满/放置者条件的await()方法实现），直至因为中断/信号等原因被唤醒；否则直接执行插入/放置操作。关于对队列容量的判断需要在循环中执行，因为即使放置者被唤醒并再次获取了锁，也不能保证当前队列存在剩余容量。这是由于可能已经有其它放置者先一步获得放置锁并完成了插入/放置，导致队列容量再次满溢（这种情况下获得先一步获得放置锁的放置者会是外来的），因此必须在放置锁的保护下重复的判断。
/**
* Inserts the specified element at the tail of this queue, waiting if necessary for space to become available.
* 在队列的尾部插入指定的元素（尾插法），如果必要等待空间变的可用（即如果容量满了就先将自身加入条件队列中挂起）
*
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
@Override
public void put(E e) throws InterruptedException {
if (e == null) throw new NullPointerException();
// Note: convention in all put/take/etc is to preset local var holding count negative to indicate failure unless set.
// 注意：惯例是所有put/take等操作会预备/事先准备本地变量var保持计数为负以表示操作失败，除非设置。
// c是操作是否成功的标志位，负数表示失败...但从逻辑上看似乎没有什么作用。
int c = -1;
// 声明一个新的节点。
Node<E> node = new Node<E>(e);
final ReentrantLock putLock = this.putLock;
final AtomicInteger count = this.count;
// lockInterruptibly方法与lock方法的差别在于其被中断（准确的说是其在中断后会抛出中断异常）。
putLock.lockInterruptibly();
try {
/*
* Note that count is used in wait guard even though it is not protected by lock. This works because count can only decrease at this point (all other
* puts are shut out by lock), and we (or some other waiting put) are signalled if it ever changes from capacity. Similarly for all other uses of count
* in other wait guards.
* 注意count（变量）在等待/延缓保护（不是很懂等待/延缓保护的意思，但翻译过来是这样，猜想应该是一个可以存在并发但并发情况不是很严重的
* 环境。因为count的类型是AtomicInteger，该类型本身就是用了乐观锁保证数据安全性，因此可以接受一定程度的并发）中使用（当前情景受放置锁
* 的保护，但不受拿取锁的保护，因此依然可能存在并发，符合猜想中存在并发但并发情况不是很严重的环境），即使不受锁的保护。这是有效的，因
* 为count（变量）在该位置只能减少（所有其它放置者（即执行put操作的线程）通过锁被排除在外）（因为受放置锁的保护，所有的put操作都被阻塞，
* 不会出现元素总数增大的情况），并且如果它从容量处变化（意思应该是队列中的元素被拿取...及元素总数减少...这TM都什么句子...），我们（或其
* 它等待中的放置者）会收到信号。相似地，count（变量）的所有其它使用（方式）也要在等待/延缓保护（环境）中（真TM服了这段注释...我这么差
* 的英文能翻译出这么一段话也真是佩服自己）。
*/
// 判断当前元素的总量是否等于容量。相等意味着已经没有空间可以存放元素了，当前线程必须进行等待。并且该操作是循环进行的，即使被唤醒的
// 第一件事也是判断，因为无法保证自己是第一个获取到锁的（可能有一次唤醒全部放置者的情况）。
while (count.get() == capacity) {
notFull.await();
}
// 执行尾部入队操作。
enqueue(node);
// 获取并自增元素总数，如果还有剩余空间，则继续唤醒一个后继放置者进行放置。
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
// 如果计数（快照）为0，意味着队列不再是空队列了，可以唤醒被阻塞的拿取者了。之所以只在为0的时候唤醒是因为其它数字意味着队列不为空，这
// 种情况下拿取者是不会被阻塞的的。
if (c == 0)
signalNotEmpty();
}
public boolean offer(E e, long timeout, TimeUnit unit) —— 提供 —— 用于插入/放置一个元素。该方法是插入/放置操作“超时”形式的定义。当队列容量已满而无法容纳插入/放置的元素时阻塞，直至队列空出容量后执行或因为超时而返回false。offer()方法的逻辑与put()方法基本相似，差别在于其只会限时挂起（通过调用非满/放置者条件的awaitNanos()方法实现），并且当超出指定的等待时间后会直接返回false。
/**
* Inserts the specified element at the tail of this queue, waiting if necessary up to the specified wait time for space to become available.
* 在队列的尾部插入指定的元素，如果必要则等待指定等待时间以致空间变得可用。
*
* @return {@code true} if successful, or {@code false} if the specified waiting time elapses before space is available
* 如果成功则返回true，如果在空间变得可用之前指定等待时间过去则返回false
* @throws InterruptedException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
*/
@Override
public boolean offer(E e, long timeout, TimeUnit unit) throws InterruptedException {
// 检查元素是否合法
if (e == null) throw new NullPointerException();
// 计算过期时间。
long nanos = unit.toNanos(timeout);
// c是操作是否成功的标志位，负数表示失败...但从逻辑上看似乎没有什么作用。
int c = -1;
final ReentrantLock putLock = this.putLock;
final AtomicInteger count = this.count;
putLock.lockInterruptibly();
try {
while (count.get() == capacity) {
// 相比put()方法其差异点就在次数，每次限时挂起之前都会先检查是否已经超时，超时则直接退出并返回false（offer()方法在定义上是不会抛出
// 异常的）。
if (nanos <= 0)
return false;
nanos = notFull.awaitNanos(nanos);
}
enqueue(new Node<E>(e));
c = count.getAndIncrement();
if (c + 1 < capacity)
notFull.signal();
} finally {
putLock.unlock();
}
// 如果计数（快照）为0，意味着队列不再是空队列了，可以唤醒被阻塞的拿取者了。之所以只在为0的时候唤醒是因为其它数字意味着队列不为空，这
// 种情况下拿取者是不会被阻塞的的。
if (c == 0)
signalNotEmpty();
return true;
}
private void enqueue(Node node) —— 入队 —— 用于插入/放置一个节点。enqueue()方法的逻辑十分简单，即将新节点从队列的尾部（即尾节点）加入队列，并将之设置为新的尾节点。话虽如此，但该方法至少要在放置锁的保护下执行，否则将出现线程安全问题。在插入/放置方法中存在对该方法的调用。
/**
* Links node at end of queue.
* 在队列的结尾链接节点（即尾插法）
*
* @param node the node 节点
*/
private void enqueue(Node<E> node) {
// assert putLock.isHeldByCurrentThread();
// assert last.next == null;
// 两步操作，先是将尾结点的后继节点设置为当前节点，随后将尾结点设置为当前节点。
last = last.next = node;
}
private void signalNotEmpty() —— 信号非空 —— 用于唤醒一个挂起的拿取者。当插入/放置方法执行成功后如果发现队列中只存在一个元素的话会调用此方法，因为这意味着可能存在挂起的拿取者。
/**
* Signals a waiting take. Called only from put/offer (which do not otherwise ordinarily lock takeLock.)
* 对一个等待中的拿取操作发信号。只在put/offer方法中调用（它们通常不会锁定takeLock。）
*/
private void signalNotEmpty() {
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
// 从等待拿取的等待队列中唤醒一个节点。本质是加入到AQS的等待队列中进行许可的获取。
notEmpty.signal();
} finally {
takeLock.unlock();
}
}
public E take() —— 拿取 —— 用于移除/拿取一个元素。该方法是移除/拿取操作“阻塞”形式的定义。当队列容量为空而无法移除/拿取元素时会阻塞，直至有新元素入队后执行。
所有的移除/拿取方法中都包含了两步固定操作（这两步操作下文不会再提及）：一是当元素成功出队后，如果当前容量不为0，则从非空/拿取者条件中唤醒一个拿取者来执行移除/拿取。该操作确保了当队列存在元素时挂起的拿取者会被持续唤醒；二是当元素成功出队后如果发现队列在执行此次移除/拿取操作前是满溢状态，则唤醒一个放置者进行执行放置。该操作保证了当队列存在剩余容量时（此次移除/拿取操作后会空出一个容量）挂起的放置者会被持续唤醒。而之所以只在该条件下执行是因为当队列中存在剩余容量的情况下放置者是不会挂起的。
/**
* @Description: 拿取：如果不存在可用元素则无限等待至有元素插入为止。
*/
@Override
public E take() throws InterruptedException {
E x;
int c = -1;
// 获取拿取锁。
final AtomicInteger count = this.count;
final ReentrantLock takeLock = this.takeLock;
takeLock.lockInterruptibly();
try {
// 如果没有可用的元素，则将自身等待（本质是将自身加入相应的条件队列），直至被唤醒，并再次重复判断。
while (count.get() == 0) {
notEmpty.await();
}
// 获取队列的头元素中保存的条目（将旧头元素抛弃，并返回其后继元素保存的条目。将后继元素作为新的头元素保留在队列中）。
x = dequeue();
c = count.getAndDecrement();
// 如果还有元素，则唤醒处于等待状态的其他拿取者。
if (c > 1)
notEmpty.signal();
} finally {
takeLock.unlock();
}
// 如果此次拿取之前队列是满溢的状态，则拿取后需要唤醒被挂起的放置者。只在该条件下唤醒是因为放置者在队列未满溢的情况下是不会挂起的。
if (c == capacity)
signalNotFull();
return x;
}
public E poll(long timeout, TimeUnit unit) —— 轮询 —— 用于移除/拿取一个元素。该方法是移除/拿取操作“超时”形式的定义。当队列容量为空而无法移除/拿取元素时阻塞，直至有新元素入队后执行或因为超时而返回false。
/**
* @Description: 轮询：如果元素不存在则等待限定的时间，在指定时间内获取则返回，否则返回null。
*/
@Override
public E poll(long timeout, TimeUnit unit) throws InterruptedException {
E x = null;
int c = -1;
// 计算过期时间并获取拿取锁。
long nanos = unit.toNanos(timeout);
final AtomicInteger count = this.count;
final ReentrantLock takeLock = this.takeLock;
takeLock.lockInterruptibly();
try {
// 在没有元素的情况下将自身限时挂起，挂起前先判断是否超时，超时则直接返回null。
while (count.get() == 0) {
if (nanos <= 0)
return null;
nanos = notEmpty.awaitNanos(nanos);
}
// 获取头元素的内容。
x = dequeue();
c = count.getAndDecrement();
// 如果还有元素，则唤醒其它挂起的拿取者。
if (c > 1)
notEmpty.signal();
} finally {
takeLock.unlock();
}
// 如果此次拿取之前队列是满溢的状态，则拿取后需要唤醒被挂起的放置者。只在该条件下唤醒是因为放置者在队列未满溢的情况下是不会挂起的。
if (c == capacity)
signalNotFull();
return x;
}
public E poll() —— 轮询 —— 用于移除/拿取一个元素。该方法是移除/拿取操作“特殊值”形式的定义，当队列容量为空而无法移除/拿取元素时返回null。
/**
* @Description: 轮询：直接进行获取，没有元素的情况下直接返回null。
*/
@Override
public E poll() {
// 进行一次判断，如果没有则直接返回null，这是双重检查锁的第一次非同步检查，有助于提高并发。
final AtomicInteger count = this.count;
if (count.get() == 0)
return null;
// 获取拿取锁。
E x = null;
int c = -1;
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
// 在持有锁的情况下再进行一次判断，在满足条件的情况下获取头元素的条目。
if (count.get() > 0) {
x = dequeue();
c = count.getAndDecrement();
// 如果还有元素，则唤醒其它的拿取者。
if (c > 1)
notEmpty.signal();
}
} finally {
takeLock.unlock();
}
// 如果此次拿取之前队列是满溢的状态，则拿取后需要唤醒被挂起的放置者。只在该条件下唤醒是因为放置者在队列未满溢的情况下是不会挂起的。
if (c == capacity)
signalNotFull();
return x;
}
private E dequeue() —— 出队 —— 用于移除/拿取队列的头节点，并返回其包含的元素。虽说方法的定义是如此，但之前也已经提及过队列的头节点实际上是一个空节点（即未容纳元素），因此我们真正要返回的元素其实是头节点的后继节点的元素值。具体的做法是先将原头节点对后继节点的引用设置为自身（这步操作一方面有助于GC（不能设置为null，这会和尾节点的判断逻辑冲突），另一方面也被作为迭代器的标志位使用，这一点下文会详述），再将其原后继节点设置为新头节点，并返回其元素。这样一来原头节点就被移除/拿取出了队列，而其后继节点因为返回了元素转变为空节点，并最终成为了新的头节点。因此，实际返回的元素其实是头节点后继节点的所容纳的元素。
/**
* Removes a node from head of queue.
* 从队列的头部移除一个节点（即头出法）
*
* @return the node 节点
*/
private E dequeue() {
// assert takeLock.isHeldByCurrentThread();
// assert head.item == null;
Node<E> h = head;
Node<E> first = h.next;
// 将头节点（快照）的后继节点设置为其自身，这有助于GC将之回收，也是迭代器从头开始的标志位。
h.next = h; // help GC
// 将头节点设置为头节点（快照）的后继节点，并返回其item（条目）字段值后将之设置为null（因为头节点的item（条目）字段值都为null，但因为置
// null操作在设置头节点操作之后执行，因此还是会有短暂的时间里是的头节点的item（条目）字段值不为null）
head = first;
E x = first.item;
first.item = null;
return x;
}
private void signalNotFull() —— 信号非满 —— 用于唤醒一个放置者。当移除/拿取方法执行成功后如果发现队列在方法执行前时满溢状态就会调用此方法，因为这意味着可能存在挂起的放置者。
/**
* Signals a waiting put. Called only from take/poll.
* 像一个等待中的放置操作发送信号，只在take/poll方法中调用。
*/
private void signalNotFull() {
final ReentrantLock putLock = this.putLock;
putLock.lock();
try {
// 从等待放置的等待队列中唤醒一个节点。
notFull.signal();
} finally {
putLock.unlock();
}
}
public E peek() —— 窥视 —— 用于获取一个元素。该方法是检查方法的“特殊值”形式的实现。当队列容量为0时不会阻塞，而是直接返回null。
/**
* @Description: 窥视：获取条目，但不会将之从元素中取出。
*/
@Override
public E peek() {
// 进行双重检查锁的第一次判断，如果没有元素则直接返回null。
if (count.get() == 0)
return null;
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
// 如果存在头元素（准确的说应该是头元素的后继元素），则直接返回其条目，否则返回null。但注意，该操作不会将条目从条目中移除。
Node<E> first = head.next;
if (first == null)
return null;
else
return first.item;
} finally {
takeLock.unlock();
}
// 因为不存在元素数量的变化，因此也就不会进行唤醒操作。
}
public int size() —— 大小 —— 用于返回队列已保存的元素数量。
/**
* Returns the number of elements in this queue.
* 返回队列中元素的数量
*
* @return the number of elements in this queue 队列中元素的数量
*/
@Override
public int size() {
return count.get();
}
public int remainingCapacity() —— 剩余容量 —— 用于获取队列可用的容量。该方法由于并发的原因，并不推荐将该方法的返回值作为是否插入的判断依据（至少不能作为精确的判断依据），因为在获取后及插入/放置前可能有其它线程执行了插入/放置操作导致容量耗尽。
/**
* Returns the number of additional elements that this queue can ideally (in the absence of memory or resource constraints) accept without blocking.
* This is always equal to the initial capacity of this queue less the current {@code size} of this queue.
* 返回该队列理想情况下（内存缺失或资源限制）可接受而不足的的新增元素数量。
* <p>
* Note that you <em>cannot</em> always tell if an attempt to insert an element will succeed by inspecting {@code remainingCapacity} because it may
* be the case that another thread is about to insert or remove an element.
* 注意不能经常试图通过检查remainingCapacity（是否有空余）来新增元素，因为可能存在其他线程新增/删除元素的情况（此时remainingCapacity
* 是一个无效快照，不能作为新增的参考依据，这是并发中典型的竞态条件场景）
*/
@Override
public int remainingCapacity() {
return capacity - count.get();
}
public boolean remove(Object o) —— 移除（false：失败，true：成功） —— 用于移除一个指定的元素。与插入/放置及移除/拿取方法不同，remove()方法必须同时获取两个锁，因为其可能在队列的任意位置进行移除，无论是单纯的加拿取锁或是放置锁都会存在线程安全问题，也正是因为我们并不推荐调用此方法，因为其性能并不高效，并且只为偶尔使用预留。除此以外，还存在对迭代器造成影响，GC等一系列的问题。
/**
* Removes a single instance of the specified element from this queue, if it is present. More formally, removes an element {@code e} such that {@code o.equals(e)},
* if this queue contains one or more such elements. Returns {@code true} if this queue contained the specified element(or equivalently, if this queue changed as a
* result of the call).
* 从队列中移除指定元素的一个单例（如果存在）。更正式地，应该通过equals()方法判断并移除元素（如果这个队列包含一个或多个指定元素）。如果这个队列包
* 含指定元素便返回true（或等效地，如果这个队列因为调用这个方法的结果而变化（也要返回true））。
*
* @param o element to be removed from this queue, if present 从队列中移除的元素（如果存在）
* @return {@code true} if this queue changed as a result of the call 如果这个队列因为调用这个方法的结果而变化
*/
@Override
public boolean remove(Object o) {
// 如果传入null，则直接返回false。因为null是头元素的标记。
if (o == null) return false;
// 加全锁，即同时加拿取锁和放置锁。因为移除可能发生在队列的人和位置，如果只加拿取锁（本质是拿取），则如果发生在队列的尾部，就可能在放置新元
// 素时导致线程数据错误。因此必须加全锁。
fullyLock();
try {
// 从头元素开始向后遍历，直至找到第一个与指定元素相同的元素，将之从队列中移除。
for (Node<E> trail = head, p = trail.next; p != null; trail = p, p = p.next) {
if (o.equals(p.item)) {
// unlink()方法规定了必须在全锁的环境下才能调用，如果执行了移除操作则返回true。
unlink(p, trail);
return true;
}
}
// 如果未执行移除操作则返回false。
return false;
} finally {
// 解全锁。
fullyUnlock();
}
}
void fullyLock() —— 全锁 —— 用于一次性获取放置锁和拿取锁。
/**
* Locks to prevent both puts and takes.
* 加锁以防止放置及拿取。
*/
void fullyLock() {
putLock.lock();
takeLock.lock();
}
void fullyUnlock() —— 全解锁 —— 用于一次性解除放置锁和拿取锁。
/**
* Unlocks to allow both puts and takes.
* 解锁以允许放置及拿取。
*/
void fullyUnlock() {
takeLock.unlock();
putLock.unlock();
}
void unlink(Node p, Node trail) —— 解除链接 —— 用于断开两个节点之间的关联。该方法被强制规定只能在获取双锁的状态下使用，因为操作可能对队列中任意位置的节点执行，因此如果不获取双锁会存在线程安全问题。unlink()方法还有一点需要被注意的是被移除的节点并不会断开与原后继节点的引用，如此设计是为了保证LinkedBlockingQueue（链接阻塞队列）类迭代器实现的弱一致性（所谓的弱一致性，是指数据最终会达成一致，但是存在延迟）。即使在迭代过程中正在被迭代的节点已经被移除，但只要其依然持有后继节点的引用，就依然可以继续迭代产生该节点依然存在于队列中的假象。是想如果迭代器是强一致性的，便需断开移除节点与后继结点的引用（因为节点已经从队列中移除了，不可以在持有存在于队列中的后继节点的引用了）。而如果该节点正恰好被迭代器所迭代，那后果就是造成迭代的中断，这显然是不能被接受的。话虽如此，这么做也存在一定的隐患，例如如果被移除的元素存在于老年代的话，可能会导致长时间的难以回收（老年代额GC并不频繁），并且如果其后继节点是新生的的对象，则还会产生跨代引用的问题。
与移除/拿取方法相似，该方法如果发现移出前队列是满溢的状态，会唤醒一个放置者执行插入/放置操作（因为移除后已经空出了空间）。
/**
* Unlinks interior Node p with predecessor trail.
* 断开内部节点p与其后继节点的路线，即关联。
*/
void unlink(Node<E> p, Node<E> trail) {
// assert isFullyLocked(); p.next is not changed, to allow iterators that are traversing p to maintain their weak-consistency guarantee.
// 断言该方法调用时处于同时获取到两个锁的状态（在断开链接的过程中队列中的节点必须保持静止，否则可能会出现并发数据安全，例如在断开链接的
// 过程中当前节点刚好出队，又或者在没有后继节点的情况下新增了一个后继节点，相关场景应该不难设想）；p的后继节点没有发生改变（即不会断开
// p与其后继节点的关联），允许遍历p的迭代器保持弱一致性（所谓的弱一致性就是指最终会达到一致，但可能会存在延时。即p已经从队列中移除的情
// 况下，有线程已经迭代到了p，从而出现p依然还处于队列中的假象。此处没有采用强一致性避免了线程在迭代过程中突然中断的情况）。
// 将p的条目设置为null，并设置trail（本质是p的前驱节点）的后继节点为p的后继节点（相当于从中抛弃了p）。但p与其后继节点的链接不会断开。
p.item = null;
trail.next = p.next;
// 如果p是最后一个节点，则将其前驱节点设置为尾节点。
if (last == p)
last = trail;
// 如果移除前的容量满了，则在移除后唤醒被挂起的放置者（如果存在的话）。
if (count.getAndDecrement() == capacity)
notFull.signal();
}
public boolean contains(Object o) —— 包含（false：不包含，true：包含） —— 用于判断是否包含指定元素（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。方法会遍历整个队列，一旦发现相同的元素便返回true，否则返回false。
/**
* Returns {@code true} if this queue contains the specified element. More formally, returns {@code true} if and only if this queue contains at least one element
* {@code e} such that {@code o.equals(e)}.
* 如果队列存在指定的元素则返回true。更正式地，当且仅当队列包含至少一个指定元素使得equals()方法为true。
*
* @param o object to be checked for containment in this queue 用于在队列中检查包含的对象
* @return {@code true} if this queue contains the specified element 如果对象包含指定元素返回true。
*/
@Override
public boolean contains(Object o) {
// 如果传入null，则直接返回false。因为null是头元素的标记。
if (o == null) return false;
// 加全锁。虽然判断包含不存在节点数量的变化，但是节点入队出队会影响判断的结果。
fullyLock();
try {
// 遍历，存在返回true，否则返回false。
for (Node<E> p = head.next; p != null; p = p.next)
if (o.equals(p.item))
return true;
return false;
} finally {
fullyUnlock();
}
}
public int drainTo(Collection<? super E> c) —— 流失 —— 用于将队列中的所有元素迁移至指定的集中。该方法底层通过重载的drainTo()方法实现，其在参数中传入了int类型的最大值，意味着迁移所有的元素。
/**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
* @Description: 流失：将队列中的元素迁移到指定的集中。
*/
@Override
public int drainTo(Collection<? super E> c) {
return drainTo(c, Integer.MAX_VALUE);
}
public int drainTo(Collection<? super E> c, int maxElements) —— 流失 —— 用于将队列中的最多指定数量的元素迁移至指定的集中。该方法的实现也较为简单，先是确定迁移元素的数量（在指定的数量与队列中元素的数量取较小值，由于迁移的元素是在一开始就确定的，因此即使是在元素总数小于指定数量的情况下，后期插入/放置的元素也无法被迁移至数据中），随后遍历队列进行元素的迁移。由于迁移的顺序是从队列的头部开始的，故操作的本质与移除/拿取相同，因此只需受拿取锁的保护。元素迁移完毕后如果发现执行之前队列是满溢的，则唤醒一个可能挂起的放置者（需要再方法中真正迁移了元素）。
/**
* @throws UnsupportedOperationException {@inheritDoc}
* @throws ClassCastException {@inheritDoc}
* @throws NullPointerException {@inheritDoc}
* @throws IllegalArgumentException {@inheritDoc}
* @Description: 流失：从队列迁移最大数量的元素到指定的集中。
*/
@Override
public int drainTo(Collection<? super E> c, int maxElements) {
// 如果指定集为null，则直接抛出NullPointerException。
if (c == null)
throw new NullPointerException();
// 如果迁移的集是队列本身，则抛出IllegalArgumentException。
if (c == this)
throw new IllegalArgumentException();
// 如果最大元素数量小于0，则直接返回0，意味着一个元素都没有迁移。
if (maxElements <= 0)
return 0;
// 加拿取锁。迁移的本质实际上就是不断地将元素从队列中出队并存入指定集中，因此只需要获取拿取锁即可。
boolean signalNotFull = false;
final ReentrantLock takeLock = this.takeLock;
takeLock.lock();
try {
// 判断节点数量与最大元素数量的大小，将较小的数量作为真正要迁移的元素数量。但有一种情况是：如果队列中存在2个元素，而最大元素的数量是5，而在迁移
// 过程中又放置了2个元素，那理论上应该一共可以迁移4个元素。但实际上只会迁移前2个元素，因此可知迁移的元素是在方法调用时的确定的，在迁移过程中新增
// 的元素不会被迁移。
int n = Math.min(maxElements, count.get());
// count.get provides visibility to first n Nodes
Node<E> h = head;
int i = 0;
try {
// 遍历队列，迁移元素。即将元素加入转移至集中。
while (i < n) {
Node<E> p = h.next;
c.add(p.item);
p.item = null;
h.next = h;
h = p;
++i;
}
return n;
} finally {
// Restore invariants even if c.add() threw
// 如果实际迁移的元素数量大于0，则将最后一个迁移的节点设置为头节点。并且如果迁移前队列元素是满的，还需要再迁移后唤醒挂起的放置者。
if (i > 0) {
// assert h.item == null;
head = h;
signalNotFull = (count.getAndAdd(-i) == capacity);
}
}
} finally {
// 解拿取锁，并根据运行结果执行对放置者的唤醒。
takeLock.unlock();
if (signalNotFull)
signalNotFull();
}
}
public Object[] toArray() —— 转化数组 —— 用于将队列中的所有元素赋值于一个新的Object（对象）数组中返回（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。其会遍历整个队列，将元素一一赋值于一个新创建的Object（对象）数组中，Object（对象）数组的长度与队列元素的数量相同。
虽说方法toArray()方法返回的是第一个新创建的Object（对象）数组，但在具体的实现中元素并没有使用拷贝的方式赋值，即Object（对象）数组中持有的元素引用与队列持有的元素引用是相同的，在任意一方对元素本身进行修改都会导致另一方的元素出现变化。
/**
* Returns an array containing all of the elements in this queue, in proper sequence.
* 返回一个包含队列所有元素的数据，按适当的（适当...应该就是队列的原顺序...应该也可以自我重写定义）顺序。
* <p>
* The returned array will be "safe" in that no references to it are maintained by this queue. (In other words, this method must allocate a new array). The caller is
* thus free to modify the returned array.
* 该返回的数据将是"安全"的，队列不会维护该数组的引用（即返回的数组是一个快照，队列的变化不会导致数组发生变化）。（换句话说，这该方法必须分配一个
* 新数组）。调用者因此可以自由的修改这个返回的数组。
* <p>
* This method acts as bridge between array-based and collection-based APIs.
* 该方法行为作为基于数组和基于集的API之间的桥梁（即通过数组，令两种不同结构的容器数组之间可以相互交流）。
*
* @return an array containing all of the elements in this queue 一个包含当前队列所有元素的数组
*/
@Override
public Object[] toArray() {
// 加全锁。虽然分配一个数组不会造成队列本身发生变化，但并发的出入对会新分配的数组数据造成影响。
fullyLock();
try {
// 实例化一个当前节点数量大小的的数组。
int size = count.get();
Object[] a = new Object[size];
// 遍历整个队列，将所有的元素都赋值到数组中...但是可以发现这里使用的并不是深拷贝，因此队列中引用的元素及数组中引用的元素实际上是同一个，因此
// 如果是引用类型，则在对元素进行修改时，无论是在哪一方进行的修改，都会影响到另一方。而上文提及数组"安全"，是指数组结构上的安全，即新增/移除一
// 个元素不会影响到队列，但如果对元素本身进行修改那还是有可能会有影响的（如果元素类型是引用类型的话）。
int k = 0;
for (Node<E> p = head.next; p != null; p = p.next)
a[k++] = p.item;
// 返回生成的数组。
return a;
} finally {
// 解全锁。
fullyUnlock();
}
}
public T[] toArray(T[] a) —— 转化数组 —— 用于将队列中的所有元素赋值于一个指定的泛型数组中返回，如果指定泛型数组不足以容纳所有的元素，则新创建一个队列元素数量大小的泛型数组用于容纳后返回（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。在遍历整个队列进行赋值之前，其会先判断指定的泛型数组长度是否足够容纳所有的队列元素，如果不足则会新创建一个队列元素大小的泛型数组用于容纳。除此以外，如果指定的泛型数组长度满足要求（>=），但其内部已含有相应的值的话，会在所有的队列元素赋值完毕之后，将数组的后一位设置为null，作为标记值表示真正的元素数据到此为止。
/**
* Returns an array containing all of the elements in this queue, in proper sequence; the runtime type of the returned array is that of the specified array. If the queue
* fits in the specified array, it is returned therein. Otherwise, a new array is allocated with the runtime type of the specified array and the size of this queue.
* 返回包含队列所有元素的数组，按合理的顺序；返回数组的运行时类型是指定数组运行时类型（即返回一个指定类型的数组）。如果队列适合指定的数组，则在其中
* 返回它（即如果传入的数组大小符合大于等于队列大小的条件，则直接在传入的数组中存放元素）。否则，分配一个指定数组的运行时类型以及队列大小的新数组。
* <p>
* If this queue fits in the specified array with room to spare (i.e., the array has more elements than this queue), the element in the array immediately following the end
* of the queue is set to {@code null}.
* 如果队列符合指定的数组并空间有所剩余（例如，该数组有比队列更多的元素）（即指定数据的空间可能比队列大小要大，并且指定数据不一定是空的，还可能存在
* 未知数量的值），数组中的元素应在队列结束之后设置为null（即再将前n位设置为队列的元素之后，将下一个数组位置的值null，作为标志位使用，而再剩下的数组
* 位置就不管了）。
* <p>
* Like the {@link #toArray()} method, this method acts as bridge between array-based and collection-based APIs. Further, this method allows precise control over the
* runtime type of the output array, and may, under certain circumstances, be used to save allocation costs.
* 类似toArray()方法，当前方法行为被作为基于数组和基于集的API之间的桥梁。进一步，该方法允许精确控制产出数组的运行时类型，并且可能在特定的情况下用于节
* 省分配消耗/成本。
* <p>
* Suppose {@code x} is a queue known to contain only strings. The following code can be used to dump the queue into a newly allocated array of {@code String}:
* 假设x是一个已知只包含字符串的队列。以下代码能够倾倒队列至新分配的字符串数组中。
* <pre> {@code String[] y = x.toArray(new String[0]);}</pre>
* <p>
* Note that {@code toArray(new Object[0])} is identical in function to {@code toArray()}.
* 注意toArray(new Object[0])是与toArray()完全相同的功能（new Object[0]是一个无法承载元素的数组，理论上会实例化一个新的Object类型的数组，但是也不一定，
* 如果队列的节点数量大小也为0的话...那还是原来的数组，因此还是有一些细小的差别的）。
*
* @param a the array into which the elements of the queue are to be stored,if it is big enough;otherwise, a new array of the same runtime type is allocated for this purpose
* 用于保存队列元素的数组（如果足够大）；否则会按计划分配一个相同运行时类型的数组。
* @return an array containing all of the elements in this queue 一个包含队列所有元素的数组
* @throws ArrayStoreException if the runtime type of the specified array is not a supertype of the runtime type of every element in this queue
* 如果指定数组的运行时类型不是队列中每个元素的运行时类型的父类型（即指定数组的类型与队列元素的类型要么相同，要么使其父类）
* @throws NullPointerException if the specified array is null 如果指定数组为null
*/
@Override
@SuppressWarnings("unchecked")
public <T> T[] toArray(T[] a) {
// 加全锁。
fullyLock();
try {
// 判断指定数组的大小是否符合条件，如果不符合（即不够大），则声明一个与队列大小相同的数组。
int size = count.get();
if (a.length < size)
// 泛型数组无法使用常规的new方式创建，因此此处使用反射的方式已创建运行时类型的数组，并强制转化为泛型。
a = (T[]) java.lang.reflect.Array.newInstance(a.getClass().getComponentType(), size);
// 遍历队列，将元素赋予数组中。
int k = 0;
for (Node<E> p = head.next; p != null; p = p.next)
a[k++] = (T) p.item;
// 如果数组还有剩余空间，则将后一个数组位置的值设置为null作为标志位，表示到此为止所有的队列元素已经全部结束。
if (a.length > k)
a[k] = null;
return a;
} finally {
// 解全锁。
fullyUnlock();
}
}
public void clear() —— 清除 —— 用于将队列中的所有元素清除（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。方法会遍历整个队列，中断所有节点之间的关联，而不止直接将头/尾节点置null。这么做的目的是加速GC对之进行收集。当节点清除完毕后，如果发现在方法执行前队列是满溢的状态，则会唤醒一个放置者进行插入/放置操作（如果存在的话）。因此方法执行结束后并不意味着队列一定为空，很有可能有被唤醒或新的放置者已经插入/放置了元素。
/**
* Atomically removes all of the elements from this queue. The queue will be empty after this call returns.
* 原子地移除队列中的所有元素。队列将在调用返回之后为空。
*/
@Override
public void clear() {
fullyLock();
try {
// 断开所有节点之间的关联，并丢弃所有的元素。
for (Node<E> p, h = head; (p = h.next) != null; h = p) {
h.next = h;
p.item = null;
}
// 将头尾节点设置为初始状态。
head = last;
// assert head.item == null && head.next == null;
// 当前容量已满的情况下，唤醒所有的放置者。因此当前方法调用之后，虽然理论上可能为空，但如果存在挂起的放置者，但还是有可能存在元素。因为放置者向
// 空队列中加入了元素。
if (count.getAndSet(0) == capacity)
notFull.signal();
} finally {
fullyUnlock();
}
}
public Iterator iterator() —— 迭代器 —— 用于获取一个Iterator（迭代器）接口对象（下文简称迭代器）。
/**
* Returns an iterator over the elements in this queue in proper sequence. The elements will be returned in order from first (head) to last (tail).
* 按适当的顺序返回该队列元素的迭代器。元素将从头到尾的顺序返回。
* <p>
* The returned iterator is <a href="package-summary.html#Weakly"><i>weakly consistent</i></a>.
* 返回的迭代器是弱一致性的（即返回的节点元素可能已经从队列中出队/移除了）。
*
* @return an iterator over the elements in this queue in proper sequence 适当的顺序返回该队列元素的迭代器
*/
@Override
public Iterator<E> iterator() {
return new Itr();
}
二 Node（节点）类源码及机制详解
类
Node（节点）类是LinkedBlockingQueue（链接阻塞队列）类的一个内部类，即使元素的容器，也是链表的基本组成单位。
/**
* Linked list node class
* 链接列表节点类
*/
static class Node<E> {
...
}
字段
item（条目） —— 用于持有记录的元素。
/**
* 节点中具体保存的内容/条目
*/
E item;
next（后继） —— 用于持有后继节点的引用。
/**
* One of:
* - the real successor Node
* - 真实后继节点
* - this Node, meaning the successor is head.next
* - 当前节点，意味着后继节点是头节点的后继节点...表示自身为头节点？
* - null, meaning there is no successor (this is the last node)
* - null，意味着当前为最后一个节点，没有后继节点。
*/
Node<E> next;
构造方法
Node(E x) —— 用于创建一个节点，并保存元素。
Node(E x) {
item = x;
}
三 Itr类源码及机制详解
类
Itr类是LinkedBlockingQueue（链接阻塞队列）类内部自实现的一个迭代器，继承自Iterator（迭代器）接口。其是弱一致性的迭代器，会在自身持有当前迭代元素（即调用next()方法返回的元素）的快照。因此即使当前迭代元素已从队列中移除，也依然可以保证迭代继续进行。
/**
* @Description: 迭代器类
*/
private class Itr implements Iterator<E> {
/*
* Basic weakly-consistent iterator. At all times hold the next item to hand out so that if hasNext() reports true, we will still have it to return even if
* lost race with a take etc.
* 基于弱一致性的迭代器。在任何时候都要持有下个项目，以便如果hasNext()报告为真，那么即使在比赛中输了（意思是下个节点因为并发的原因已
* 经出队了），我们仍然可以将其返回（下个节点）。
*/
...
}
字段
current（当前节点） —— 用于持有当前迭代节点。
/**
* 当前节点：实际上是下个返回的节点，即下次调用next()方法返回的节点。
*/
private Node<E> current;
lastRet（上个节点） —— 用于持有上个迭代节点，即当前节点的前驱节点。
/**
* 上个节点：实际上是当前返回的节点，即最后一次调用next()方法返回的节点。
*/
private Node<E> lastRet;
currentElement（当前元素） —— 用于持有当前节点中容纳的元素。由于节点可能会被移除/拿取（包括中途移除），这种情况下节点都会被转化空节点，因此元素需要额外保存。
/**
* 当前元素：即当前节点对应的元素，由于节点被出队/移除后其内部的元素会被置null，因此还需要额外保存；
*/
private E currentElement;
构造方法
Itr() —— 该方法会在创建迭代器对象后，将队列的首个非空节点（即头节点的后继节点）设置为当前节点（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。
Itr() {
// 加全锁。
fullyLock();
try {
// 将当前节点设置为头节点的后继节点，即第一个真正的节点。如果该节点存在，则再保存其元素，避免出队/移除后被删除。
current = head.next;
if (current != null)
currentElement = current.item;
} finally {
fullyUnlock();
}
}
方法
public boolean hasNext() —— 存在下一个 —— 用于判断是否存在下一个元素。由于迭代器中存有当前迭代节点的快照（当前节点），因此只需直接判断当前节点是否为null即可。
/**
* @Description: 存在下一个：通过判断当前节点是否存在来判断是否存在下一个节点，当前节点的本质是下个要返回的节点。
*/
@Override
public boolean hasNext() {
return current != null;
}
public E next() —— 下一个 —— 用于获取当前迭代节点的元素（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。由于迭代器中直接存有当前节点所容纳的元素值，因此该方法的关键在于如何找到当前节点的后继节点，该功能由nextNode()方法实现。其会将当前节点设置为上个节点，并将新获取的后继节点设置为当前节点，并记录当前节点的元素，以避免该节点被移除而无法获取元素。
/**
* @Description: 下一个：即获取当前元素的下一个元素
*/
@Override
public E next() {
// 加全锁。
fullyLock();
try {
// 如果当前节点为null，则说明已经没有后续节点了，直接抛出异常。
if (current == null)
throw new NoSuchElementException();
// 获取当前节点的用于返回。
E x = currentElement;
// 将上个节点设置为当前节点，并检索新的当前节点。这个检索的过程中，由于出队/移除并发的原因，因此可能出现直接返回第一个真正节
// 点或跳跃多个节点的情况。
lastRet = current;
current = nextNode(current);
// 为了防止检索到的节点后期被移除，需要将其元素进行单独的保存。
currentElement = (current == null) ? null : current.item;
return x;
} finally {
// 解全锁。
fullyUnlock();
}
}
private Node nextNode(Node p) —— 下个节点 —— 用于获取指定节点的首个存在于队列中的后继节点。方法会在指定节点的基础上向后遍历，以获取后继节点。如果发现指定节点的后继引用指向自身，说明当前节点已经被正常的移除/出队，这就意味着第一个存在于队列中的后继节点就是队列的第一个非空节点；如果发现指定节点的后继节点为null，这就意味着所有的元素都已经遍历完毕，已经没有元素可以遍历了，直接返回null；如果发现后继节点是一个非空节点，这说明该后继节点正常存在于队列中，也正是我们需要寻找的节点，直接将之返回；而如果发现后继节点是一个空节点，这就意味着当前节点已经从队列中被移除（通过remove()方法）。但由于被移除的节点不会清除起后继引用（这就是remove()方法移除节点时不清除后继引用的原因），因此可通过其继续向后遍历，直至找到第一个存在于队列中的后继节点（如果存在的话）。
/**
* Returns the next live successor of p, or null if no such.
* 返回p的下个存活（即还未将元素置null）后继节点，如果没有则返回null。
* <p>
* Unlike other traversal methods, iterators need to handle both:
* 不像其他遍历方法，迭代器需要处理两种情况：
* - dequeued nodes (p.next == p)
* - 节点出队 （p.next == p）
* - (possibly multiple) interior removed nodes (p.item == null)
* - （可能多数）内部移除节点（p.item == null）（如果当前元素的引用的后继节点已被移除，则其元素即为null，属于非存活节点，其唯一作用就是
* 链接下个后继节点，从而使得迭代正常，因此移除节点并不会像出队节点一样断开对后继节点的引用）。
*/
private Node<E> nextNode(Node<E> p) {
for (; ; ) {
// 从指定节点向后遍历。
Node<E> s = p.next;
// 如果当前节点与其后继节点相同，意味着这是一个正常出队的节点，直接返回当前的第一个真正的节点（不存在即是null）。
if (s == p)
return head.next;
// 如果后继节点不存在（意味着已经是最后一个节点了），或者后继节点的元素不为null（意味着这是一个存活后继节点），则直接返回。
if (s == null || s.item != null)
return s;
// 如果后继节点存在，但对应的元素为null，这说明该节点从队列中移除了，因此需要继续向后遍历，直至结束或找到存活后继节点位为止。
p = s;
}
}
public void remove() —— 移除 —— 用于将上个元素移除，即上个节点所包含的元素（该方法在双锁的保护下执行，防止元素的出入队对执行过程造成影响）。该方法的本质与LinkedBlockingQueue（链接阻塞队列）类的remove()方法完全一致，因此只需通过迭代器中保存的上个节点找到队列中所在的位置，就可以直接调用unlink()方法将之移除。如果在队列的过程中没有找到指定节点，就意味着该节点已被其它线程中途移除。于此同时，还需要将迭代器中保存的上个节点置null。
/**
* @Description: 移除：移除当前元素（即通过next()方法获得的元素）
*/
@Override
public void remove() {
// 如果上个节点不存在，则直接抛出异常。因为这说明迭代器从来没有调用过next()方法或next()方法没有可返回的元素。
if (lastRet == null)
throw new IllegalStateException();
// 加全锁。
fullyLock();
try {
// 先将储存在迭代器中的上个节点置null。
Node<E> node = lastRet;
lastRet = null;
// 随后遍历数组，找到指定的节点，将之从队列中移除。如果一直没有发现，则说明该节点已被移除。
for (Node<E> trail = head, p = trail.next; p != null; trail = p, p = p.next) {
if (p == node) {
unlink(p, trail);
break;
}
}
} finally {
// 解全锁。
fullyUnlock();
}
}
四 相关系列
- 《Java ~ Executor》
- 《Java ~ Executor ~ LinkedBlockingQueue【总结】》
- 《Java ~ Executor ~ LinkedBlockingQueue【源码】》