一、双向队列Deque

Queue除了前面介绍的实现外，还有一种双向的 Queue实现Deque。这种队列允许在队列头和尾部进行入队出队操作，因此在功能上比Queue显然要更复杂。下图描述的是Deque的完整体系图。 需要说明的是LinkedList也已经加入了Deque的一部分（LinkedList是从jdk1.2 开始就存在数据结构）。
?

?
从上图可以看到，Deque不仅具有FIFO的Queue实现，也有FILO的实现，也就是不仅可以实现队列，也可以实现一个堆栈。
同时在Deque的体系结构图中可以看到，实现一个Deque可以使用数组（ArrayDeque），同时也可以使用链表（LinkedList），还可以同实现一个支持阻塞的线程安全版本队列LinkedBlockingDeque。

1、ArrayDeque实现Deque
?

?
?
对于LinkedList本身而言，数据结构就更简单了，除了一个size用来记录大小外，只有head一个元素Entry。对比Map和Queue的其它数据结构可以看到这里的Entry有两个引用，是双向的队列。
在示意图中，LinkedList总是有一个“傀儡”节点，用来描述队列“头部”，但是并不表示头部元素，它是一个执行null的空节点。
队列一开始只有head一个空元素，然后从尾部加 入E1(add/addLast)，head和E1之间建立双向链接。然后继续从尾部加入E2，E2就在head和E1之间建立双向链接。最后从队列的头 部加入E3(push/addFirst)，于是E3就在E1和head之间链接双向链接。
双向链表的数据结构比较简单，操作起来也比较容 易，从事从“傀儡”节点开始，“傀儡”节点的下一个元素就是队列的头部，前一个元素是队列的尾部，换句话说，“傀儡”节点在头部和尾部之间建立了一个通 道，是整个队列形成一个循环，这样就可以从任意一个节点的任意一个方向能遍历完整的队列。
同样LinkedList也是一个没有容量限制的队列，因此入队列（不管是从头部还是尾部）总能成功。
?
3、小结

上面描述的ArrayDeque和LinkedList是两种不同方式的实现，通常在遍历和节省内存上ArrayDeque更高效（索引更快，另外不需要Entry对象），但是在队列扩容下LinkedList更灵活，因为不需要复制原始的队列，某些情况下可能更高效。
同样需要注意的上述两个实现都不是线程安全的，因此只适合在单线程环境下使用，下面章节要介绍的LinkedBlockingDeque就是线程安全的可阻塞的Deque。事实上也应该是功能最强大的Queue实现，当然了实现起来也许会复杂一点。

二、双向并发阻塞队列?LinkedBlockingDeque

1、LinkedBlockingDeque数据结构

双向并发阻塞队列。所谓双向是指可以从队列的头和尾同时操作，并发只是线程安全的实现，阻塞允许在入队出队不满足条件时挂起线程，这里说的队列是指支持FIFO/FILO实现的链表。
?
首先看下LinkedBlockingDeque的数据结构。通常情况下从数据结构上就能看出这种实现的优缺点，这样就知道如何更好的使用工具了。
?

?
从数据结构和功能需求上可以得到以下结论：
要想支持阻塞功能，队列的容量一定是固定的，否则无法在入队的时候挂起线程。也就是capacity是final类型的。
既然是双向链表，每一个结点就需要前后两个引用，这样才能将所有元素串联起来，支持双向遍历。也即需要prev/next两个引用。
双向链表需要头尾同时操作，所以需要first/last两个节点，当然可以参考LinkedList那样采用一个节点的双向来完成，那样实现起来就稍微麻烦点。
既然要支持阻塞功能，就需要锁和条件变量来挂起线程。这里使用一个锁两个条件变量来完成此功能。

2、LinkedBlockingDeque源码分析

[java] view plaincopy
public?class?LinkedBlockingDeque<E>?extends?AbstractQueue<E>?implements?BlockingDeque<E>,??java.io.Serializable?{?
????/**?包含前驱和后继节点的双向链式结构?*/?
????static?final?class?Node<E>?{?
?E?item;?
????????Node<E>?prev;?
????????Node<E>?next;?
????????Node(E?x,?Node<E>?p,?Node<E>?n)?{?
????????????item?=?x;?
????????????prev?=?p;?
????????????next?=?n;?
????????}?
????}?
????/**?头节点?*/?
????private?transient?Node<E>?first;?
????/**?尾节点?*/?
????private?transient?Node<E>?last;?
????/**?元素个数*/?
????private?transient?int?count;?
????/**?队列容量?*/?
????private?final?int?capacity;?
????/**?锁?*/?
????private?final?ReentrantLock?lock?=?new?ReentrantLock();?
????/**?notEmpty条件?*/?
????private?final?Condition?notEmpty?=?lock.newCondition();?
????/**?notFull条件?*/?
????private?final?Condition?notFull?=?lock.newCondition();?
????/**?构造方法?*/?
????public?LinkedBlockingDeque()?{?
????????this(Integer.MAX_VALUE);?
????}?
????public?LinkedBlockingDeque(int?capacity)?{?
????????if?(capacity?<=?0)?throw?new?IllegalArgumentException();?
????????this.capacity?=?capacity;?
????}?
????public?LinkedBlockingDeque(Collection<??extends?E>?c)?{?
????????this(Integer.MAX_VALUE);?
????????for?(E?e?:?c)?
????????????add(e);?
????}?
?
????/**
?????*?添加元素作为新的头节点
?????*/?
????private?boolean?linkFirst(E?e)?{?
????????if?(count?>=?capacity)?
????????????return?false;?
????????++count;?
????????Node<E>?f?=?first;?
????????Node<E>?x?=?new?Node<E>(e,?null,?f);?
????????first?=?x;?
????????if?(last?==?null)?
????????????last?=?x;?
????????else?
????????????f.prev?=?x;?
????????notEmpty.signal();?
????????return?true;?
????}? <