一 概覽
image.png
由上圖可知，Queue分成只擴展AbstractQueue的繁涂，實現(xiàn)BlockingQueue接口的膘魄，實現(xiàn)TransferQueue的昧港，實現(xiàn)BlockingDeque的以及實現(xiàn)Deque接口的五類
二 PriorityQueue
- siftUp
/**
* Inserts item x at position k, maintaining heap invariant by
* promoting x up the tree until it is greater than or equal to
* its parent, or is the root.
*
* To simplify and speed up coercions and comparisons. the
* Comparable and Comparator versions are separated into different
* methods that are otherwise identical. (Similarly for siftDown.)
*
* @param k the position to fill
* @param x the item to insert
*/
@SuppressWarnings("unchecked")
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > 0) {
int parent = (k - 1) >>> 1; //不像siftDown那樣需要考慮找左右 孩子中的最小節(jié)點，siftUp只需要比較key跟parent節(jié)點即可
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
- siftDown
/**
* Inserts item x at position k, maintaining heap invariant by
* demoting x down the tree repeatedly until it is less than or
* equal to its children or is a leaf.
*
* @param k the position to fill
* @param x the item to insert
*/
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf 先看看是不是非葉子節(jié)點
while (k < half) {
int child = (k << 1) + 1; // assume left child is least 先假設左孩子節(jié)點最小
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > 0)
c = queue[child = right]; //如果右孩子更小逻住，則將right賦給child钟哥，把queue[right]賦給c
if (key.compareTo((E) c) <= 0) //如果目標節(jié)點值小于等于c，則break瞎访，否則腻贰，繼續(xù)循環(huán)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
- offer
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
modCount++;
int i = size;
if (i >= queue.length)
grow(i + 1); //擴容，與map和list的grow類似
size = i + 1;
if (i == 0)
queue[0] = e;
else
siftUp(i, e);
return true;
}
offer(E e)方法的實現(xiàn)思路如下：
1）首先檢查要添加的元素e是否為null扒秸，如果為null播演，則拋空指針異常，如果不為null伴奥，則進行2
2）判斷數(shù)組是否已滿宾巍，如果已滿，則進行擴容渔伯，否則將元素加入到數(shù)組末尾即可顶霞。但是由于這個數(shù)組表示的是一個“二叉堆”，因此還需要進行相應的調整操作，使得這個數(shù)組在添加元素之后依然保持的是二叉堆的特性选浑。
- poll
public E poll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
if (s != 0)
siftDown(0, x);
return result;
}
poll 方法的思想為：取出 queue[0] 元素蓝厌，然后將 queue[size-1] 插入到 queue[0] , 然后向下沉來保持二叉堆的特性。
