Queue接口定義了隊列數(shù)據(jù)結(jié)構(gòu)，元素是有序的(按插入順序)，先進先出沐兰。Queue接口相關(guān)的部分UML類圖如下：
DeQueue
DeQueue(Double-ended queue)為接口瞻佛，繼承了Queue接口，創(chuàng)建雙向隊列嘲玫，靈活性更強悦施，可以前向或后向迭代，在隊頭隊尾均可心插入或刪除元素去团。它的兩個主要實現(xiàn)類是ArrayDeque和LinkedList抡诞。
ArrayDeque （底層使用循環(huán)數(shù)組實現(xiàn)雙向隊列）
1.1 創(chuàng)建
public ArrayDeque() {
// 默認(rèn)容量為16
elements = new Object[16];
}
public ArrayDeque(int numElements) {
// 指定容量的構(gòu)造函數(shù)
allocateElements(numElements);
}
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;// 最小容量為8
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
// 如果要分配的容量大于等于8，擴大成2的冪（是為了維護頭土陪、尾下標(biāo)值）昼汗；否則使用最小容量8
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> 1);
initialCapacity |= (initialCapacity >>> 2);
initialCapacity |= (initialCapacity >>> 4);
initialCapacity |= (initialCapacity >>> 8);
initialCapacity |= (initialCapacity >>> 16);
initialCapacity++;
if (initialCapacity < 0) // Too many elements, must back off
initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
}
elements = new Object[initialCapacity];
}
1.2 add操作
add(E e) 調(diào)用 addLast(E e) 方法：
public void addLast(E e) {
if (e == null)
throw new NullPointerException("e == null");
elements[tail] = e; // 根據(jù)尾索引，添加到尾端
// 尾索引+1鬼雀，并與數(shù)組（length - 1）進行取‘&’運算顷窒，因為length是2的冪，所以（length-1）轉(zhuǎn)換為2進制全是1源哩，
// 所以如果尾索引值 tail 小于等于（length - 1）鞋吉，那么‘&’運算后仍為 tail 本身；如果剛好比（length - 1）大1時励烦，
// ‘&’運算后 tail 便為0（即回到了數(shù)組初始位置）谓着。正是通過與（length - 1）進行取‘&’運算來實現(xiàn)數(shù)組的雙向循環(huán)。
// 如果尾索引和頭索引重合了坛掠，說明數(shù)組滿了赊锚，進行擴容治筒。
if ((tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();// 擴容為原來的2倍
}
addFirst(E e) 的實現(xiàn)：
public void addFirst(E e) {
if (e == null)
throw new NullPointerException("e == null");
// 此處如果head為0，則-1（1111 1111 1111 1111 1111 1111 1111 1111）與（length - 1）進行取‘&’運算舷蒲，結(jié)果必然是（length - 1）耸袜，即回到了數(shù)組的尾部。
elements[head = (head - 1) & (elements.length - 1)] = e;
// 如果尾索引和頭索引重合了牲平，說明數(shù)組滿了堤框，進行擴容
if (head == tail)
doubleCapacity();
}
1.3 remove操作
remove()方法最終都會調(diào)對應(yīng)的poll()方法：
public E poll() {
return pollFirst();
}
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked") E result = (E) elements[h];
// Element is null if deque empty
if (result == null)
return null;
elements[h] = null; // Must null out slot
// 頭索引 + 1
head = (h + 1) & (elements.length - 1);
return result;
}
public E pollLast() {
// 尾索引 - 1
int t = (tail - 1) & (elements.length - 1);
@SuppressWarnings("unchecked") E result = (E) elements[t];
if (result == null)
return null;
elements[t] = null;
tail = t;
return result;
}
PriorityQueue（底層用數(shù)組實現(xiàn)堆的結(jié)構(gòu)）
優(yōu)先隊列跟普通的隊列不一樣，普通隊列是一種遵循FIFO規(guī)則的隊列欠拾，拿數(shù)據(jù)的時候按照加入隊列的順序拿取胰锌。 而優(yōu)先隊列每次拿數(shù)據(jù)的時候都會拿出優(yōu)先級最高的數(shù)據(jù)。
優(yōu)先隊列內(nèi)部維護著一個堆藐窄，每次取數(shù)據(jù)的時候都從堆頂拿數(shù)據(jù)（堆頂?shù)膬?yōu)先級最高）资昧，這就是優(yōu)先隊列的原理。
2.1 add荆忍，添加方法
public boolean add(E e) {
return offer(e); // add方法內(nèi)部調(diào)用offer方法
}
public boolean offer(E e) {
if (e == null) // 元素為空的話格带，拋出NullPointerException異常
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length) // 如果當(dāng)前用堆表示的數(shù)組已經(jīng)滿了，調(diào)用grow方法擴容
grow(i + 1); // 擴容
size = i + 1; // 元素個數(shù)+1
if (i == 0) // 堆還沒有元素的情況
queue[0] = e; // 直接給堆頂賦值元素
else // 堆中已有元素的情況
siftUp(i, e); // 重新調(diào)整堆刹枉，從下往上調(diào)整叽唱，因為新增元素是加到最后一個葉子節(jié)點
return true;
}
private void siftUp(int k, E x) {
if (comparator != null) // 比較器存在的情況下
siftUpUsingComparator(k, x); // 使用比較器調(diào)整
else // 比較器不存在的情況下
siftUpComparable(k, x); // 使用元素自身的比較器調(diào)整
}
private void siftUpUsingComparator(int k, E x) {
while (k > 0) { // 一直循環(huán)直到父節(jié)點還存在
int parent = (k - 1) >>> 1; // 找到父節(jié)點索引，等同于（k - 1）/ 2
Object e = queue[parent]; // 獲得父節(jié)點元素
// 新元素與父元素進行比較微宝，如果滿足比較器結(jié)果棺亭，直接跳出，否則進行調(diào)整
if (comparator.compare(x, (E) e) >= 0)
break;
queue[k] = e; // 進行調(diào)整蟋软，新位置的元素變成了父元素
k = parent; // 新位置索引變成父元素索引镶摘，進行遞歸操作
}
queue[k] = x; // 新添加的元素添加到堆中
}
2.2 poll，出隊方法
public E poll() {
if (size == 0)
return null;
int s = --size; // 元素個數(shù)-1
modCount++;
E result = (E) queue[0]; // 得到堆頂元素
E x = (E) queue[s]; // 最后一個葉子節(jié)點
queue[s] = null; // 最后1個葉子節(jié)點置空
if (s != 0)
siftDown(0, x); // 從上往下調(diào)整岳守，因為刪除元素是刪除堆頂?shù)脑? return result;
}
private void siftDown(int k, E x) {
if (comparator != null) // 比較器存在的情況下
siftDownUsingComparator(k, x); // 使用比較器調(diào)整
else // 比較器不存在的情況下
siftDownComparable(k, x); // 使用元素自身的比較器調(diào)整
}
private void siftDownUsingComparator(int k, E x) {
int half = size >>> 1; // 只需循環(huán)節(jié)點個數(shù)的一般即可
while (k < half) {
int child = (k << 1) + 1; // 得到父節(jié)點的左子節(jié)點索引凄敢，即（k * 2）+ 1
Object c = queue[child]; // 得到左子元素
int right = child + 1; // 得到父節(jié)點的右子節(jié)點索引
if (right < size &&
comparator.compare((E) c, (E) queue[right]) > 0) // 左子節(jié)點跟右子節(jié)點比較，取更大的值
c = queue[child = right];
if (comparator.compare(x, (E) c) <= 0) // 然后這個更大的值跟最后一個葉子節(jié)點比較
break;
queue[k] = c; // 新位置使用更大的值
k = child; // 新位置索引變成子元素索引湿痢，進行遞歸操作
}
queue[k] = x; // 最后一個葉子節(jié)點添加到合適的位置
}
2.3 remove涝缝，刪除隊列元素
public boolean remove(Object o) {
int i = indexOf(o); // 找到數(shù)據(jù)對應(yīng)的索引
if (i == -1) // 不存在的話返回false
return false;
else { // 存在的話調(diào)用removeAt方法，返回true
removeAt(i);
return true;
}
}
private E removeAt(int i) {
modCount++;
int s = --size; // 元素個數(shù)-1
if (s == i) // 如果是刪除最后一個葉子節(jié)點
queue[i] = null; // 直接置空譬重，刪除即可拒逮，堆還是保持特質(zhì)，不需要調(diào)整
else { // 如果是刪除的不是最后一個葉子節(jié)點
E moved = (E) queue[s]; // 獲得最后1個葉子節(jié)點元素
queue[s] = null; // 最后1個葉子節(jié)點置空
siftDown(i, moved); // 從上往下調(diào)整
if (queue[i] == moved) { // 如果從上往下調(diào)整完畢之后發(fā)現(xiàn)元素位置沒變臀规，從下往上調(diào)整
siftUp(i, moved); // 從下往上調(diào)整
if (queue[i] != moved)
return moved;
}
}
return null;
}
先執(zhí)行 siftDown() 下濾過程：
再執(zhí)行 siftUp() 上濾過程：
2.4 總結(jié)和同步的問題
1消恍、jdk內(nèi)置的優(yōu)先隊列PriorityQueue內(nèi)部使用一個堆維護數(shù)據(jù)，每當(dāng)有數(shù)據(jù)add進來或者poll出去的時候會對堆做從下往上的調(diào)整和從上往下的調(diào)整以现。
2狠怨、PriorityQueue不是一個線程安全的類，如果要在多線程環(huán)境下使用邑遏，可以使用 PriorityBlockingQueue 這個優(yōu)先阻塞隊列佣赖。其中add、poll记盒、remove方法都使用 ReentrantLock 鎖來保持同步憎蛤，take() 方法中如果元素為空，則會一直保持阻塞纪吮。
