系列文章目錄
1、ArrayList - ArrayList函數及相關解釋(一)
2、ArrayList - ArrayList函數及相關解釋(二)
文章目錄
- 系列文章目錄
- ArrayDeque介紹
-
- 1、calculateSize
- 2、allocateElements
- 3、doubleCapacity
- 4、copyElements
- 5、構造方法
- 6、add方法
- 7、addLast方法
- 8、offerFirst方法
- 9、addFirst方法
- 10、offerLast方法
- 11、removeFirst方法
- 12、pollFirst方法
- 13、removeLast方法
- 14、pollLast方法
- 15、元素的擷取方法
- 16、removeFirstOccurrence方法
- 17、delete方法
- 18、removeLastOccurrence方法
- 19、add方法
- 20、offer方法
- 21、remove方法
- 22、poll方法
- 23、element方法
- 24、peek方法
- 25、push操作
- 26、pop方法
ArrayDeque介紹
Deque接口的可調整大小的數組實作。數組雙端隊列沒有容量限制；它随着支援使用的必要性來擴充容量。他們不是線程安全的；在沒有外部同步的情況下，它不支援被多個線程同時通路。Null元素是被禁止的。這個類當被用作棧的時候，可能會被Stack類快；并且當被用作隊列的時候，要比LinkedList類要快。
大多數的ArrayDeque操作都是以固定時間内運作的。異常包含remove(Object), removeFirstOccurrence, removeLastOccurrence, contains, iterator.remove()和批量操作，所有的這些操作在運作線上性時間内。
這個類的iterator方法傳回的疊代器是快速失敗的：如果deque在疊代器被建立之後，在任何時候被修改，除了通過疊代器自己的remove方法之後，該疊代器通常會扔出一個ConcurrentModificationException。是以，在面對同時修改的時候，疊代器會快速而幹淨的失敗，而不是在未來不确定的時間不确定行為冒險嘗試。
注意，不能保證疊代器的快速故障行為，因為一般來說，在存在非同步并發修改的情況下，不可能做出任何硬保證。失敗的快速疊代器會盡最大努力抛出{@code ConcurrentModificationException}。是以，為了它的正确性編寫一個依賴于這個異常的程式将會是錯誤的：疊代器的快速失敗行為應該僅僅被用于檢測bug。
我們先看一下該類中的一些屬性：
transient Object[] elements; // 非私有以簡化嵌套類通路
從這裡可以看出，該屬性是使用transient修飾的，這說明在該類進行序列化的時候，該屬性是不被序列化的。雙端隊列中的元素被儲存到這個數組中。雙端隊列的容量便是這個數組的長度，該長度一直是2的幂。這個數組是不被允許存滿的，除了在addX方法中，一旦被存儲滿則會立即被重新調整大小，是以這樣就避免了頭部和尾部互相纏繞。我們也能保證不包含雙端隊列元素的數組單元總是空的。
因為這裡是雙端隊列，是以在雙端隊列的實作過程中包含了兩個節點，一個頭節點head和一個尾部節點tail，這兩個節點都是數組的下标索引。
private static final int MIN_INITIAL_CAPACITY = 8;
這裡設定的是新建立的雙端隊列的最小容量，這個值必須是2的幂次方。
1、calculateSize
下面我們看一下雙端隊列中數組的配置設定和重新配置設定大小的工具：
private static int calculateSize(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
// Find the best power of two to hold elements.
// Tests "<=" because arrays aren't kept full.
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
}
return initialCapacity;
}
這裡的處理很巧妙，該方法用于計算數組需要的容量的大小，對于給定的參數numElements，如果為12，則因為這裡要求的數組長度為2的幂次方，是以numElements期望的值為16。該方法就是為了計算該值。
傳入的參數值numElements如果小于初始化最小容量，則不需要做處理。如果超過最小容量，則對該值進行處理，對值做32次無符号右移（這裡無符号右移，即如果值為正數，則右移的時候，高位補0；如果為負數，高位也補0）并對原值做或操作。做32次的原因是因為在Java中int類型的值大小為32位，是以操作32次之後，該值12原值對于的2進制為1100，操作完成之後，則值變成了1111，即15；是以對其進行加1操作便完成了期望值的計算。
2、allocateElements
該方法用于配置設定空的給定數量大小的數組。
private void allocateElements(int numElements) {
elements = new Object[calculateSize(numElements)];
}
這裡用到了基礎的期望值計算的方法。
3、doubleCapacity
該方法用于擴充數組的容量變為兩倍。該方法僅僅是在數組滿了之後，即當頭節點和尾節點首位連接配接為相等的時候進行調用。
private void doubleCapacity() {
assert head == tail;
int p = head;
int n = elements.length;
int r = n - p; // number of elements to the right of p
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
System.arraycopy(elements, p, a, 0, r);
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
該方法的程式比較簡單，首先聲明一個兩倍長度的數組，然後将原數組的資料複制到新的數組中。
4、copyElements
将程式中的數組資料按照順序（從雙端隊列中的第一個到最後一個元素）複制到指定的數組中。這裡假設數組是足夠大的，能夠儲存雙端隊列中的所有的元素。
private <T> T[] copyElements(T[] a) {
if (head < tail) {
System.arraycopy(elements, head, a, 0, size());
} else if (head > tail) {
int headPortionLen = elements.length - head;
System.arraycopy(elements, head, a, 0, headPortionLen);
System.arraycopy(elements, 0, a, headPortionLen, tail);
}
return a;
}
該方法主要關注的地友善是當head大于tail的時候，需要分兩段進行數組的複制。
5、構造方法
該雙端隊列一共有三個構造方法，如下所示：
public ArrayDeque() {
elements = new Object[16];
}
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
對于無參構造器來說，該雙端隊列的預設長度為16。當使用給定初始長度的雙端隊列構造器的時候，則需要使用配置設定長度方法，将該長度換算成2的幂次方的長度。第三個構造器為給定一個容器作為參數，通過代碼可以看出，該構造器内部會先配置設定數組長度，然後再調用addAll()方法将資料配置設定給數組。addAll()方法則是AbstractCollection類中封裝的方法，其内部調用add方法。
6、add方法
該方法用于插入指定元素到該雙端隊列的尾部。該方法與addLast方法在功能上是相同的。
public boolean add(E e) {
addLast(e);
return true;
}
7、addLast方法
該方法用于插入指定元素到該雙端隊列的尾部。該方法會抛出空指針異常，當被插入的元素為空的時候，則會抛出空指針異常。
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
在該雙端隊列的實作内部，有兩個指針head和tail，head指針指向數組中的第一個元素，tail指針指向數組中最後一個元素的下一個位置。是以當插入元素的時候，隻需要将tail位置的元素設定為指定元素即可。比較有趣的是後續的操作，即當tail指針轉到下一個位置的時候，有可能會超出數組的長度，舉個例子：
當剛剛插入元素8的時候，tail将要指向下一個元素，下面我們運作後面代碼部分：
tail + 1 = 8; 其對應二進制為：1000
elements.length - 1 = 7，該值對應的二進制為：0111
則對其取與操作後，對應的tail = 0；是以由此可以判斷需要擴充數組的長度了，則調用doubleCapacity方法擴充數組的長度。
8、offerFirst方法
該方法用于在雙端隊列前面插入一個指定元素。
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
該方法與方法addFirst的功能是相同的，是以該方法内部調用addFirst方法。
9、addFirst方法
該雙端隊列中主要的插入和提取方法是addFirst, addLast, pollFirst, pollLast。其他方法都是用這些方法實作的。
該方法是在該雙端隊列的前端插入一個指定元素。當被插入的元素為空的時候，該方法會抛出空指針異常。
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
該方法比較有意思，當我們建立完成新的雙端隊列的時候，預設的值為：
head = 0;
elements.length = 16;
是以，運作下述邏輯：
head = (head - 1) & (elements.length - 1)
head = (-1 & 15)
head = 15
是以初始添加資料的時候，資料被插入到數組的最後一個位置15，舉個例子，我們首次調用addFirst插入元素1。
如圖所示：
接着，我們繼續調用addFirst方法，插入元素2。
head = 15
head = (head - 1) & (elements.length - 1)
head = (15 - 1) & (16 - 1)
head = 14 & 15
head = 14
是以元素2就被插入到14的位置處。
10、offerLast方法
該方法用于在雙端隊列尾部插入一個指定元素。
public boolean offerLast(E e) {
addLast(e);
return true;
}
同樣，該方法的功能與addLast方法是相同的。
11、removeFirst方法
顧名思義，該方法用于移除雙端隊列中的第一個元素。
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
該方法通過調用pollFirst方法彈出第一個元素，同時，如果元素不存在，則抛出元素不存在的異常。
12、pollFirst方法
該方法用于彈出head指針指向的元素。
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
head = (h + 1) & (elements.length - 1);
return result;
}
這裡取值的代碼部分很簡單，直接擷取head指針位置的元素，如果元素為空，則傳回空。如果元素不為空，則傳回該元素，并将數組中head位置的元素置為空，同時運作與addFirst方法相反的方式重新計算head的大小。
最後，傳回該元素。
13、removeLast方法
該方法用于移除最後一個元素。
public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
}
該方法調用pollLast方法彈出最後一個元素。如果該元素不存在的時候，該方法會抛出元素不存在的異常。
14、pollLast方法
該方法用于彈出該雙端隊列中的最後一個元素。
public E pollLast() {
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;
}
由于在該雙端隊列中，head指針指向的是雙端隊列中的第一個元素的位置；tail指針指向的是雙端隊列中的最後一個元素的下一個位置。
是以如果想要擷取最後一個元素的位置，則需要擷取他的上一個位置，同樣調用與addLast方法相反的方式擷取最後一個元素的位置。
後續的操作便比較容易了解了。
15、元素的擷取方法
擷取第一個元素，擷取最後一個元素等方法，在邏輯上也是比較好了解的。
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getFirst() {
@SuppressWarnings("unchecked")
E result = (E) elements[head];
if (result == null)
throw new NoSuchElementException();
return result;
}
/**
* @throws NoSuchElementException {@inheritDoc}
*/
public E getLast() {
@SuppressWarnings("unchecked")
E result = (E) elements[(tail - 1) & (elements.length - 1)];
if (result == null)
throw new NoSuchElementException();
return result;
}
@SuppressWarnings("unchecked")
public E peekFirst() {
// elements[head] is null if deque empty
return (E) elements[head];
}
@SuppressWarnings("unchecked")
public E peekLast() {
return (E) elements[(tail - 1) & (elements.length - 1)];
}
這裡的getFirst和peekFirst，getLast和peekLast方法唯一的不同，便是對null元素的校驗。其中get相關的擷取元素的方法是對null元素進行校驗的，如果元素為空，則抛出元素不存在的異常；而peek相關的擷取元素的方法，則不對元素的null值進行校驗，如果元素為空，則直接傳回null值。
16、removeFirstOccurrence方法
該方法會删除這個雙端隊列中的指定元素的第一個比對項（當從頭到尾周遊數組的時候）。如果該雙端隊列不包含該元素，該雙端隊列不會改變。
更加正式的說法是，如果元素o.equals(e)，并且元素存在的元素，則移除第一個元素。如果這個元素包含指定元素，則傳回true。
（或者是等價的，如果這個雙端隊列因為函數被調用而改變的話）。
public boolean removeFirstOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = head;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i + 1) & mask;
}
return false;
}
該方法從head開始向tail進行周遊，當遇到第一個不為null并且雙端隊列中的元素與指定元素相同的時候，則删除該元素。該方法調用delete方法對該元素進行删除。
17、delete方法
該方法用于移除元素數組中指定位置的元素，并根據需要調整頭部和尾部。這可能會導緻數組中的元素向前或向後移動。
此方法稱為delete而不是remove，以強調其語義不同于List裡面的remove方法。
private boolean delete(int i) {
checkInvariants();
final Object[] elements = this.elements;
final int mask = elements.length - 1;
final int h = head;
final int t = tail;
final int front = (i - h) & mask;
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
if (front < back) {
if (h <= i) {
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
System.arraycopy(elements, 0, elements, 1, i);
elements[0] = elements[mask];
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
elements[h] = null;
head = (h + 1) & mask;
return false;
} else {
if (i < t) { // Copy the null tail as well
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
System.arraycopy(elements, i + 1, elements, i, mask - i);
elements[mask] = elements[0];
System.arraycopy(elements, 1, elements, 0, t);
tail = (t - 1) & mask;
}
return true;
}
}
我們舉個例子來驗證一下該程式的算法實作：
ArrayDeque<Integer> queue = new ArrayDeque<>();
for(int i = 1;i <= 17;i++){
queue.addFirst(i);
}
由上述代碼得到的雙端隊列内部的數組形式如下：
從圖中可以看出：
tail = 16
head = 31
i = 5 // 要被删除的元素的位置
我們來運作delete程式來看一下該方法的執行過程：
i = 5;
elements = {16,15,14,13,12,11,10,9,8,7,6,5,4,3,2,1,
null,null,null,null,null,null,null,null,null,null,null,null,null,
null,null,17};
mask = elements.length - 1 = 31;
h = head = 31;
t = tail = 16;
front = (i - h) & mask = (-26) & 31 = 6
back = (t - i) & mask = (16 - 5) & 31 = 11 & 31 = 11
(t - h) & mask = (-15) & 31 = 17
執行完成後，數組的資料結構變為如圖所示：
18、removeLastOccurrence方法
移除該雙端隊列中最後一個比對指定元素的元素（這裡最後一個比對元素指的是從頭部向尾部周遊的時候，最後一個比對的元素）。
該方法與上述方法的處理過程基本上是一樣的，不過該雙端隊列的周遊是從尾部開始，這樣第一個比對的元素即為邏輯上最後一個比對的元素。
public boolean removeLastOccurrence(Object o) {
if (o == null)
return false;
int mask = elements.length - 1;
int i = (tail - 1) & mask;
Object x;
while ( (x = elements[i]) != null) {
if (o.equals(x)) {
delete(i);
return true;
}
i = (i - 1) & mask;
}
return false;
}
從此開始，後續的方法便是隊列的相關操作方法。我們一起來學習一下。
19、add方法
該方法調用addLast方法，用于在該雙端隊列的尾端插入一個元素，并傳回true。當該方法中被插入的元素為空的時候，将會抛出空指針異常。
public boolean add(E e) {
addLast(e);
return true;
}
20、offer方法
該方法是調用上述的offerLast方法，功能與add方法一緻，同樣也是用于将元素插入該雙端隊列的尾部。當被插入的元素為空的時候，該方法也會抛出空指針異常。
public boolean offer(E e) {
return offerLast(e);
}
21、remove方法
該方法調用上述的removeFirst方法，用于移除該雙端隊列中的頭部的第一個元素。
public E remove() {
return removeFirst();
}
22、poll方法
該方法調用pollFirst方法用于擷取并移除該雙端隊列中的頭部元素。
public E poll() {
return pollFirst();
}
23、element方法
該方法用于擷取該雙端隊列中的頭部元素，但是并不移除該元素，但是當被擷取的元素不存在的話，則抛出元素不存在的異常。
public E element() {
return getFirst();
}
24、peek方法
該方法用于擷取該雙端隊列中的頭部元素，但并不是移除；同時如果元素不存在，則傳回空元素。
public E peek() {
return peekFirst();
}
至此，相關隊列queue的操作方法基本上完成了。從此之後的後續操作，是相關于棧(Stack)的操作。
25、push操作
該方法用于向棧中壓入一個元素，相對于在該雙端隊列中來說，相當于向該雙端隊列中的首部插入一個元素。
public void push(E e) {
addFirst(e);
}
26、pop方法
該方法是棧操作中彈出頭部元素，相當于在雙端隊列中移除頭部元素。
public E pop() {
return removeFirst();
}
這樣，棧的元素的壓入操作和彈出操作就完成了。接着我們學習一個集合相關的操作方法。
後續的擷取雙端隊列的長度，移除元素等方法都比較簡單了。後面有一個比較有意思的便是其内部類實作了Spliterator接口，該接口是java 8中新增的用于并行計算的接口，後續我們将專門對該接口進行學習。