title: PriorityQueue and Queue源碼剖析
date: 2018-3-3 23:18:40
categories:
- JDK
tags:
- JDK
- 源碼學習
此博文過長，純屬自己記錄的筆記，慎入。
ArrayDeque
是一個雙向隊列，隊列的兩個口都可以入隊和出隊操作。再進一步說，其實ArrayDeque可以說成是一個雙向循環隊列
defination
public class ArrayDeque<E> extends AbstractCollection<E>
implements Deque<E>, Cloneable, Serializable
{
}
從ArrayDeque的定義可以看到，它繼承AbstractCollection，實作了Deque，Cloneable，Serializable接口。不知道看到這裡你會不會發現什麼，Deque接口我們在LinkedList中見過，LinkedList也是實作Deque接口的。Deque是一個雙端隊列，它實作于Queue接口，就是在隊列的同一端即可以入隊又可以出隊，是以Deque即可以作為隊列又可以作為棧使用。
欲知Dequeue先知Queue,jdk1.8源碼如下:
public interface Queue<E> extends Collection<E> {
// 增加一個元素到隊尾，如果隊列已滿，則抛出一個IIIegaISlabEepeplian異常
boolean add(E e);
// 添加一個元素到隊尾并傳回true，如果隊列已滿，則傳回false
boolean offer(E e);
// 移除并傳回隊列頭部的元素，如果隊列為空，則抛出一個NoSuchElementException異常
E remove();
// 移除并返問隊列頭部的元素，如果隊列為空，則傳回null
E poll();
// 傳回隊列頭部的元素，如果隊列為空，則抛出一個NoSuchElementException異常
E element();
// 返問隊列頭部的元素，如果隊列為空，則傳回null
E peek()
}
Queue的定義和Stack的定義差不多了。ArrayDeque并不是一個固定大小的隊列，每次隊列滿了就會進行擴容，除非擴容至超過int的邊界，才會抛出異常。是以這裡的add和offer幾乎是沒有差別的。
// 底層用數組存儲元素
private transient E[] elements;
// 隊列的頭部元素索引（即将pop出的一個）
private transient int head;
// 隊列下一個要添加的元素索引
private transient int tail;
// 最小的初始化容量大小，需要為2的n次幂
private static final int MIN_INITIAL_CAPACITY = ;
這裡的MIN_INITIAL_CAPACITY要求是2的整數次幂，我們知道在Hashmap裡面，bucket桶的長度是要求2的整數次幂，這裡又是什麼原因呢？
看一下ArrayDeque的構造函數就知道了。
/**
* 預設構造方法，數組的初始容量為16
*/
public ArrayDeque() {
elements = (E[]) new Object[];
}
/**
* 使用一個指定的初始容量構造一個ArrayDeque
*/
public ArrayDeque( int numElements) {
allocateElements(numElements);
}
/**
* 構造一個指定Collection集合參數的ArrayDeque
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
/**
* 配置設定合适容量大小的數組，確定初始容量是大于指定numElements的最小的2的n次幂
*/
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// 找到大于指定容量的最小的2的n次幂
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
// 如果指定的容量小于初始容量8，則執行一下if中的邏輯操作
if (numElements >= initialCapacity) {
initialCapacity = numElements;
initialCapacity |= (initialCapacity >>> );
initialCapacity |= (initialCapacity >>> );
initialCapacity |= (initialCapacity >>> );
initialCapacity |= (initialCapacity >>> );
initialCapacity |= (initialCapacity >>> );
initialCapacity++;
if (initialCapacity < ) // Too many elements, must back off
initialCapacity >>>= ; // Good luck allocating 2 ^ 30 elements
}
elements = (E[]) new Object[initialCapacity];
}
這裡的代碼是抄别人的，期初我也看不懂，大概的意思就是說，每次需要找到剛好大于numElementsd的2的整數次幂的整數，這些位運算，你自己去算吧。
入隊操作
我們經常用到就是 add(), offer(),分别調用 addLast(), offerLast()這幾個方法了。不同的是 add()系列的方法會抛異常，而offer()系列的會傳回true or false. remove() poll()同理。
/**
* 增加一個元素，如果隊列已滿，則抛出一個IIIegaISlabEepeplian異常
*/
public boolean add(E e) {
// 調用addLast方法，将元素添加到隊尾
addLast(e);
return true;
}
/**
* 添加一個元素
*/
public boolean offer(E e) {
// 調用offerLast方法，将元素添加到隊尾
return offerLast(e);
}
/**
* 在隊尾添加一個元素
*/
public boolean offerLast(E e) {
// 調用addLast方法，将元素添加到隊尾
addLast(e);
return true;
}
/**
* 将元素添加到隊尾
*/
public void addLast(E e) {
// 如果元素為null，咋抛出空指針異常
if (e == null)
throw new NullPointerException();
// 将元素e放到數組的tail位置
elements[tail ] = e;
// 判斷tail和head是否相等，如果相等則對數組進行擴容
if ( (tail = (tail + ) & ( elements.length - )) == head)
// 進行兩倍擴容
doubleCapacity();
}
(tail = (tail + 1) & ( elements.length - 1)) == head)
最為精妙！
偷張别人的圖解釋一下。
我們假設隊列初始容量為8，初始化添加，A,B,C,D四元素。分别對應數組下标0,1,2,3,但是因為這是雙端隊列，經過一段時間的出隊，入隊，可能會變成上圖，右邊的情況。
那麼tail到達了數組末尾，再添加元素的話，怎麼辦， 直接擴容嗎？ 前面還有一段呢？ 答案是不會擴容，會把元素填充到前面缺失的位置，一直到這個數組是真正的滿了，才會擴容。(tail = (tail + 1) & ( elements.length - 1))隻會在 head 和 tail指針相鄰才會 == head然後就開始擴容。
Javaer們把這個叫做，循環數組！
ArrayDeque的擴容
/**
* 數組将要滿了的時候(tail==head)将，數組進行2倍擴容
*/
private void doubleCapacity() {
// 驗證head和tail是否相等
assert head == tail;
int p = head ;
// 記錄數組的長度
int n = elements .length;
// 計算head後面的元素個數，這裡沒有采用jdk中自帶的英文注釋right，是因為所謂隊列的上下左右，隻是我們看的方位不同而已，如果上面畫的圖，這裡就應該是left而非right
int r = n - p; // number of elements to the right of p
// 将數組長度擴大2倍
int newCapacity = n << ;
// 如果此時長度小于0，則抛出IllegalStateException異常，什麼時候newCapacity會小于0呢，前面我們說過了int值<<1越界
if (newCapacity < )
throw new IllegalStateException( "Sorry, deque too big" );
// 建立一個長度是原數組大小2倍的新數組
Object[] a = new Object[newCapacity];
// 将原數組head後的元素都拷貝值新數組
System. arraycopy(elements, p, a, , r);
// 将原數組head前的元素都拷貝到新數組
System. arraycopy(elements, , a, r, p);
// 将新數組指派給elements
elements = (E[])a;
// 重置head為數組的第一個位置索引0
head = ;
// 重置tail為數組的最後一個位置索引+1（(length - 1) + 1）
tail = n;
}
兩次複制，是因為，這個數組是分為兩段的。
出隊
/**
* 移除并傳回隊列頭部的元素，如果隊列為空，則抛出一個NoSuchElementException異常
*/
public E remove() {
// 調用removeFirst方法，移除隊頭的元素
return removeFirst();
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E removeFirst() {
// 調用pollFirst方法，移除并傳回隊頭的元素
E x = pollFirst();
// 如果隊列為空，則抛出NoSuchElementException異常
if (x == null)
throw new NoSuchElementException();
return x;
}
/**
* 移除并返問隊列頭部的元素，如果隊列為空，則傳回null
*/
public E poll() {
// 調用pollFirst方法，移除并傳回隊頭的元素
return pollFirst();
}
public E pollFirst() {
int h = head ;
// 取出數組隊頭位置的元素
E result = elements[h]; // Element is null if deque empty
// 如果數組隊頭位置沒有元素，則傳回null值
if (result == null)
return null;
// 将數組隊頭位置置空，也就是删除元素
elements[h] = null; // Must null out slot
// 将head指針往前移動一個位置
head = (h + ) & (elements .length - );
// 将隊頭元素傳回
return result;
}
PriorityQueue
自己在寫一些算法題目的時候，特别是一些面試刁鑽的搜尋問題時(google有一道無序數組，尋找第K大元素，就是用構造K堆來實作的)，都會用到堆排序，其實JDK已經為我們封裝好了一個類似對結構的優先隊列，就是這個PriorityQueue 也叫 二叉堆。
其實就是一顆完全二叉樹（二叉堆），特點：在第n層深度被填滿之前，不會開始填第n+1層深度，而且元素插入是從左往右填滿。
基于這個特點，二叉堆又可以用數組來表示而不是用連結清單
public class PriorityQueue<E> extends AbstractQueue<E>
implements java.io.Serializable {
}
底層存儲
// 預設初始化大小
privatestaticfinalintDEFAULT_INITIAL_CAPACITY = ;
//
/**
* Priority queue represented as a balanced binary heap: the two
* children of queue[n] are queue[2*n+1] and queue[2*(n+1)]. The
* priority queue is ordered by comparator, or by the elements'
* natural ordering, if comparator is null: For each node n in the
* heap and each descendant d of n, n <= d. The element with the
* lowest value is in queue[0], assuming the queue is nonempty.
*/
private transient Object[] queue ;
// 隊列的大小
private int size = ;
// 比較器
private final Comparator<? super E> comparator;
// 版本号
private transient int modCount = ;
看上面的英文注釋，我的英語不好也看懂了，哈哈。
PriorityQueue()
public PriorityQueue() {
this(DEFAULT_INITIAL_CAPACITY, null); // null 為比較器，預設null
}
public PriorityQueue( int initialCapacity) {
this(initialCapacity, null);
}
/**
* 使用指定的初始大小和比較器來構造一個優先隊列
*/
public PriorityQueue( int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
// 初始大小不允許小于1
if (initialCapacity < )
throw new IllegalArgumentException();
// 使用指定初始大小建立數組
this.queue = new Object[initialCapacity];
// 初始化比較器
this.comparator = comparator;
}
/**
* 構造一個指定Collection集合參數的優先隊列
*/
public PriorityQueue(Collection<? extends E> c) {
// 從集合c中初始化資料到隊列
initFromCollection(c);
// 如果集合c是包含比較器Comparator的(SortedSet/PriorityQueue)，則使用集合c的比較器來初始化隊列的Comparator
if (c instanceof SortedSet)
comparator = (Comparator<? super E>)
((SortedSet<? extends E>)c).comparator();
else if (c instanceof PriorityQueue)
comparator = (Comparator<? super E>)
((PriorityQueue<? extends E>)c).comparator();
// 如果集合c沒有包含比較器，則預設比較器Comparator為空
else {
comparator = null;
// 調用heapify方法重新将資料調整為一個二叉堆
heapify();
}
}
/**
* 構造一個指定PriorityQueue參數的優先隊列
*/
public PriorityQueue(PriorityQueue<? extends E> c) {
comparator = (Comparator<? super E>)c.comparator();
initFromCollection(c);
}
/**
* 構造一個指定SortedSet參數的優先隊列
*/
public PriorityQueue(SortedSet<? extends E> c) {
comparator = (Comparator<? super E>)c.comparator();
initFromCollection(c);
}
/**
* 從集合中初始化資料到隊列
*/
private void initFromCollection(Collection<? extends E> c) {
// 将集合Collection轉換為數組a
Object[] a = c.toArray();
// If c.toArray incorrectly doesn't return Object[], copy it.
// 如果轉換後的數組a類型不是Object數組，則轉換為Object數組
if (a.getClass() != Object[].class)
a = Arrays. copyOf(a, a.length, Object[]. class);
// 将數組a指派給隊列的底層數組queue
queue = a;
// 将隊列的元素個數設定為數組a的長度
size = a.length ;
}
add() 和 offer()
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
//如果壓入的元素為null 抛出異常
int i = size;
if (i >= queue.length)
grow(i + );
//如果數組的大小不夠擴充
size = i + ;
if (i == )
queue[] = e;
//如果隻有一個元素之間放在堆頂
else
siftUp(i, e);
//否則調用siftUp函數從下往上調整堆。
return true;
}
這兩個方法都是向這個小堆裡面添加一個元素，add()方法體内，也是調用的offer()啦。
public boolean add(E e) {
return offer(e);
}
offer()的源碼是這樣的：
public boolean offer(E e) {
if (e == null)
throw new NullPointerException();
//如果壓入的元素為null 抛出異常
int i = size;
if (i >= queue.length)
grow(i + );
//如果數組的大小不夠擴充
size = i + ;
if (i == )
queue[] = e;
//如果隻有一個元素之間放在堆頂
else
siftUp(i, e);
//否則調用siftUp函數從下往上調整堆。
return true;
}
和我自己寫得堆排序裡面的，交換過程差不多。
1. 優先隊列無法存放 null
2. 元素進堆之後，如果數組大小不夠，進行擴充數組，
3. 從下往上，調整堆。siftUp(i,e)
private void siftUpComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>) x;
while (k > ) {
int parent = (k - ) >>> ;
Object e = queue[parent];
if (key.compareTo((E) e) >= )
break;
queue[k] = e;
k = parent;
}
queue[k] = key;
}
就是一個不斷比較交換的過程，不再贅述。
Poll() remove()
poll 方法每次從 PriorityQueue 的頭部删除一個節點，也就是從小頂堆的堆頂删除一個節點，而remove（）不僅可以删除頭節點而且還可以用 remove(Object o) 來删除堆中的與給定對象相同的最先出現的對象。
poll() 方法就很好了解了，删除堆頂元素，然後再調整堆。
public E poll() {
if (size == )
return null;
//如果堆大小為0則傳回null
int s = --size;
modCount++;
E result = (E) queue[];
E x = (E) queue[s];
queue[s] = null;
//如果堆中隻有一個元素直接删除
if (s != )
siftDown(, x);
//否則删除元素後對堆進行調整
return result;
}
同理，siftDown()是從堆頂往下調整堆。
private void siftDownComparable(int k, E x) {
Comparable<? super E> key = (Comparable<? super E>)x;
int half = size >>> ; // loop while a non-leaf
while (k < half) {
int child = (k << ) + ; // assume left child is least
Object c = queue[child];
int right = child + ;
if (right < size &&
((Comparable<? super E>) c).compareTo((E) queue[right]) > )
c = queue[child = right];
if (key.compareTo((E) c) <= )
break;
queue[k] = c;
k = child;
}
queue[k] = key;
}
大小變換
如果想利用 priorityQueue來構造最大堆的話，自己寫一個Comparator傳入構造函數就行了，具體的構造函數，前面已經說過了啊。
public PriorityQueue(int initialCapacity,
Comparator<? super E> comparator) {
// Note: This restriction of at least one is not actually needed,
// but continues for 1.5 compatibility
if (initialCapacity < )
throw new IllegalArgumentException();
this.queue = new Object[initialCapacity];
this.comparator = comparator;
}