xylz,imxylz

有一段時(shí)間沒有更新了。接著上節(jié)繼續(xù)吧。

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

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

從上圖可以看到，Deque不僅具有FIFO的Queue實(shí)現(xiàn)，也有FILO的實(shí)現(xiàn)，也就是不僅可以實(shí)現(xiàn)隊(duì)列，也可以實(shí)現(xiàn)一個(gè)堆棧。

同時(shí)在Deque的體系結(jié)構(gòu)圖中可以看到，實(shí)現(xiàn)一個(gè)Deque可以使用數(shù)組（ArrayDeque），同時(shí)也可以使用鏈表（LinkedList），還可以同實(shí)現(xiàn)一個(gè)支持阻塞的線程安全版本隊(duì)列LinkedBlockingDeque。

對(duì)于數(shù)組實(shí)現(xiàn)的Deque來說，數(shù)據(jù)結(jié)構(gòu)上比較簡(jiǎn)單，只需要一個(gè)存儲(chǔ)數(shù)據(jù)的數(shù)組以及頭尾兩個(gè)索引即可。由于數(shù)組是固定長(zhǎng)度的，所以很容易就得到數(shù)組的頭和尾，那么對(duì)于數(shù)組的操作只需要移動(dòng)頭和尾的索引即可。

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

同樣繼續(xù)性能的考慮，使用System.arraycopy復(fù)制一個(gè)數(shù)組比循環(huán)設(shè)置要高效得多。

對(duì)于LinkedList本身而言，數(shù)據(jù)結(jié)構(gòu)就更簡(jiǎn)單了，除了一個(gè)size用來記錄大小外，只有head一個(gè)元素Entry。對(duì)比Map和Queue的其它數(shù)據(jù)結(jié)構(gòu)可以看到這里的Entry有兩個(gè)引用，是雙向的隊(duì)列。

在示意圖中，LinkedList總是有一個(gè)“傀儡”節(jié)點(diǎn)，用來描述隊(duì)列“頭部”，但是并不表示頭部元素，它是一個(gè)執(zhí)行null的空節(jié)點(diǎn)。

隊(duì)列一開始只有head一個(gè)空元素，然后從尾部加入E1(add/addLast)，head和E1之間建立雙向鏈接。然后繼續(xù)從尾部加入E2，E2就在head和E1之間建立雙向鏈接。最后從隊(duì)列的頭部加入E3(push/addFirst)，于是E3就在E1和head之間鏈接雙向鏈接。

雙向鏈表的數(shù)據(jù)結(jié)構(gòu)比較簡(jiǎn)單，操作起來也比較容易，從事從“傀儡”節(jié)點(diǎn)開始，“傀儡”節(jié)點(diǎn)的下一個(gè)元素就是隊(duì)列的頭部，前一個(gè)元素是隊(duì)列的尾部，換句話說，“傀儡”節(jié)點(diǎn)在頭部和尾部之間建立了一個(gè)通道，是整個(gè)隊(duì)列形成一個(gè)循環(huán)，這樣就可以從任意一個(gè)節(jié)點(diǎn)的任意一個(gè)方向能遍歷完整的隊(duì)列。

同樣LinkedList也是一個(gè)沒有容量限制的隊(duì)列，因此入隊(duì)列（不管是從頭部還是尾部）總能成功。

上面描述的ArrayDeque和LinkedList是兩種不同方式的實(shí)現(xiàn)，通常在遍歷和節(jié)省內(nèi)存上ArrayDeque更高效（索引更快，另外不需要Entry對(duì)象），但是在隊(duì)列擴(kuò)容下LinkedList更靈活，因?yàn)椴恍枰獜?fù)制原始的隊(duì)列，某些情況下可能更高效。

同樣需要注意的上述兩個(gè)實(shí)現(xiàn)都不是線程安全的，因此只適合在單線程環(huán)境下使用，下面章節(jié)要介紹的LinkedBlockingDeque就是線程安全的可阻塞的Deque。事實(shí)上也應(yīng)該是功能最強(qiáng)大的Queue實(shí)現(xiàn)，當(dāng)然了實(shí)現(xiàn)起來也許會(huì)復(fù)雜一點(diǎn)。