Java集合ArrayDeque類(lèi)實(shí)例分析
公司主營(yíng)業(yè)務(wù)：網(wǎng)站制作、成都網(wǎng)站設(shè)計(jì)、移動(dòng)網(wǎng)站開(kāi)發(fā)等業(yè)務(wù)。幫助企業(yè)客戶真正實(shí)現(xiàn)互聯(lián)網(wǎng)宣傳，提高企業(yè)的競(jìng)爭(zhēng)能力。成都創(chuàng)新互聯(lián)是一支青春激揚(yáng)、勤奮敬業(yè)、活力青春激揚(yáng)、勤奮敬業(yè)、活力澎湃、和諧高效的團(tuán)隊(duì)。公司秉承以“開(kāi)放、自由、嚴(yán)謹(jǐn)、自律”為核心的企業(yè)文化，感謝他們對(duì)我們的高要求，感謝他們從不同領(lǐng)域給我們帶來(lái)的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會(huì)用頭腦與智慧不斷的給客戶帶來(lái)驚喜。成都創(chuàng)新互聯(lián)推出萊山免費(fèi)做網(wǎng)站回饋大家。
前言
ArrayDeque類(lèi)是雙端隊(duì)列的實(shí)現(xiàn)類(lèi)，類(lèi)的繼承結(jié)構(gòu)如下面，繼承自AbastractCollection（該類(lèi)實(shí)習(xí)了部分集合通用的方法，其實(shí)現(xiàn)了Collection接口），其實(shí)現(xiàn)的接口Deque接口中定義了雙端隊(duì)列的主要的方法，比如從頭刪除，從尾部刪除，獲取頭數(shù)據(jù)，獲取尾部數(shù)據(jù)等等。
public class ArrayDequeextends AbstractCollection implements Deque , Cloneable, Serializable
ArrayDeque基本特征
就其實(shí)現(xiàn)而言，ArrayDeque采用了循環(huán)數(shù)組的方式來(lái)完成雙端隊(duì)列的功能。
1. 無(wú)限的擴(kuò)展，自動(dòng)擴(kuò)展隊(duì)列大小的。（當(dāng)然在不會(huì)內(nèi)存溢出的情況下。）
2. 非線程安全的，不支持并發(fā)訪問(wèn)和修改。
3. 支持fast-fail.
4. 作為棧使用的話比比棧要快.
5. 當(dāng)隊(duì)列使用比linklist要快。
6. null元素被禁止使用。
ArrayDeque實(shí)現(xiàn)方法解讀
最小初始化容量限制
/** * The minimum capacity that we'll use for a newly created deque. * Must be a power of 2. */ private static final int MIN_INITIAL_CAPACITY = 8;
這里根據(jù)注釋中提及，必須是2的冪次。僅僅通過(guò)這里是不會(huì)知道為何要這樣設(shè)定的。
重慶分公司
重慶分公司
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
addFirst方法中使用了head-1和length-1相與的形式來(lái)計(jì)算，那么，length-1這里是多少，因?yàn)橐?guī)定了length必須是2的冪次，所以length-1后二進(jìn)制低位將全部為1，然后與head-1相與相當(dāng)于對(duì)其進(jìn)行取模。
擴(kuò)容
之所以說(shuō)該ArrayDeque容量無(wú)限制，是因?yàn)橹灰獧z測(cè)到head==tail的時(shí)候，就直接調(diào)用doubleCapacity方法進(jìn)行擴(kuò)容。
這個(gè)時(shí)候?qū)?shù)組展開(kāi)，head和tail指向的是同一個(gè)位置，那么，因?yàn)槭茄h(huán)數(shù)組，所以head左邊可能存在一部分元素為p個(gè)，右邊也可能存在一部分?jǐn)?shù)據(jù)r=n-p個(gè)，右邊的部分復(fù)制到從0到r,左邊的部分復(fù)制到從r到結(jié)束。這樣原來(lái)的數(shù)據(jù)從0開(kāi)始往下排列。
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 = (E[])a;
head = 0;
tail = n;
}
刪除元素
刪除元素的基本思路為確定那一側(cè)的數(shù)據(jù)少，少的一側(cè)移動(dòng)元素位置，這樣效率相對(duì)于不比較更高些，然后，判斷head是跨越最大值還是為跨越最大值，繼而可以分兩種不同的情況進(jìn)行拷貝。但是該方法比較慢，因?yàn)榇嬖跀?shù)組的拷貝。
private boolean delete(int i) {
checkInvariants();
final E[] 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
// 為了最小的拷貝數(shù)據(jù)
if (front < back) {
// 遞增的順序時(shí)
if (h <= i) {
// 刪除部分前面的向后移動(dòng)
System.arraycopy(elements, h, elements, h + 1, front);
} else { // Wrap around
// 跨越最小與最大值
// 分兩次拷貝
System.arraycopy(elements, 0, elements, 1, i);
// 最大的地方單獨(dú)處理
elements[0] = elements[mask];
// 前面的部分向后移動(dòng)一位
System.arraycopy(elements, h, elements, h + 1, mask - h);
}
elements[h] = null;
head = (h + 1) & mask;
return false;
} else {
// 遞增的順序時(shí)
if (i < t) { // Copy the null tail as well
// 拷貝i后面的部分?jǐn)?shù)據(jù)前置
System.arraycopy(elements, i + 1, elements, i, back);
tail = t - 1;
} else { // Wrap around
// 跨越中間最大值的時(shí)候
// 后面向前拷貝
// 0處的值單獨(dú)處置放在最大的下標(biāo)處
// 后面的部分從1開(kāi)始向前移動(dòng)一個(gè)，原來(lái)的1在0處
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;
}
}
獲取并刪除元素
這里在舉個(gè)簡(jiǎn)單點(diǎn)的例子，中間判斷是不是null，可以看出該隊(duì)列不支持null,通過(guò)把其值設(shè)為null就算是將其刪除了。然后head向遞增的方向退一位即可。
public E pollFirst() {
int h = head;
E result = 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;
}
感謝閱讀，希望能幫助大家，謝謝大家對(duì)本站的支持！
