双向队列---Deque与LinkedBlockingDeque深入分析

阳光穿透心脏的1/2处 2022-08-07 13:41 192阅读 0赞

# 一、双向队列Deque #

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

![1354809676_3123.png][]

Deque在Queue的基础上增加了更多的操作方法。

![1354809693_2460.png][]

从上图可以看到，Deque不仅具有FIFO的Queue实现，也有FILO的实现，也就是不仅可以实现队列，也可以实现一个堆栈。

同时在Deque的体系结构图中可以看到，实现一个Deque可以使用数组（ArrayDeque），同时也可以使用链表（LinkedList），还可以同实现一个支持阻塞的线程安全版本队列LinkedBlockingDeque。

## 1、ArrayDeque实现Deque ##

![1354809706_2576.png][]

对于数组实现的Deque来说，数据结构上比较简单，只需要一个存储数据的数组以及头尾两个索引即可。由于数组是固定长度的，所以很容易就得到数组的头和尾，那么对于数组的操作只需要移动头和尾的索引即可。

特别说明的是ArrayDeque并不是一个固定大小的队列，每次队列满了以后就将队列容量扩大一倍（doubleCapacity()），因此加入一个元素总是能成功，而且也不会抛出一个异常。也就是说ArrayDeque是一个没有容量限制的队列。

同样继续性能的考虑，使用System.arraycopy复制一个数组比循环设置要高效得多。

