xylz,imxylz

有一段時間沒有更新了。接著上節繼續吧。

Queue除了前面介紹的實現外，還有一種雙向的Queue實現Deque。這種隊列允許在隊列頭和尾部進行入隊出隊操作，因此在功能上比Queue顯然要更復雜。下圖描述的是Deque的完整體系圖。需要說明的是LinkedList也已經加入了Deque的一部分（LinkedList是從jdk1.2 開始就存在數據結構）。

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

從上圖可以看到，Deque不僅具有FIFO的Queue實現，也有FILO的實現，也就是不僅可以實現隊列，也可以實現一個堆棧。

同時在Deque的體系結構圖中可以看到，實現一個Deque可以使用數組（ArrayDeque），同時也可以使用鏈表（LinkedList），還可以同實現一個支持阻塞的線程安全版本隊列LinkedBlockingDeque。

對于數組實現的Deque來說，數據結構上比較簡單，只需要一個存儲數據的數組以及頭尾兩個索引即可。由于數組是固定長度的，所以很容易就得到數組的頭和尾，那么對于數組的操作只需要移動頭和尾的索引即可。

特別說明的是ArrayDeque并不是一個固定大小的隊列，每次隊列滿了以后就將隊列容量擴大一倍（doubleCapacity()），因此加入一個元素總是能成功，而且也不會拋出一個異常。也就是說ArrayDeque是一個沒有容量限制的隊列。

同樣繼續性能的考慮，使用System.arraycopy復制一個數組比循環設置要高效得多。

對于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也是一個沒有容量限制的隊列，因此入隊列（不管是從頭部還是尾部）總能成功。

上面描述的ArrayDeque和LinkedList是兩種不同方式的實現，通常在遍歷和節省內存上ArrayDeque更高效（索引更快，另外不需要Entry對象），但是在隊列擴容下LinkedList更靈活，因為不需要復制原始的隊列，某些情況下可能更高效。

同樣需要注意的上述兩個實現都不是線程安全的，因此只適合在單線程環境下使用，下面章節要介紹的LinkedBlockingDeque就是線程安全的可阻塞的Deque。事實上也應該是功能最強大的Queue實現，當然了實現起來也許會復雜一點。