1 ArrayDeque簡介
通過名稱我們可以知道ArrayDeque是Java中使用數(shù)組實(shí)現(xiàn)的雙端隊(duì)列郑气。是用作隊(duì)列、雙端隊(duì)列、棧的絕佳選擇澜公。
1.1 如何理解“棧”
關(guān)于“椑撸”坟乾，一個非常貼切的例子，就是一摞疊在一起的盤子蝶防。我們平時放盤子的時候甚侣，都是從下往上一個一個放；取的時候间学，我們也是從上往下一個一個地依次取殷费，不能從中間任意抽出。后進(jìn)者先出低葫，先進(jìn)者后出宗兼，這就是典型的“棧”結(jié)構(gòu)氮采。從棧的操作特性上來看殷绍，棧是一種“操作受限”的線性表，只允許在一端插入和刪除數(shù)據(jù)鹊漠。
1.2 如何“理解隊(duì)列“
隊(duì)列這個概念非常好理解主到。你可以把它想象成排隊(duì)買票，先來的先買躯概，后來的人只能站末尾登钥，不允許插隊(duì)。先進(jìn)者先出娶靡，這就是典型的“隊(duì)列”牧牢。
相對于棧只支持兩個基本操作：入棧 push()和出棧 pop()，對于也只支持兩個操作入隊(duì) enqueue()姿锭，放一個數(shù)據(jù)到隊(duì)列尾部塔鳍；出隊(duì) dequeue()，從隊(duì)列頭部取一個元素呻此，因此隊(duì)列跟棧一樣轮纫，也是一種操作受限的線性表數(shù)據(jù)結(jié)構(gòu)
1.3 如何理解“雙端隊(duì)列”
Deque 全稱為double ended queue，即雙向隊(duì)列焚鲜，相對于隊(duì)列它提供了更強(qiáng)大的功能.它允許在隊(duì)列兩側(cè)插入或刪除元素掌唾。因此deque實(shí)現(xiàn)不僅僅能能作為隊(duì)列【先進(jìn)先出FIFO(first in first out)】使用放前，還能作為棧【后入先出LIFO(last in first out)使用】糯彬。
1.4 Java中雙端隊(duì)列“接口”
Java容器隊(duì)列(二)-Deque(雙端隊(duì)列)
2 數(shù)組實(shí)現(xiàn)隊(duì)列
隊(duì)列的數(shù)組實(shí)現(xiàn)需要兩個指針：一個是 head 指針凭语，指向隊(duì)頭；一個是 tail 指針撩扒，指向隊(duì)尾似扔。結(jié)合下面這幅圖來理解。當(dāng) a却舀、b、c锤灿、d 依次入隊(duì)之后挽拔，隊(duì)列中的 head 指針指向下標(biāo)為 0 的位置，tail 指針指向下標(biāo)為 4 的位置但校。
當(dāng)我們調(diào)用兩次出隊(duì)操作之后螃诅，隊(duì)列中 head 指針指向下標(biāo)為 2 的位置，tail 指針仍然指向下標(biāo)為 4 的位置状囱。
你肯定已經(jīng)發(fā)現(xiàn)了术裸，隨著不停地進(jìn)行入隊(duì)、出隊(duì)操作亭枷，head 和 tail 都會持續(xù)往后移動袭艺。當(dāng) tail 移動到最右邊，即使數(shù)組中還有空閑空間叨粘，
也無法繼續(xù)往隊(duì)列中添加數(shù)據(jù)了猾编。這個問題該如何解決呢？
2.1 循環(huán)隊(duì)列
循環(huán)隊(duì)列升敲，顧名思義答倡，它長得像一個環(huán)。原本數(shù)組是有頭有尾的驴党，是一條直線”衿玻現(xiàn)在我們把首尾相連，扳成了一個環(huán)港庄。
我們可以看到倔既，圖中這個隊(duì)列的大小為 8，當(dāng)前 head=4鹏氧，tail=7叉存。當(dāng)有一個新的元素 a 入隊(duì)時，我們放入下標(biāo)為 7 的位置度帮。但這個時候歼捏，我們并不把 tail 更新為 8稿存，而是將其在環(huán)中后移一位，到下標(biāo)為 0 的位置瞳秽。當(dāng)再有一個元素 b 入隊(duì)時瓣履，我們將 b 放入下標(biāo)為 0 的位置，然后 tail 加 1 更新為 1练俐。所以袖迎，在 a，b 依次入隊(duì)之后腺晾，循環(huán)隊(duì)列中的元素就變成了下面的樣子：
通過這樣的方法燕锥，我們成功避免了數(shù)據(jù)搬移操作。但是循環(huán)隊(duì)列最關(guān)鍵的是悯蝉，確定好隊(duì)空和隊(duì)滿的判定條件归形。
在用數(shù)組實(shí)現(xiàn)的非循環(huán)隊(duì)列中，隊(duì)滿的判斷條件是 tail == n鼻由，隊(duì)空的判斷條件是 head == tail暇榴。那針對循環(huán)隊(duì)列，如何判斷隊(duì)空和隊(duì)滿呢蕉世？
方式一
就像我圖中畫的隊(duì)滿的情況蔼紧，tail=3，head=4狠轻，n=8奸例，所以總結(jié)一下規(guī)律就是：(3+1)%8=4。多畫幾張隊(duì)滿的圖向楼，你就會發(fā)現(xiàn)哩至，當(dāng)隊(duì)滿時滿足以下公式 ：(tail+1)%n=head。
當(dāng)隊(duì)列滿時蜜自，圖中的 tail 指向的位置實(shí)際上是沒有存儲數(shù)據(jù)的菩貌。所以，循環(huán)隊(duì)列會浪費(fèi)一個數(shù)組的存儲空間重荠。
3 數(shù)組實(shí)現(xiàn)雙端隊(duì)列
還是循環(huán)隊(duì)列隊(duì)列為例箭阶，雙端隊(duì)列相對于普通隊(duì)列，支持頭部插入隊(duì)戈鲁，尾部出隊(duì)
3.1 入隊(duì)操作
隊(duì)首入隊(duì)
圖中這個隊(duì)列的大小為 8仇参，當(dāng)前 head=0，tail=0婆殿。將一個元素a從隊(duì)列頭部入隊(duì)诈乒，首先移動head指向下標(biāo)為7的位置，之后將a放入head新指向位置7 （先移動后賦值）
隊(duì)尾入隊(duì)
和普通隊(duì)列一樣婆芦，將元素b 隊(duì)尾入隊(duì)時,首先將b值放入tail指向的位置0怕磨，移動head指向下標(biāo)為1的位置 (先賦值后移動)
3.2 出隊(duì)操作
隊(duì)首出隊(duì)
圖中這個隊(duì)列的大小為 8喂饥，當(dāng)前 head=6，tail=2肠鲫。隊(duì)首出隊(duì)時员帮，首先將head指向的數(shù)據(jù)清空，之后移動head指向下標(biāo)為7的位置导饲。（先清理后移動）
隊(duì)尾出隊(duì)
和普通隊(duì)列一樣捞高，隊(duì)尾出隊(duì)時，移動tail指向下標(biāo)為1的位置渣锦，將tail指向的數(shù)據(jù)清空 (先賦值后移動)
3.3 擴(kuò)容
新建一個原始數(shù)組2倍大小的數(shù)組硝岗，移動head,tail指向位置0，并將原始數(shù)組中數(shù)據(jù)按順序插入新隊(duì)列尾部袋毙。
3 ArrayDeque源碼解析
3.1 內(nèi)部成員變量
//容器capacity最小值型檀，也是2的次冪（數(shù)組初始容量保證都時2的次冪，方便使用位運(yùn)算）
private static final int MIN_INITIAL_CAPACITY = 8;
//存放數(shù)據(jù)數(shù)組娄猫，長度和capacity一致贱除，并且總是2的次冪
transient Object[] elements;
//標(biāo)記隊(duì)首元素所在的位置
transient int head;
//標(biāo)記隊(duì)尾元素所在的位置
transient int tail;
3.2 構(gòu)造函數(shù)
/**
* 構(gòu)造一個初始容量為16的空隊(duì)列
*/
public ArrayDeque() {
elements = new Object[16];
}
/**
* 構(gòu)造一個能容納指定大小的空隊(duì)列
*/
public ArrayDeque(int numElements) {
allocateElements(numElements);
}
/**
* 構(gòu)造一個包含指定集合所有元素的隊(duì)列
*/
public ArrayDeque(Collection<? extends E> c) {
allocateElements(c.size());
addAll(c);
}
allocateElements方法主要用于給內(nèi)部的數(shù)組分配合適大小的空間生闲，大于等于最接近toSize的2的冪數(shù)
private void allocateElements(int numElements) {
int initialCapacity = MIN_INITIAL_CAPACITY;
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
}
elements = (E[]) new Object[initialCapacity];
}
3.3 容量設(shè)置成2^n的冪好處媳溺？
任何一個數(shù)和2^n-1做&運(yùn)算可以用在循環(huán)隊(duì)列的數(shù)組中快速指針的位置。
一個負(fù)數(shù)x和2^n-1做&運(yùn)算相當(dāng)于 2^n-1-|x|
案例
System.out.println(Integer.toBinaryString(8 - 1));
System.out.println(Integer.toBinaryString((0 - 1) & (8 - 1)));
System.out.println((0 - 1) & (8 - 1));
System.out.println(Integer.toBinaryString((0 - 2) & (8 - 1)));
System.out.println((0 - 2) & (8 - 1));
//結(jié)果
00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000111
00000000 00000000 00000000 00000110
7
6
一個正數(shù)x和2^n-1做&運(yùn)算相當(dāng)于取余碍讯。
案例
System.out.println(Integer.toBinaryString((1) & (8 - 1)));
System.out.println(Integer.toBinaryString(( 2) & (8 - 1)));
System.out.println(( 1) & (8 - 1));
System.out.println(( 2) & (8 - 1));
00000000 00000000 00000000 00000001
00000000 00000000 00000000 00000010
1
2
3.4 入隊(duì)
/** 在隊(duì)首添加元素 **/
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
/** 在隊(duì)首添加元素 **/
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
/** 在隊(duì)尾添加元素 **/
public boolean offerLast(E e) {
addLast(e);
return true;
}
/** 在隊(duì)尾添加元素 **/
public void addLast(E e) {
if (e == null)
throw new NullPointerException();
elements[tail] = e;
if ( (tail = (tail + 1) & (elements.length - 1)) == head)
doubleCapacity();
}
3.5 出隊(duì)
/** 隊(duì)首出隊(duì) **/
public E removeFirst() {
E x = pollFirst();
if (x == null)
throw new NoSuchElementException();
return x;
}
/** 隊(duì)首出隊(duì) **/
public E pollFirst() {
int h = head;
@SuppressWarnings("unchecked")
E result = (E) elements[h];
if (result == null)
return null;
elements[h] = null;
head = (h + 1) & (elements.length - 1);
return result;
}
/** 隊(duì)尾出隊(duì) **/
public E removeLast() {
E x = pollLast();
if (x == null)
throw new NoSuchElementException();
return x;
}
/** 隊(duì)尾出隊(duì) **/
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;
}
3.6 擴(kuò)容
private void doubleCapacity() {
//只有head==tail時才可以擴(kuò)容
assert head == tail;
int p = head;
int n = elements.length;
//在head之后悬蔽，還有多少元素
int r = n - p; // number of elements to the right of p
//直接翻倍，因?yàn)閏apacity初始化時就已經(jīng)是2的倍數(shù)了捉兴，這里無需再考慮
int newCapacity = n << 1;
if (newCapacity < 0)
throw new IllegalStateException("Sorry, deque too big");
Object[] a = new Object[newCapacity];
//左側(cè)數(shù)據(jù)拷貝
System.arraycopy(elements, p, a, 0, r);
//右側(cè)數(shù)據(jù)拷貝
System.arraycopy(elements, 0, a, r, p);
elements = a;
head = 0;
tail = n;
}
3.7 獲取
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)];
}
3.8 其他
removeFirstOccurrence和removeLastOccurrence分別用于找到元素在隊(duì)首或隊(duì)尾第一次出現(xiàn)的位置并刪除蝎困。其實(shí)現(xiàn)原理是一致的
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;
}
這里就是遍歷所有元素，然后通過delete方法刪除倍啥，我們看看delete實(shí)現(xiàn)：
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;
//待刪除元素前面的元素個數(shù)
final int front = (i - h) & mask;
//待刪除元素后面的元素個數(shù)
final int back = (t - i) & mask;
// Invariant: head <= i < tail mod circularity
//確認(rèn) i 在head和tail之間
if (front >= ((t - h) & mask))
throw new ConcurrentModificationException();
// Optimize for least element motion
//盡量最少操作數(shù)據(jù)
//前面數(shù)據(jù)比較少
if (front < back) {
if (h <= i) {
//這時 h 和 i 之間最近距離沒有跨過位置0
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
//這時 t 和 i 之間最近距離沒有跨過位置0
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;
}
}
