LinkedBlockingDeque阻塞队列 LinkedBlockingDeque阻塞队列

一、简述 LinkedBlockingDeque 是一个由链表结构组成的双向阻塞队列，即可以从队列的两端插入和移除元素。双向队列因为多了一个操作队列的入口，在多线程同时入队时，也就减少了一半的竞争。相比于其他阻塞队列，LinkedBlockingDeque 多了 addFirst、addLast、peekFirst、peekLast 等方法。以first结尾的方法，表示插入、获取或移除双端队列的第一个元素。以 last 结尾的方法，表示插入、获取或移除双端队列的最后一个元素。LinkedBlockingDeque 是可选容量的，在初始化时可以设置容量防止其过度膨胀。如果不设置，默认容量大小为 Integer.MAX_VALUE。LinkedBlockingDeque 类有三个构造方法：

public LinkedBlockingDeque() public LinkedBlockingDeque(int capacity) public LinkedBlockingDeque(Collection c)

二、LinkedBlockingDeque源码详解 LinkedBlockingDeque 类定义为：

public class LinkedBlockingDeque extends AbstractQueue implements BlockingDeque, java.io.Serializable

该类继承自 AbstractQueue 抽象类，又实现了 BlockingDeque 接口。BlockingDeque 接口定义如下：

public interface BlockingDeque extends BlockingQueue, Deque

BlockingDeque 继承自 BlockingQueue 和 Deque 接口，BlockingDeque 接口定义了在双端队列中常用的方法。
LinkedBlockingDeque 类中的数据都被封装成了 Node 对象：

static final class Node { E item; Node prev; Node next; Node(E x) { item = x; } }

LinkedBlockingDeque 类中的重要字段如下：

// 队列双向链表首节点 transient Node first; // 队列双向链表尾节点 transient Node last; // 双向链表元素个数 private transient int count; // 双向链表最大容量 private final int capacity; // 全局独占锁 final ReentrantLock lock = new ReentrantLock(); // 非空Condition对象 private final Condition notEmpty = lock.newCondition(); // 非满Condition对象 private final Condition notFull = lock.newCondition();

LinkedBlockingDeque 类的底层实现和 LinkedBlockingQueue 类很相似，都有一个全局独占锁，和两个 Condition 对象，用来阻塞和唤醒线程。
LinkedBlockingDeque 类对元素的操作方法比较多。针对元素的入队、出队操作以 putFirst、putLast、pollFirst、pollLast 方法来进行分析。
三、入队 1??putFirst(E e) 是将指定的元素插入双端队列的开头，源码如下：

public void putFirst(E e) throws InterruptedException { // 若插入元素为null，则直接抛出NullPointerException异常 if (e == null) throw new NullPointerException(); // 将插入节点包装为Node节点 Node node = new Node(e); // 获取全局独占锁 final ReentrantLock lock = this.lock; lock.lock(); try { while (!linkFirst(node)) notFull.await(); } finally { // 释放全局独占锁 lock.unlock(); } }

2??入队操作是通过 linkFirst(E e) 来完成的，如下所示：

private boolean linkFirst(Node node) { // assert lock.isHeldByCurrentThread(); // 元素个数超出容量。直接返回false if (count >= capacity) return false; // 获取双向链表的首节点 Node f = first; // 将node设置为首节点 node.next = f; first = node; // 若last为null，设置尾节点为node节点 if (last == null) last = node; else // 更新原首节点的前驱节点 f.prev = node; ++count; // 唤醒阻塞在notEmpty上的线程 notEmpty.signal(); return true; }

若入队成功，则 linkFirst(E e) 返回 true，否则返回 false。若该方法返回 false，则当前线程会阻塞在 notFull 条件上。
3??putLast(E e) 是将指定的元素插入到双端队列的末尾，源码如下：

public void putLast(E e) throws InterruptedException { // 若插入元素为null，则直接抛出NullPointerException异常 if (e == null) throw new NullPointerException(); // 将插入节点包装为Node节点 Node node = new Node(e); // 获取全局独占锁 final ReentrantLock lock = this.lock; lock.lock(); try { while (!linkLast(node)) notFull.await(); } finally { // 释放全局独占锁 lock.unlock(); } }

4??该方法和 putFirst(E e) 几乎一样，不同点在于，putLast(E e) 通过调用 linkLast(E e) 来插入节点：

private boolean linkLast(Node node) { // assert lock.isHeldByCurrentThread(); // 元素个数超出容量。直接返回false if (count >= capacity) return false; // 获取双向链表的尾节点 Node l = last; // 将node设置为尾节点 node.prev = l; last = node; // 若first为null，设置首节点为node节点 if (first == null) first = node; else // 更新原尾节点的后继节点 l.next = node; ++count; // 唤醒阻塞在notEmpty上的线程 notEmpty.signal(); return true; }

若入队成功，则 linkLast(E e) 返回 true，否则返回 false。若该方法返回 false，则当前线程会阻塞在 notFull 条件上。
四、出队 1??pollFirst() 是获取并移除此双端队列的首节点，若不存在，则返回 null，源码如下：

public E pollFirst() { // 获取全局独占锁 final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkFirst(); } finally { // 释放全局独占锁 lock.unlock(); } }

2??移除首节点的操作是通过 unlinkFirst() 来完成的：

private E unlinkFirst() { // assert lock.isHeldByCurrentThread(); // 获取首节点 Node f = first; // 首节点为null，则返回null if (f == null) return null; // 获取首节点的后继节点 Node n = f.next; // 移除first，将首节点更新为n E item = f.item; f.item = null; f.next = f; // help GC first = n; // 移除首节点后，为空队列 if (n == null) last = null; else // 将新的首节点的前驱节点设置为null n.prev = null; --count; // 唤醒阻塞在notFull上的线程 notFull.signal(); return item; }

3??pollLast() 是获取并移除此双端队列的尾节点，若不存在，则返回 null，源码如下：

public E pollLast() { // 获取全局独占锁 final ReentrantLock lock = this.lock; lock.lock(); try { return unlinkLast(); } finally { // 释放全局独占锁 lock.unlock(); } }

4??移除尾节点的操作是通过 unlinkLast() 来完成的：

private E unlinkLast() { // assert lock.isHeldByCurrentThread(); // 获取尾节点 Node l = last; // 尾节点为null，则返回null if (l == null) return null; // 获取尾节点的前驱节点 Node p = l.prev; // 移除尾节点，将尾节点更新为p E item = l.item; l.item = null; l.prev = l; // help GC last = p; // 移除尾节点后，为空队列 if (p == null) first = null; else // 将新的尾节点的后继节点设置为null p.next = null; --count; // 唤醒阻塞在notFull上的线程 notFull.signal(); return item; }

【LinkedBlockingDeque阻塞队列】其实 LinkedBlockingDeque 类的入队、出队操作都是通过 linkFirst、linkLast、unlinkFirst、unlinkLast 这几个方法来实现的，源码读起来也比较简单。