### 1.1、ArrayDeque的源码解析 ###

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  //数组双端队列ArrayDeque的源码解析
2.  public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable\{
3.  /\*\*
4.   \* 存放队列元素的数组，数组的长度为“2的指数”
5.   \*/
6.  private transient E\[\] elements;
7.  /\*\*
8.   \*队列的头部索引位置，（被remove（）或pop（）操作的位置），当为空队列时，首尾index相同
9.   \*/
10. private transient int head;
11. /\*\*
12.  \* 队列的尾部索引位置，(被 addLast(E), add(E), 或 push(E)操作的位置).
13.  \*/
14. private transient int tail;
15. /\*\*
16.  \* 队列的最小容量（大小必须为“2的指数”）
17.  \*/
18. private static final int MIN\_INITIAL\_CAPACITY = 8;
19. // \*\*\*\*\*\* Array allocation and resizing utilities \*\*\*\*\*\*
20. /\*\*
21.  \* 根据所给的数组长度，得到一个比该长度大的最小的2^p的真实长度，并建立真实长度的空数组
22.  \*/
23. private void allocateElements(int numElements) \{
24. int initialCapacity = MIN\_INITIAL\_CAPACITY;
25. if (numElements >= initialCapacity) \{
26. initialCapacity = numElements;
27. initialCapacity |= (initialCapacity >>> 1);
28. initialCapacity |= (initialCapacity >>> 2);
29. initialCapacity |= (initialCapacity >>> 4);
30. initialCapacity |= (initialCapacity >>> 8);
31. initialCapacity |= (initialCapacity >>> 16);
32. initialCapacity++;
33. if (initialCapacity < 0) // Too many elements, must back off
34. initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
35. \}
36. elements = (E\[\]) new Object\[initialCapacity\];
37. \}
38. /\*\*
39.  \* 当队列首尾指向同一个引用时，扩充队列的容量为原来的两倍，并对元素重新定位到新数组中
40.  \*/
41. private void doubleCapacity() \{
42. assert head == tail;
43. int p = head;
44. int n = elements.length;
45. int r = n - p; // number of elements to the right of p
46. int newCapacity = n << 1;
47. if (newCapacity < 0)
48. throw new IllegalStateException("Sorry, deque too big");
49. Object\[\] a = new Object\[newCapacity\];
50. System.arraycopy(elements, p, a, 0, r);
51. System.arraycopy(elements, 0, a, r, p);
52. elements = (E\[\])a;
53. head = 0;
54. tail = n;
55. \}
56. /\*\*
57.  \* 拷贝队列中的元素到新数组中
58.  \*/
59. private <T> T\[\] copyElements(T\[\] a) \{
60. if (head < tail) \{
61. System.arraycopy(elements, head, a, 0, size());
62. \} else if (head > tail) \{
63. int headPortionLen = elements.length - head;
64. System.arraycopy(elements, head, a, 0, headPortionLen);
65. System.arraycopy(elements, 0, a, headPortionLen, tail);
66. \}
67. return a;
68. \}
69. /\*\*
70.  \* 默认构造队列，初始化一个长度为16的数组
71.  \*/
72. public ArrayDeque() \{
73. elements = (E\[\]) new Object\[16\];
74. \}
75. /\*\*
76.  \* 指定元素个数的构造方法
77.  \*/
78. public ArrayDeque(int numElements) \{
79. allocateElements(numElements);
80. \}
81. /\*\*
82.  \* 用一个集合作为参数的构造方法
83.  \*/
84. public ArrayDeque(Collection<? extends E> c) \{
85. allocateElements(c.size());
86. addAll(c);
87. \}
88. //插入和删除的方法主要是： addFirst(),addLast(), pollFirst(), pollLast()。
89. //其他的方法依赖于这些实现。
90. /\*\*
91.  \* 在双端队列的前端插入元素,元素为null抛异常
92.  \*/
93. public void addFirst(E e) \{
94. if (e == null)
95. throw new NullPointerException();
96. elements\[head = (head - 1) & (elements.length - 1)\] = e;
97. if (head == tail)
98. doubleCapacity();
99. \}
100. /\*\*
101.  \*在双端队列的末端插入元素，元素为null抛异常
102.  \*/
103. public void addLast(E e) \{
104. if (e == null)
105. throw new NullPointerException();
106. elements\[tail\] = e;
107. if ( (tail = (tail + 1) & (elements.length - 1)) == head)
108. doubleCapacity();
109. \}
110. /\*\*
111.  \* 在前端插入，调用addFirst实现，返回boolean类型
112.  \*/
113. public boolean offerFirst(E e) \{
114. addFirst(e);
115. return true;
116. \}
117. /\*\*
118.  \* 在末端插入，调用addLast实现，返回boolean类型
119.  \*/
120. public boolean offerLast(E e) \{
121. addLast(e);
122. return true;
123. \}
124. /\*\*
125.  \* 删除前端，调用pollFirst实现
126.  \*/
127. public E removeFirst() \{
128. E x = pollFirst();
129. if (x == null)
130. throw new NoSuchElementException();
131. return x;
132. \}
133. /\*\*
134.  \* 删除后端，调用pollLast实现
135.  \*/
136. public E removeLast() \{
137. E x = pollLast();
138. if (x == null)
139. throw new NoSuchElementException();
140. return x;
141. \}
142. //前端出对（删除前端）
143. public E pollFirst() \{
144. int h = head;
145. E result = elements\[h\]; // Element is null if deque empty
146. if (result == null)
147. return null;
148. elements\[h\] = null; // Must null out slot
149. head = (h + 1) & (elements.length - 1);
150. return result;
151. \}
152. //后端出对（删除后端）
153. public E pollLast() \{
154. int t = (tail - 1) & (elements.length - 1);
155. E result = elements\[t\];
156. if (result == null)
157. return null;
158. elements\[t\] = null;
159. tail = t;
160. return result;
161. \}
162. /\*\*
163.  \* 得到前端头元素
164.  \*/
165. public E getFirst() \{
166. E x = elements\[head\];
167. if (x == null)
168. throw new NoSuchElementException();
169. return x;
170. \}
171. /\*\*
172.  \* 得到末端尾元素
173.  \*/
174. public E getLast() \{
175. E x = elements\[(tail - 1) & (elements.length - 1)\];
176. if (x == null)
177. throw new NoSuchElementException();
178. return x;
179. \}
180. public E peekFirst() \{
181. return elements\[head\]; // elements\[head\] is null if deque empty
182. \}
183. public E peekLast() \{
184. return elements\[(tail - 1) & (elements.length - 1)\];
185. \}
186. /\*\*
187.  \* 移除此双端队列中第一次出现的指定元素（当从头部到尾部遍历双端队列时）。
188.  \*/
189. public boolean removeFirstOccurrence(Object o) \{
190. if (o == null)
191. return false;
192. int mask = elements.length - 1;
193. int i = head;
194. E x;
195. while ( (x = elements\[i\]) != null) \{
196. if (o.equals(x)) \{
197. delete(i);
198. return true;
199. \}
200. i = (i + 1) & mask;
201. \}
202. return false;
203. \}
204. /\*\*
205.  \* 移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
206.  \*/
207. public boolean removeLastOccurrence(Object o) \{
208. if (o == null)
209. return false;
210. int mask = elements.length - 1;
211. int i = (tail - 1) & mask;
212. E x;
213. while ( (x = elements\[i\]) != null) \{
214. if (o.equals(x)) \{
215. delete(i);
216. return true;
217. \}
218. i = (i - 1) & mask;
219. \}
220. return false;
221. \}
222. // \*\*\* 队列方法（Queue methods） \*\*\*
223. /\*\*
224.  \* add方法，添加到队列末端
225.  \*/
226. public boolean add(E e) \{
227. addLast(e);
228. return true;
229. \}
230. /\*\*
231.  \* 同上
232.  \*/
233. public boolean offer(E e) \{
234. return offerLast(e);
235. \}
236. /\*\*
237.  \* remove元素，删除队列前端
238.  \*/
239. public E remove() \{
240. return removeFirst();
241. \}
242. /\*\*
243.  \* 弹出前端（出对，删除前端）
244.  \*/
245. public E poll() \{
246. return pollFirst();
247. \}
248. public E element() \{
249. return getFirst();
250. \}
251. public E peek() \{
252. return peekFirst();
253. \}
254. // \*\*\* 栈 方法（Stack methods） \*\*\*
255. public void push(E e) \{
256. addFirst(e);
257. \}
258. public E pop() \{
259. return removeFirst();
260. \}
261. private void checkInvariants() \{ …… \}
262. private boolean delete(int i) \{ …… \}
263. // \*\*\* 集合方法（Collection Methods） \*\*\*
264. ……
265. // \*\*\* Object methods \*\*\*
266. ……
267. \}
268. 整体来说:1个数组，2个index（head 索引和tail索引）。实现比较简单，容易理解。

