Java的容器分成四個系列：Set, List, Queue,Map，除Map外，其餘三個都實作了Collection接口，List和Queue實作順序存儲，Map實作了K-V對。
本章分析其中實作較為簡單的Queue系列
一、類實作/繼承體系結構
為了對整個Queue實作/繼承體系有個全貌，先将體系結構圖畫出來：
二、關鍵資料成員
（1）存儲結構
PriorityQueue内部使用平衡二叉樹（小根堆）儲存元素，底層采用的資料結構是數組：
transientObject[] queue;
利用數組儲存二叉樹，那麼某個節點queue[n]的左子樹和右子樹分别是queue[2*n+1] 和queue[2*(n+1)]。
隊列queue的預設初始化大小(DEFAULT_INITIAL_CAPACITY)是11。
（2）比較運算符
優先級隊列要麼根據比較運算符進行排序，當運算符為null時，則根據元素的自然順序進行排序，最小值是queue[0]。
在PriorityQueue中，有一個成員變量用于記錄采取的比較運算符：
private final Comparator<? super E> comparator;
PriorityQueue要求外部傳入的Comparator比較器的類型必須是目前正在構造類的本身或者是其父類、祖父類。。。總之，在繼承層次上，大于等于它自身
為什麼這麼要求呢？
我琢磨着原因應該是這樣：
一個類的比較，最終要落到對其資料成員的操作，得到比較結果，子類是繼承了父類的資料成員（也許是部分，除掉一些在父類中的private成員，後面再讨論），也就是說，利用父類的Comparator進行比較時，對子類也是适用的，但反過來，子類可能定義了一些新的資料成員，是父類中沒有的，如果子類的Comparator在compare函數中使用這些新的資料成員比較，那麼對父類是不适用的，是以，子類可以使用父類的Comparator，反過來不行。
對于父類使用私有資料成員實作compare函數，分兩種情況：
一種子類可以通過構造函數，對父類的私有成員指派，如果構造函數中有對私有成員初始化的參數，那麼這種情況也會子類的比較起作用；
另一種情況，子類本身無法使用父類的私有資料成員，又沒有辦法改變它，那麼父類的comparator對子類的排序不起作用。
（3）修改次數
transientint modCount = 0;
資料成員modCount用于記錄queue隊列被修改的次數
（4）
三、構造函數
PriorityQueue提供了多種形式的構造函數，在此不一一列舉，就參數來說，主要包括，隊列(queue)初始化大小（initialCapacity）值、比較運算符、其他集合（包括PriorityQueue或者别的類型的集合，比如Set）
這裡要講下以下幾個構造函數：
public MyPriorityQueue(Collection<?extends E> c)
<? extends E>表示c中的元素(?)隻能是類型E的子類，這樣其實将一個子類對象指派給了一個父類對象，父類對象指向了一個子類對象，即多态，比如：
class Fruit {
}
class Apple extends Fruit {
}
List<Apple>appleL= newArrayList<Apple>();
appleL.add(new Apple("red"));
appleL.add(new Apple("green"));
Queue<Fruit>fruitQ= newPriorityQueue<Fruit>(appleL);
反過來就會出錯了，如果用一個存放Fruit的List作為PriorityQueue的構造函數的參數就會出錯了。
注意，上面是簡化的寫法，代碼是無法編譯通過的，因為PriorityQueue在存入對象時涉及到對象之間的比較，那就要去存入的對象之間可以進行比較，一種是傳遞了Comparator，實作對象的比較；另一種是類實作Comparable接口的比較函數compareTo，有些類本身支援比較，比如String，Integer，但對于自定義的類，那就要求實作者自己實作compareTo，當調用PriorityQueue構造函數時沒有傳遞Comparator，PriorityQueue在比較元素的時候就調用類的compareTo進行比較，如果二者都沒有提供，那就會抛異常了。下面是實作了compareTo的例子，如：
class Fruit implements Comparable<Fruit> {
protected String name;
public Fruit(String name) {
this.name = name;
}
public String getName() {
returnname;
}
@Override
publicint compareTo(Fruit o) {
returnthis.name.compareTo(o.getName());
}
}
class Apple extends Fruit {
public Apple(String name) {
super(name);
}
}
四、堆操作
PriorityQueue底層使用堆進行存儲，後面要講的隊列的增删改查很多時候涉及到對堆的操作。堆的操作主要包括兩個：
siftUp
siftDown
PriorityQueue實作了标準的heap上浮（sift up）和下沉（sift down）操作，隻是在進行元素比較時，不是直接比較元素大小，而是使用使用者傳入的comparator或者元素所屬類的compareTo成員函數來比較大小。
private voidsiftUp(int k, E x) {
if (comparator != null)
siftUpUsingComparator(k, x);
else
siftUpComparable(k, x);
}
@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;
Object e = queue[parent];
if (key.compareTo((E) e) >= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftUpUsingComparator(int k, Ex) {
while (k > 0) {
int parent = (k - 1) >>>1;
Object e = queue[parent];
if (comparator.compare(x, (E) e)>= 0)
break;
queue[k] = e;
k = parent;
}
queue[k] = x;
}
private void siftDown(int k, E x) {
if (comparator != null)
siftDownUsingComparator(k, x);
else
siftDownComparable(k, x);
}
@SuppressWarnings("unchecked")
private void siftDownComparable(int k, E x){
Comparable<? super E> key =(Comparable<? super E>)x;
int half = size >>> 1; // loop while a non-leaf
while (k < half) {
int child = (k << 1) + 1; //assume left child is least
Object c = queue[child];
int right = child + 1;
if (right < size &&
((Comparable<? super E>)c).compareTo((E) queue[right]) > 0)
c = queue[child = right];
if (key.compareTo((E) c) <= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
@SuppressWarnings("unchecked")
private void siftDownUsingComparator(int k,E x) {
int half = size >>> 1;
while (k < half) {
int child = (k << 1) + 1;
Object c = queue[child];
int right = child + 1;
if (right < size &&
comparator.compare((E) c, (E)queue[right]) > 0)
c = queue[child = right];
if (comparator.compare(x, (E) c)<= 0)
break;
queue[k] = c;
k = child;
}
queue[k] = x;
}
五、增
在往PriorityQueue中添加元素（add/offer）PriorityQueue在隊列滿的時候，自動實作擴容。擴容的操作是privatevoid grow(int minCapacity)實作的，
private void grow(int minCapacity) {
int oldCapacity = queue.length;
// Double size if small; else grow by50%
int newCapacity = oldCapacity +((oldCapacity < 64) ?
(oldCapacity + 2) :
(oldCapacity>> 1));
// overflow-conscious code
if (newCapacity - MAX_ARRAY_SIZE >0)
newCapacity =hugeCapacity(minCapacity);
queue = Arrays.copyOf(queue,newCapacity);
}
add的實作就是調用offer，首先檢查參數是否合法，PriorityQueue中不允許儲存null元素；接下來檢查隊列是否已滿，如果滿了，執行grow，擴容；然後将元素放入隊列數組，執行堆操作siftUp，當數組中不止一個元素時。
六、删
boolean remove(Object o)：删除對象o，首先利用indexOf(Object o)找到o的index，然後調用removeAt(private E removeAt(int i)):
privateE removeAt(int i) {
// assert i >= 0 && i <size;
modCount++;
int s = --size;
if (s == i) // removed last element
queue[i] = null;
else {
E moved = (E) queue[s];
queue[s] = null;
siftDown(i, moved);
if (queue[i] == moved) {
siftUp(i, moved);
if (queue[i] != moved)
return moved;
}
}
return null;
}
如果不是最後一個對象，删除對象後，需要執行siftDown/siftUp操作。
同樣的，poll操作是删除堆的根元素，即隊列的queue[0]元素，
public Epoll() {
if (size == 0)
return null;
int s = --size;
modCount++;
E result = (E) queue[0];
E x = (E) queue[s];
queue[s] = null;
//如果s==0，則說明此次删除了隊列裡的最後一個元素，
//删除後，隊列為空，無需執行siftDown
if (s != 0)
siftDown(0, x);
return result;
}
七、查
peek()：傳回隊列queue中index=0的元素，queue[0]；如果為空，則傳回null。
contains(Object o)：
public booleancontains(Object o) {
return indexOf(o) != -1;
}
總結：
（1） PriorityQueue實作可以作為學習堆資料結構的範例；
（2） PriorityQueue還有一個内部類private finalclass Itr，實作了疊代器；