##基本概念
LinkedBlockingQueue 是一个用链表实现的有界阻塞队列。
LinkedBlockingQueue 按照先进先出的原则对元素进行排序。
LinkedBlockingQueue 采用了双锁、双条件队列来提高读写效率。
##内部构造
LinkedBlockingQueue 内部维护着一个单向链表，且链表头节点的值永远为空。如下图所示：
下面来看它的构成：
-
Node ,节点
static class Node<E> { E item;
1Node<E> next; 2 3Node(E x) { 4 item = x; 5}}
-
构造函数
private transient Node<E> head; private transient Node<E> last; private final int capacity;
public LinkedBlockingQueue() { // 该队列是有界的，若不指定容量，默认为最大值 this(Integer.MAX_VALUE); }
public LinkedBlockingQueue(int capacity) { if (capacity <= 0){ // 抛出异常... }
1this.capacity = capacity; 2last = head = new Node<E>(null);}
##双锁机制
由于采用了双锁机制，因此它的出队、入队操作可以同时进行，从而提高效率。
1// 用于入队操作 2private final ReentrantLock putLock = new ReentrantLock(); 3private final Condition notFull = putLock.newCondition(); 4 5// 用于出队操作 6private final ReentrantLock takeLock = new ReentrantLock(); 7private final Condition notEmpty = takeLock.newCondition();
由于出入队可以同时进行，因此必须避免冲突问题。
-
同一元素操作冲突：由于 LinkedBlockingQueue 采用了 FIFO（先进先出）的原则，实际上是双端操作，不会存在冲突。并且在其内部定义了两个变量：head、last。
// 出队修改头节点 private transient Node<E> head;
// 入队修改尾节点 private transient Node<E> last;
-
元素数量操作冲突：因为入队数量要+1，出队数量要-1，因此需要保证它的可见性，这里采用了这里采用原子类来实现：
private final AtomicInteger count = new AtomicInteger(0);
##入队操作
-
offer，该操作成功返回 true，失败返回 false。
public boolean offer(E e) { if (e == null){ // 抛出异常... }
1// 判断元素的个数是否超过容量4 2final AtomicInteger count = this.count; 3if (count.get() == capacity){ 4 return false; 5} 6 7int c = -1; 8 9Node<E> node = new Node(e); 10 11// 加锁 12final ReentrantLock putLock = this.putLock; 13putLock.lock(); 14 15try { 16 // 再次判断，存在等待获取锁期间，其他线程执行入队操作。 17 if (count.get() < capacity) { 18 // 入队操作 19 enqueue(node); 20 21 // 注意：数量+1，返回的旧值 22 c = count.getAndIncrement(); 23 if (c + 1 < capacity){ 24 // 队列未满，唤醒因为队列满而阻塞的线程 25 notFull.signal(); 26 } 27 } 28} finally { 29 putLock.unlock(); 30} 31 32// 为 0 表示之前队列是空的，唤醒出队时因为空队列而进入 notEmpty 条件等待队列的线程 33if (c == 0){ 34 signalNotEmpty(); 35} 36 37return c >= 0;}
-
put，该操作成功返回 true，失败则进入阻塞。
private final AtomicInteger count = new AtomicInteger(0);
public void put(E e) throws InterruptedException {
1if (e == null){ 2 // 抛出异常... 3} 4 5int c = -1; 6Node<E> node = new Node(e); 7final ReentrantLock putLock = this.putLock; 8final AtomicInteger count = this.count; 9putLock.lockInterruptibly(); 10 11try { 12 13 // 满队列，进入条件等待队列，线程阻塞 14 while (count.get() == capacity) { 15 notFull.await(); 16 } 17 18 // 关键-> 入队操作 19 enqueue(node); 20 21 c = count.getAndIncrement(); 22 if (c + 1 < capacity){ 23 notFull.signal(); 24 } 25 26} finally { 27 putLock.unlock(); 28} 29 30if (c == 0){ 31 signalNotEmpty(); 32}}
-
关键
private void enqueue(Node<E> node) { last = last.next = node; }
private void signalNotEmpty() { final ReentrantLock takeLock = this.takeLock; takeLock.lock(); try { notEmpty.signal(); } finally { takeLock.unlock(); } }
-
入队操作的过程如下所示：
##出队操作
-
poll，成功返回被移除的元素，失败返回 null。
public E poll() { final AtomicInteger count = this.count; if (count.get() == 0){ return null; }
1E x = null; 2int c = -1; 3 4// 加锁 5final ReentrantLock takeLock = this.takeLock; 6takeLock.lock(); 7 8try { 9 if (count.get() > 0) { 10 // 关键 -> 出队 11 x = dequeue(); 12 c = count.getAndDecrement(); 13 if (c > 1){ 14 notEmpty.signal(); 15 } 16 } 17} finally { 18 takeLock.unlock(); 19} 20 21// 表示出队前满队列，唤醒因入队时满队列而进入 notFull 条件等待队列的线程。 22if (c == capacity){ 23 signalNotFull(); 24} 25return x;}
-
take，成功返回被移除的元素，失败则线程阻塞。
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(); }
1} finally { 2 takeLock.unlock(); 3} 4 5if (c == capacity){ 6 signalNotFull(); 7} 8 9return x;}
-
关键
private E dequeue() { // 头节点、以及它的后继节点 Node<E> h = head; Node<E> first = h.next;
1// 等于 h.next = null，即断开后指针 2h.next = h; 3 4// 设置新的头节点 5head = first; 6 7E x = first.item; 8 9// 将节点的值置空 10first.item = null; 11return x;}
private void signalNotFull() { final ReentrantLock putLock = this.putLock; putLock.lock(); try { notFull.signal(); } finally { putLock.unlock(); } }
-
出队过程如下图所示：