//数组双端队列ArrayDeque的源码解析
    public class ArrayDeque<E> extends AbstractCollection<E> implements Deque<E>, Cloneable, Serializable{
        /**
         * 存放队列元素的数组，数组的长度为“2的指数”
         */
        private transient E[] elements;
        /**
         *队列的头部索引位置，（被remove（）或pop（）操作的位置），当为空队列时，首尾index相同
         */
        private transient int head;
        /**
         * 队列的尾部索引位置，(被 addLast(E), add(E), 或 push(E)操作的位置).
         */
        private transient int tail;
        /**
         * 队列的最小容量（大小必须为“2的指数”）
         */
        private static final int MIN_INITIAL_CAPACITY = 8;
        // ******  Array allocation and resizing utilities ******
        /**
         * 根据所给的数组长度，得到一个比该长度大的最小的2^p的真实长度，并建立真实长度的空数组
         */
        private void allocateElements(int numElements) {
            int initialCapacity = MIN_INITIAL_CAPACITY;
            if (numElements >= initialCapacity) {
                initialCapacity = numElements;
                initialCapacity |= (initialCapacity >>>  1);
                initialCapacity |= (initialCapacity >>>  2);
                initialCapacity |= (initialCapacity >>>  4);
                initialCapacity |= (initialCapacity >>>  8);
                initialCapacity |= (initialCapacity >>> 16);
                initialCapacity++;
                if (initialCapacity < 0)   // Too many elements, must back off
                    initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
            }
            elements = (E[]) new Object[initialCapacity];
        }
        /**
         * 当队列首尾指向同一个引用时，扩充队列的容量为原来的两倍，并对元素重新定位到新数组中
         */
        private void doubleCapacity() {
            assert head == tail;
            int p = head;
            int n = elements.length;
            int r = n - p; // number of elements to the right of p
            int newCapacity = n << 1;
            if (newCapacity < 0)
                throw new IllegalStateException("Sorry, deque too big");
            Object[] a = new Object[newCapacity];
            System.arraycopy(elements, p, a, 0, r);
            System.arraycopy(elements, 0, a, r, p);
            elements = (E[])a;
            head = 0;
            tail = n;
        }
        /**
         * 拷贝队列中的元素到新数组中
         */
        private <T> T[] copyElements(T[] a) {
            if (head < tail) {
                System.arraycopy(elements, head, a, 0, size());
            } else if (head > tail) {
                int headPortionLen = elements.length - head;
                System.arraycopy(elements, head, a, 0, headPortionLen);
                System.arraycopy(elements, 0, a, headPortionLen, tail);
            }
            return a;
        }
        /**
         * 默认构造队列，初始化一个长度为16的数组
         */
        public ArrayDeque() {
            elements = (E[]) new Object[16];
        }
        /**
         * 指定元素个数的构造方法
         */
        public ArrayDeque(int numElements) {
            allocateElements(numElements);
        }
        /**
         * 用一个集合作为参数的构造方法
         */
        public ArrayDeque(Collection<? extends E> c) {
            allocateElements(c.size());
            addAll(c);
        }
        //插入和删除的方法主要是： addFirst(),addLast(), pollFirst(), pollLast()。
        //其他的方法依赖于这些实现。
        /**
         * 在双端队列的前端插入元素,元素为null抛异常
         */
        public void addFirst(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[head = (head - 1) & (elements.length - 1)] = e;
            if (head == tail)
                doubleCapacity();
        }
        /**
         *在双端队列的末端插入元素，元素为null抛异常
         */
        public void addLast(E e) {
            if (e == null)
                throw new NullPointerException();
            elements[tail] = e;
            if ( (tail = (tail + 1) & (elements.length - 1)) == head)
                doubleCapacity();
        }
        /**
         * 在前端插入，调用addFirst实现，返回boolean类型
         */
        public boolean offerFirst(E e) {
            addFirst(e);
            return true;
        }
        /**
         * 在末端插入，调用addLast实现，返回boolean类型
         */
        public boolean offerLast(E e) {
            addLast(e);
            return true;
        }
        /**
         * 删除前端，调用pollFirst实现
         */
        public E removeFirst() {
            E x = pollFirst();
            if (x == null)
                throw new NoSuchElementException();
            return x;
        }
        /**
         * 删除后端，调用pollLast实现
         */
        public E removeLast() {
            E x = pollLast();
            if (x == null)
                throw new NoSuchElementException();
            return x;
        }
        //前端出对（删除前端）
        public E pollFirst() {
            int h = head;
            E result = elements[h]; // Element is null if deque empty
            if (result == null)
                return null;
            elements[h] = null;     // Must null out slot
            head = (h + 1) & (elements.length - 1);
            return result;
        }
        //后端出对（删除后端）
        public E pollLast() {
            int t = (tail - 1) & (elements.length - 1);
            E result = elements[t];
            if (result == null)
                return null;
            elements[t] = null;
            tail = t;
            return result;
        }
        /**
         * 得到前端头元素
         */
        public E getFirst() {
            E x = elements[head];
            if (x == null)
                throw new NoSuchElementException();
            return x;
        }
        /**
         * 得到末端尾元素
         */
        public E getLast() {
            E x = elements[(tail - 1) & (elements.length - 1)];
            if (x == null)
                throw new NoSuchElementException();
            return x;
        }
        public E peekFirst() {
            return elements[head]; // elements[head] is null if deque empty
        }
        public E peekLast() {
            return elements[(tail - 1) & (elements.length - 1)];
        }
        /**
         * 移除此双端队列中第一次出现的指定元素（当从头部到尾部遍历双端队列时）。
         */
        public boolean removeFirstOccurrence(Object o) {
            if (o == null)
                return false;
            int mask = elements.length - 1;
            int i = head;
            E x;
            while ( (x = elements[i]) != null) {
                if (o.equals(x)) {
                    delete(i);
                    return true;
                }
                i = (i + 1) & mask;
            }
            return false;
        }
        /**
         * 移除此双端队列中最后一次出现的指定元素（当从头部到尾部遍历双端队列时）。
         */
        public boolean removeLastOccurrence(Object o) {
            if (o == null)
                return false;
            int mask = elements.length - 1;
            int i = (tail - 1) & mask;
            E x;
            while ( (x = elements[i]) != null) {
                if (o.equals(x)) {
                    delete(i);
                    return true;
                }
                i = (i - 1) & mask;
            }
            return false;
        }
        // *** 队列方法（Queue methods） ***
        /**
         * add方法，添加到队列末端
         */
        public boolean add(E e) {
            addLast(e);
            return true;
        }
        /**
         * 同上
         */
        public boolean offer(E e) {
            return offerLast(e);
        }
        /**
         * remove元素，删除队列前端
         */
        public E remove() {
            return removeFirst();
        }
        /**
         * 弹出前端（出对，删除前端）
         */
        public E poll() {
            return pollFirst();
        }
        public E element() {
            return getFirst();
        }
        public E peek() {
            return peekFirst();
        }
        // *** 栈 方法（Stack methods） ***
        public void push(E e) {
            addFirst(e);
        }
        public E pop() {
            return removeFirst();
        }
        private void checkInvariants() { ……    }
        private boolean delete(int i) {   ……   }
        // *** 集合方法（Collection Methods） ***
        ……
        // *** Object methods ***
        ……
    }
    整体来说:1个数组，2个index（head 索引和tail索引）。实现比较简单，容易理解。

