前面介紹過一個隊(duì)列的實(shí)現(xiàn)-PriorityQueue绍绘，現(xiàn)在我們介紹一下ArrayDeque.
從它的名字中稿壁，我們可以看到，其內(nèi)部結(jié)構(gòu)是一個數(shù)組酵使，并且它是一個Deque.
我們首先看一下這個類的文檔注釋:
從中我們可以提取出來幾點(diǎn)重要信息:
- 內(nèi)部數(shù)組的容量會自動增加趴乡，如果必要的話
- 這個類不是線程安全的
- 這個類是Fail-Fast的
- 如果把它當(dāng)做棧來使用对省，那么它比Stack這個數(shù)據(jù)結(jié)構(gòu)更快(這點(diǎn)我也不知道是什么原因，我感覺它應(yīng)該比Stack慢．因?yàn)镾tack只需要在棧頂增加和刪除數(shù)據(jù)晾捏，時間復(fù)雜度均為O(1),而ArrayDeque在刪除數(shù)據(jù)時由于還要涉及到數(shù)據(jù)移動的問題蒿涎，所以即使單純的增加和刪除數(shù)據(jù)的時間復(fù)雜度為O(1)，但是再加上數(shù)據(jù)移動的開銷惦辛，其不是應(yīng)該比Stack慢嗎?)
- 如果把它當(dāng)做隊(duì)列來使用劳秋，那么它比LinkedList更快(這點(diǎn)也不理解，因?yàn)長inkedList中有一個指向鏈表末尾的指針，并且每個節(jié)點(diǎn)都有指向前一個節(jié)點(diǎn)的指針玻淑，那么在插入數(shù)據(jù)時時間復(fù)雜度也為O(1)啊)
- 它的所有操作的時間復(fù)雜度基本上都是O(1),除了一些需要通過遍歷找到數(shù)據(jù)位置的操作嗽冒，比如remove(Object), removeFirstOccurence(Object), removeLastOccurrence(Object), contains(Object)等．
ArrayDeque的內(nèi)部數(shù)據(jù)結(jié)構(gòu)
其內(nèi)部數(shù)據(jù)容器為一個數(shù)組, Object[] elements.
然后還有兩個屬性，head和tail补履，分別表示elements中添坊，第一個數(shù)據(jù)所在的位置以及最后一個數(shù)據(jù)所在的位置．
ArrayDeque的重要操作
ArrayDeque中，有這么兩個方法箫锤，用于擴(kuò)容:
這一個方法用于將容量擴(kuò)展兩倍并拷貝數(shù)據(jù).
這個方法用于找到跟numElements接近但是比它大的2的整數(shù)次冪．如果numElements已經(jīng)是2的整數(shù)次冪贬蛙，則取它的兩倍.
其他的方法就很簡單了．就是向隊(duì)首和隊(duì)尾插入刪除數(shù)據(jù)的一些方法．這里就不一一介紹了．
