xylz,imxylz

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

Queue除了前面介紹的實(shí)現(xiàn)外，還有一種雙向的Queue實(shí)現(xiàn)Deque。這種隊列允許在隊列頭和尾部進(jìn)行入隊出隊操作，因此在功能上比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)隊列，也可以實(shí)現(xiàn)一個堆棧。

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

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

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

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

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

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

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

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

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

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

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