## 2、LinkedList实现Deque ##

![1354809729_7889.png][]

对于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的数据结构。通常情况下从数据结构上就能看出这种实现的优缺点，这样就知道如何更好的使用工具了。

![1354809743_7567.png][]

从数据结构和功能需求上可以得到以下结论：

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

## 2、LinkedBlockingDeque源码分析 ##

**\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]

1.  public class LinkedBlockingDeque<E> extends AbstractQueue<E> implements BlockingDeque<E>, java.io.Serializable \{
2.  /\*\* 包含前驱和后继节点的双向链式结构 \*/
3.  static final class Node<E> \{
4.  E item;
5.  Node<E> prev;
6.  Node<E> next;
7.  Node(E x, Node<E> p, Node<E> n) \{
8.  item = x;
9.  prev = p;
10. next = n;
11. \}
12. \}
13. /\*\* 头节点 \*/
14. private transient Node<E> first;
15. /\*\* 尾节点 \*/
16. private transient Node<E> last;
17. /\*\* 元素个数\*/
18. private transient int count;
19. /\*\* 队列容量 \*/
20. private final int capacity;
21. /\*\* 锁 \*/
22. private final ReentrantLock lock = new ReentrantLock();
23. /\*\* notEmpty条件 \*/
24. private final Condition notEmpty = lock.newCondition();
25. /\*\* notFull条件 \*/
26. private final Condition notFull = lock.newCondition();
27. /\*\* 构造方法 \*/
28. public LinkedBlockingDeque() \{
29. this(Integer.MAX\_VALUE);
30. \}
31. public LinkedBlockingDeque(int capacity) \{
32. if (capacity <= 0) throw new IllegalArgumentException();
33. this.capacity = capacity;
34. \}
35. public LinkedBlockingDeque(Collection<? extends E> c) \{
36. this(Integer.MAX\_VALUE);
37. for (E e : c)
38. add(e);
39. \}
40. 
41. /\*\*
42.  \* 添加元素作为新的头节点
43.  \*/
44. private boolean linkFirst(E e) \{
45. if (count >= capacity)
46. return false;
47. \++count;
48. Node<E> f = first;
49. Node<E> x = new Node<E>(e, null, f);
50. first = x;
51. if (last == null)
52. last = x;
53. else
54. f.prev = x;
55. notEmpty.signal();
56. return true;
57. \}
58. /\*\*
59.  \* 添加尾元素
60.  \*/
61. private boolean linkLast(E e) \{
62. if (count >= capacity)
63. return false;
64. \++count;
65. Node<E> l = last;
66. Node<E> x = new Node<E>(e, l, null);
67. last = x;
68. if (first == null)
69. first = x;
70. else
71. l.next = x;
72. notEmpty.signal();
73. return true;
74. \}
75. /\*\*
76.  \* 返回并移除头节点
77.  \*/
78. private E unlinkFirst() \{
79. Node<E> f = first;
80. if (f == null)
81. return null;
82. Node<E> n = f.next;
83. first = n;
84. if (n == null)
85. last = null;
86. else
87. n.prev = null;
88. \--count;
89. notFull.signal();
90. return f.item;
91. \}
92. /\*\*
93.  \* 返回并移除尾节点
94.  \*/
95. private E unlinkLast() \{
96. Node<E> l = last;
97. if (l == null)
98. return null;
99. Node<E> p = l.prev;
100. last = p;
101. if (p == null)
102. first = null;
103. else
104. p.next = null;
105. \--count;
106. notFull.signal();
107. return l.item;
108. \}
109. /\*\*
110.  \* 移除节点x
111.  \*/
112. private void unlink(Node<E> x) \{
113. Node<E> p = x.prev;
114. Node<E> n = x.next;
115. if (p == null) \{ //x是头的情况
116. if (n == null)
117. first = last = null;
118. else \{
119. n.prev = null;
120. first = n;
121. \}
122. \} else if (n == null) \{ //x是尾的情况
123. p.next = null;
124. last = p;
125. \} else \{ //x是中间的情况
126. p.next = n;
127. n.prev = p;
128. \}
129. \--count;
130. notFull.signalAll();
131. \}
132. //--------------------------------- BlockingDeque 双端阻塞队列方法实现
133. public void addFirst(E e) \{
134. if (!offerFirst(e))
135. throw new IllegalStateException("Deque full");
136. \}
137. public void addLast(E e) \{
138. if (!offerLast(e))
139. throw new IllegalStateException("Deque full");
140. \}
141. public boolean offerFirst(E e) \{
142. if (e == null) throw new NullPointerException();
143. lock.lock();
144. try \{
145. return linkFirst(e);
146. \} finally \{
147. lock.unlock();
148. \}
149. \}
150. public boolean offerLast(E e) \{
151. if (e == null) throw new NullPointerException();
152. lock.lock();
153. try \{
154. return linkLast(e);
155. \} finally \{
156. lock.unlock();
157. \}
158. \}
159. public void putFirst(E e) throws InterruptedException \{
160. if (e == null) throw new NullPointerException();
161. lock.lock();
162. try \{
163. while (!linkFirst(e))
164. notFull.await();
165. \} finally \{
166. lock.unlock();
167. \}
168. \}
169. public void putLast(E e) throws InterruptedException \{
170. if (e == null) throw new NullPointerException();
171. lock.lock();
172. try \{
173. while (!linkLast(e))
174. notFull.await();
175. \} finally \{
176. lock.unlock();
177. \}
178. \}
179. public boolean offerFirst(E e, long timeout, TimeUnit unit)
180. throws InterruptedException \{
181. if (e == null) throw new NullPointerException();
182. long nanos = unit.toNanos(timeout);
183. lock.lockInterruptibly();
184. try \{
185. for (;;) \{
186. if (linkFirst(e))
187. return true;
188. if (nanos <= 0)
189. return false;
190. nanos = notFull.awaitNanos(nanos);
191. \}
192. \} finally \{
193. lock.unlock();
194. \}
195. \}
196. public boolean offerLast(E e, long timeout, TimeUnit unit)
197. throws InterruptedException \{
198. if (e == null) throw new NullPointerException();
199. long nanos = unit.toNanos(timeout);
200. lock.lockInterruptibly();
201. try \{
202. for (;;) \{
203. if (linkLast(e))
204. return true;
205. if (nanos <= 0)
206. return false;
207. nanos = notFull.awaitNanos(nanos);
208. \}
209. \} finally \{
210. lock.unlock();
211. \}
212. \}
213. public E removeFirst() \{
214. E x = pollFirst();
215. if (x == null) throw new NoSuchElementException();
216. return x;
217. \}
218. public E removeLast() \{
219. E x = pollLast();
220. if (x == null) throw new NoSuchElementException();
221. return x;
222. \}
223. public E pollFirst() \{
224. lock.lock();
225. try \{
226. return unlinkFirst();
227. \} finally \{
228. lock.unlock();
229. \}
230. \}
231. public E pollLast() \{
232. lock.lock();
233. try \{
234. return unlinkLast();
235. \} finally \{
236. lock.unlock();
237. \}
238. \}
239. public E takeFirst() throws InterruptedException \{
240. lock.lock();
241. try \{
242. E x;
243. while ( (x = unlinkFirst()) == null)
244. notEmpty.await();
245. return x;
246. \} finally \{
247. lock.unlock();
248. \}
249. \}
250. public E takeLast() throws InterruptedException \{
251. lock.lock();
252. try \{
253. E x;
254. while ( (x = unlinkLast()) == null)
255. notEmpty.await();
256. return x;
257. \} finally \{
258. lock.unlock();
259. \}
260. \}
261. public E pollFirst(long timeout, TimeUnit unit)
262. throws InterruptedException \{
263. long nanos = unit.toNanos(timeout);
264. lock.lockInterruptibly();
265. try \{
266. for (;;) \{
267. E x = unlinkFirst();
268. if (x != null)
269. return x;
270. if (nanos <= 0)
271. return null;
272. nanos = notEmpty.awaitNanos(nanos);
273. \}
274. \} finally \{
275. lock.unlock();
276. \}
277. \}
278. public E pollLast(long timeout, TimeUnit unit)
279. throws InterruptedException \{
280. long nanos = unit.toNanos(timeout);
281. lock.lockInterruptibly();
282. try \{
283. for (;;) \{
284. E x = unlinkLast();
285. if (x != null)
286. return x;
287. if (nanos <= 0)
288. return null;
289. nanos = notEmpty.awaitNanos(nanos);
290. \}
291. \} finally \{
292. lock.unlock();
293. \}
294. \}
295. public E getFirst() \{
296. E x = peekFirst();
297. if (x == null) throw new NoSuchElementException();
298. return x;
299. \}
300. public E getLast() \{
301. E x = peekLast();
302. if (x == null) throw new NoSuchElementException();
303. return x;
304. \}
305. public E peekFirst() \{
306. lock.lock();
307. try \{
308. return (first == null) ? null : first.item;
309. \} finally \{
310. lock.unlock();
311. \}
312. \}
313. public E peekLast() \{
314. lock.lock();
315. try \{
316. return (last == null) ? null : last.item;
317. \} finally \{
318. lock.unlock();
319. \}
320. \}
321. public boolean removeFirstOccurrence(Object o) \{
322. if (o == null) return false;
323. lock.lock();
324. try \{
325. for (Node<E> p = first; p != null; p = p.next) \{
326. if (o.equals(p.item)) \{
327. unlink(p);
328. return true;
329. \}
330. \}
331. return false;
332. \} finally \{
333. lock.unlock();
334. \}
335. \}
336. public boolean removeLastOccurrence(Object o) \{
337. if (o == null) return false;
338. lock.lock();
339. try \{
340. for (Node<E> p = last; p != null; p = p.prev) \{
341. if (o.equals(p.item)) \{
342. unlink(p);
343. return true;
344. \}
345. \}
346. return false;
347. \} finally \{
348. lock.unlock();
349. \}
350. \}
351. //---------------------------------- BlockingQueue阻塞队列 方法实现
352. public boolean add(E e) \{
353. addLast(e);
354. return true;
355. \}
356. public boolean offer(E e) \{
357. return offerLast(e);
358. \}
359. public void put(E e) throws InterruptedException \{
360. putLast(e);
361. \}
362. public boolean offer(E e, long timeout, TimeUnit unit)
363. throws InterruptedException \{
364. return offerLast(e, timeout, unit);
365. \}
366. public E remove() \{
367. return removeFirst();
368. \}
369. public E poll() \{
370. return pollFirst();
371. \}
372. public E take() throws InterruptedException \{
373. return takeFirst();
374. \}
375. public E poll(long timeout, TimeUnit unit) throws InterruptedException \{
376. return pollFirst(timeout, unit);
377. \}
378. public E element() \{
379. return getFirst();
380. \}
381. public E peek() \{
382. return peekFirst();
383. \}
384. //------------------------------------------- Stack 方法实现
385. public void push(E e) \{
386. addFirst(e);
387. \}
388. public E pop() \{
389. return removeFirst();
390. \}
391. //------------------------------------------- Collection 方法实现
392. public boolean remove(Object o) \{
393. return removeFirstOccurrence(o);
394. \}
395. public int size() \{
396. lock.lock();
397. try \{
398. return count;
399. \} finally \{
400. lock.unlock();
401. \}
402. \}
403. public boolean contains(Object o) \{
404. if (o == null) return false;
405. lock.lock();
406. try \{
407. for (Node<E> p = first; p != null; p = p.next)
408. if (o.equals(p.item))
409. return true;
410. return false;
411. \} finally \{
412. lock.unlock();
413. \}
414. \}
415. boolean removeNode(Node<E> e) \{
416. lock.lock();
417. try \{
418. for (Node<E> p = first; p != null; p = p.next) \{
419. if (p == e) \{
420. unlink(p);
421. return true;
422. \}
423. \}
424. return false;
425. \} finally \{
426. lock.unlock();
427. \}
428. \}
429. ……
430. \}

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;
        }
        /**
         * 添加尾元素
         */
        private boolean linkLast(E e) {
            if (count >= capacity)
                return false;
            ++count;
            Node<E> l = last;
            Node<E> x = new Node<E>(e, l, null);
            last = x;
            if (first == null)
                first = x;
            else
                l.next = x;
            notEmpty.signal();
            return true;
        }
        /**
         * 返回并移除头节点
         */
        private E unlinkFirst() {
            Node<E> f = first;
            if (f == null)
                return null;
            Node<E> n = f.next;
            first = n;
            if (n == null)
                last = null;
            else
                n.prev = null;
            --count;
            notFull.signal();
            return f.item;
        }
        /**
         * 返回并移除尾节点
         */
        private E unlinkLast() {
            Node<E> l = last;
            if (l == null)
                return null;
            Node<E> p = l.prev;
            last = p;
            if (p == null)
                first = null;
            else
                p.next = null;
            --count;
            notFull.signal();
            return l.item;
        }
        /**
         * 移除节点x
         */
        private void unlink(Node<E> x) {
            Node<E> p = x.prev;
            Node<E> n = x.next;
            if (p == null) {//x是头的情况
                if (n == null)
                    first = last = null;
                else {
                    n.prev = null;
                    first = n;
                }
            } else if (n == null) {//x是尾的情况
                p.next = null;
                last = p;
            } else {//x是中间的情况
                p.next = n;
                n.prev = p;
            }
            --count;
            notFull.signalAll();
        }
        //--------------------------------- BlockingDeque 双端阻塞队列方法实现
        public void addFirst(E e) {
            if (!offerFirst(e))
                throw new IllegalStateException("Deque full");
        }
        public void addLast(E e) {
            if (!offerLast(e))
                throw new IllegalStateException("Deque full");
        }
        public boolean offerFirst(E e) {
            if (e == null) throw new NullPointerException();
            lock.lock();
            try {
                return linkFirst(e);
            } finally {
                lock.unlock();
            }
        }
        public boolean offerLast(E e) {
            if (e == null) throw new NullPointerException();
            lock.lock();
            try {
                return linkLast(e);
            } finally {
                lock.unlock();
            }
        }
        public void putFirst(E e) throws InterruptedException {
            if (e == null) throw new NullPointerException();
            lock.lock();
            try {
                while (!linkFirst(e))
                    notFull.await();
            } finally {
                lock.unlock();
            }
        }
        public void putLast(E e) throws InterruptedException {
            if (e == null) throw new NullPointerException();
            lock.lock();
            try {
                while (!linkLast(e))
                    notFull.await();
            } finally {
                lock.unlock();
            }
        }
        public boolean offerFirst(E e, long timeout, TimeUnit unit)
            throws InterruptedException {
            if (e == null) throw new NullPointerException();
     long nanos = unit.toNanos(timeout);
            lock.lockInterruptibly();
            try {
                for (;;) {
                    if (linkFirst(e))
                        return true;
                    if (nanos <= 0)
                        return false;
                    nanos = notFull.awaitNanos(nanos);
                }
            } finally {
                lock.unlock();
            }
        }
        public boolean offerLast(E e, long timeout, TimeUnit unit)
            throws InterruptedException {
            if (e == null) throw new NullPointerException();
     long nanos = unit.toNanos(timeout);
            lock.lockInterruptibly();
            try {
                for (;;) {
                    if (linkLast(e))
                        return true;
                    if (nanos <= 0)
                        return false;
                    nanos = notFull.awaitNanos(nanos);
                }
            } finally {
                lock.unlock();
            }
        }
        public E removeFirst() {
            E x = pollFirst();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
        public E removeLast() {
            E x = pollLast();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
        public E pollFirst() {
            lock.lock();
            try {
                return unlinkFirst();
            } finally {
                lock.unlock();
            }
        }
        public E pollLast() {
            lock.lock();
            try {
                return unlinkLast();
            } finally {
                lock.unlock();
            }
        }
        public E takeFirst() throws InterruptedException {
            lock.lock();
            try {
                E x;
                while ( (x = unlinkFirst()) == null)
                    notEmpty.await();
                return x;
            } finally {
                lock.unlock();
            }
        }
        public E takeLast() throws InterruptedException {
            lock.lock();
            try {
                E x;
                while ( (x = unlinkLast()) == null)
                    notEmpty.await();
                return x;
            } finally {
                lock.unlock();
            }
        }
        public E pollFirst(long timeout, TimeUnit unit)
            throws InterruptedException {
     long nanos = unit.toNanos(timeout);
            lock.lockInterruptibly();
            try {
                for (;;) {
                    E x = unlinkFirst();
                    if (x != null)
                        return x;
                    if (nanos <= 0)
                        return null;
                    nanos = notEmpty.awaitNanos(nanos);
                }
            } finally {
                lock.unlock();
            }
        }
        public E pollLast(long timeout, TimeUnit unit)
            throws InterruptedException {
     long nanos = unit.toNanos(timeout);
            lock.lockInterruptibly();
            try {
                for (;;) {
                    E x = unlinkLast();
                    if (x != null)
                        return x;
                    if (nanos <= 0)
                        return null;
                    nanos = notEmpty.awaitNanos(nanos);
                }
            } finally {
                lock.unlock();
            }
        }
        public E getFirst() {
            E x = peekFirst();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
        public E getLast() {
            E x = peekLast();
            if (x == null) throw new NoSuchElementException();
            return x;
        }
        public E peekFirst() {
            lock.lock();
            try {
                return (first == null) ? null : first.item;
            } finally {
                lock.unlock();
            }
        }
        public E peekLast() {
            lock.lock();
            try {
                return (last == null) ? null : last.item;
            } finally {
                lock.unlock();
            }
        }
        public boolean removeFirstOccurrence(Object o) {
            if (o == null) return false;
            lock.lock();
            try {
                for (Node<E> p = first; p != null; p = p.next) {
                    if (o.equals(p.item)) {
                        unlink(p);
                        return true;
                    }
                }
                return false;
            } finally {
                lock.unlock();
            }
        }
        public boolean removeLastOccurrence(Object o) {
            if (o == null) return false;
            lock.lock();
            try {
                for (Node<E> p = last; p != null; p = p.prev) {
                    if (o.equals(p.item)) {
                        unlink(p);
                        return true;
                    }
                }
                return false;
            } finally {
                lock.unlock();
            }
        }
        //---------------------------------- BlockingQueue阻塞队列 方法实现
        public boolean add(E e) {
     addLast(e);
     return true;
        }
        public boolean offer(E e) {
     return offerLast(e);
        }
        public void put(E e) throws InterruptedException {
     putLast(e);
        }
        public boolean offer(E e, long timeout, TimeUnit unit)
            throws InterruptedException {
     return offerLast(e, timeout, unit);
        }
        public E remove() {
     return removeFirst();
        }
        public E poll() {
     return pollFirst();
        }
        public E take() throws InterruptedException {
     return takeFirst();
        }
        public E poll(long timeout, TimeUnit unit) throws InterruptedException {
     return pollFirst(timeout, unit);
        }
        public E element() {
     return getFirst();
        }
        public E peek() {
     return peekFirst();
        }
        //------------------------------------------- Stack 方法实现
        public void push(E e) {
     addFirst(e);
        }
        public E pop() {
     return removeFirst();
        }
        //------------------------------------------- Collection 方法实现
        public boolean remove(Object o) {
     return removeFirstOccurrence(o);
        }
        public int size() {
            lock.lock();
            try {
                return count;
            } finally {
                lock.unlock();
            }
        }
        public boolean contains(Object o) {
            if (o == null) return false;
            lock.lock();
            try {
                for (Node<E> p = first; p != null; p = p.next)
                    if (o.equals(p.item))
                        return true;
                return false;
            } finally {
                lock.unlock();
            }
        }
        boolean removeNode(Node<E> e) {
            lock.lock();
            try {
                for (Node<E> p = first; p != null; p = p.next) {
                    if (p == e) {
                        unlink(p);
                        return true;
                    }
                }
                return false;
            } finally {
                lock.unlock();
            }
        }
      ……
    }

## 3、LinkedBlockingDeque的优缺点 ##

有了上面的结论再来研究LinkedBlockingDeque的优缺点。

优点当然是功能足够强大，同时由于采用一个独占锁，因此实现起来也比较简单。所有对队列的操作都加锁就可以完成。同时独占锁也能够很好的支持双向阻塞的特性。

凡事有利必有弊。缺点就是由于独占锁，所以不能同时进行两个操作，这样性能上就大打折扣。从性能的角度讲LinkedBlockingDeque要比LinkedBlockingQueue要低很多，比CocurrentLinkedQueue就低更多了，这在高并发情况下就比较明显了。

前面分析足够多的Queue实现后，LinkedBlockingDeque的原理和实现就不值得一提了，无非是在独占锁下对一个链表的普通操作。

## 4、LinkedBlockingDeque的序列化、反序列化 ##

有趣的是此类支持序列化，但是Node并不支持序列化，因此fist/last就不能序列化，那么如何完成序列化/反序列化过程呢？

清单4 LinkedBlockingDeque的序列化、反序列化

> **\[java\]** [ view plain][view plain] [copy][view plain] [print][view plain] [?][view plain]
> 
> 1.  <span style="font-size: 14px;">private void writeObject(java.io.ObjectOutputStream s)
> 2.  throws java.io.IOException \{
> 3.  lock.lock();
> 4.  try \{
> 5.  // Write out capacity and any hidden stuff
> 6.  s.defaultWriteObject();
> 7.  // Write out all elements in the proper order.
> 8.  for (Node<E> p = first; p != null; p = p.next)
> 9.  s.writeObject(p.item);
> 10. // Use trailing null as sentinel
> 11. s.writeObject(null);
> 12. \} finally \{
> 13. lock.unlock();
> 14. \}
> 15. \}
> 16. 
> 17. private void readObject(java.io.ObjectInputStream s)
> 18. throws java.io.IOException, ClassNotFoundException \{
> 19. s.defaultReadObject();
> 20. count = 0;
> 21. first = null;
> 22. last = null;
> 23. // Read in all elements and place in queue
> 24. for (;;) \{
> 25. E item = (E)s.readObject();
> 26. if (item == null)
> 27. break;
> 28. add(item);
> 29. \}
> 30. \}
> 31. 
> 32. </span>
> 
>     <span style="font-size: 14px;">private void writeObject(java.io.ObjectOutputStream s)
>         throws java.io.IOException {
>         lock.lock();
>         try {
>             // Write out capacity and any hidden stuff
>             s.defaultWriteObject();
>             // Write out all elements in the proper order.
>             for (Node<E> p = first; p != null; p = p.next)
>                 s.writeObject(p.item);
>             // Use trailing null as sentinel
>             s.writeObject(null);
>         } finally {
>             lock.unlock();
>         }
>     }
>     
>     private void readObject(java.io.ObjectInputStream s)
>         throws java.io.IOException, ClassNotFoundException {
>         s.defaultReadObject();
>         count = 0;
>         first = null;
>         last = null;
>         // Read in all elements and place in queue
>         for (;;) {
>             E item = (E)s.readObject();
>             if (item == null)
>                 break;
>             add(item);
>         }
>     }
>     
>      </span>
> 
>   
>   
>

清单4 描述的是LinkedBlockingDeque序列化/反序列化的过程。序列化时将真正的元素写入输出流，最后还写入了一个null。读取的时候将所有对象列表读出来，如果读取到一个null就表示结束。这就是为什么写入的时候写入一个null的原因，因为没有将count写入流，所以就靠null来表示结束，省一个整数空间。

参考内容来源：

集合框架 Queue篇（1）---ArrayDeque  
http://hi.baidu.com/yao1111yao/item/1a1346f65a50d9c8521c266d  
集合框架 Queue篇（7）---LinkedBlockingDeque  
http://hi.baidu.com/yao1111yao/item/b1649cff2cf60be91a111f6d  
深入浅出 Java Concurrency (24): 并发容器 part 9 双向队列集合 Deque  
http://www.blogjava.net/xylz/archive/2010/08/12/328587.html  
深入浅出 Java Concurrency (25): 并发容器 part 10 双向并发阻塞队列 BlockingDeque  
http://www.blogjava.net/xylz/archive/2010/08/18/329227.html

[1354809676_3123.png]: https://img-my.csdn.net/uploads/201212/07/1354809676_3123.png
[1354809693_2460.png]: https://img-my.csdn.net/uploads/201212/07/1354809693_2460.png
[1354809706_2576.png]: https://img-my.csdn.net/uploads/201212/07/1354809706_2576.png
[view plain]: http://blog.csdn.net/vernonzheng/article/details/8267541#
[1354809729_7889.png]: https://img-my.csdn.net/uploads/201212/07/1354809729_7889.png
[1354809743_7567.png]: https://img-my.csdn.net/uploads/201212/07/1354809743_7567.png