ArrayDeque 的結(jié)構(gòu)是一個循環(huán)數(shù)組渔呵，用作棧比Stack 性能優(yōu)秀酌摇，用作隊列比LinkedList 要好
image
1 成員變量及構(gòu)造函數(shù)
-
成員變量
因為是循環(huán)數(shù)組淫痰，所以本身就是一個數(shù)組
elements來存儲元素病瞳，并且有數(shù)組的容量践惑；而循環(huán)意味著在插入刪除元素的時候必定有兩個方向慎颗，所以會有head和tail乡恕，類似于雙指針。image -
構(gòu)造函數(shù)
image分析
allocateElements俯萎，原理上和HashMap中的計算容量的算法是差不多的imageimage以上函數(shù)是為了找到大于等于需要長度的最小2的冪整數(shù)傲宜。
2 增加
-
offerimage -
addimage -
pushimage
可以看到所有關(guān)于新增的操作都是調(diào)用了add 相關(guān)函數(shù)，源碼的解釋也如上圖所示夫啊。
3 刪除
-
removeimage -
popimage -
pollimage
4 查看
-
containsimage -
peekimage
5 擴容
擴容發(fā)生的時機在增加中有體現(xiàn)函卒，當(dāng)head == tail 的時候就會調(diào)用doubleCapacity 進行擴容
image
為什么不直接用一次System.arraycopy 來完成數(shù)組的遷移呢
image
如果直接一次性全部遷移就會面臨一個問題，head和tail分別指向哪里呢撇眯。
- 對于head报嵌，增加元素下標(biāo)自減虱咧，刪除元素自增；對于tail锚国，增加元素下標(biāo)自增腕巡，刪除元素自減。
- 一般情況下血筑，head指向的是頭元素绘沉，tail指向的是尾元素
基于上述兩方面的考慮，最終的遷移如圖所示豺总。
-
往頭部增加元素： 那么和一開始的分析一樣车伞，在
element.length - 1下標(biāo)往小下標(biāo)增加。 - 刪除頭部元素： 那么就是4 = 0园欣，并且head指向5帖世，這里的數(shù)字是指元素而不是下標(biāo)
- 往尾部增加元素： tail正常往右移動
- 刪除尾部元素： 3 = 0，并且tail指向3
創(chuàng)作不易沸枯，歡迎點贊日矫，收藏和分享啦！
