主要學(xué)習(xí)雙端隊(duì)列 ArrayDeque ，通過(guò)對(duì)其棧功能的使用，掌握循環(huán)數(shù)組底層原理

覺(jué)得文章枯燥的可以結(jié)合ArrayDeque 底層原理可視化視頻：https://www.bilibili.com/video/BV1zChGz8EVL/

有環(huán)形的數(shù)組？同時(shí)具備棧功能和隊(duì)列功能？

1. Java 中的棧實(shí)現(xiàn)

在Java中，棧類你可以直接找到的是Stack類。Stack類實(shí)在JDK 1.0 的時(shí)候就有了，但你會(huì)發(fā)現(xiàn)在Stack類頭注釋寫著：建議優(yōu)先使用Deque接口及其實(shí)現(xiàn)類，例如：ArrayDeque。

1.1. Stack

Stack 繼承自 Vector<E>，線程安全，但因每次操作都要加鎖，性能較差。Vector 集合基本也不會(huì)用到的。

示例：

Stack<Integer> stack = new Stack<>();
stack.push(1);
int top = stack.peek();
int popped = stack.pop();

1.2. LinkedList

LinkedList實(shí)現(xiàn)了Deque雙端隊(duì)列接口，具備了隊(duì)列功能和棧功能，也就是說(shuō)LinkedList 可以當(dāng)做普通List集合來(lái)用，同時(shí)還可以當(dāng)做棧或隊(duì)列來(lái)使用。

以下是通過(guò)LinkedList 來(lái)實(shí)現(xiàn)入棧、出棧操作：

LinkedList<String> linkedList = new LinkedList<>();
// 入棧
linkedList.push("淵");
linkedList.push("渟");
linkedList.push("岳");
linkedList.push("Why?");
System.out.println(linkedList); // [Why?, 岳, 渟, 淵]
// 獲取棧頂元素
String peek = linkedList.peek();//不會(huì)出棧
System.out.println(peek); // Why?
// 出棧
String pop = linkedList.pop();//出棧一個(gè)
System.out.println(pop);// Why?
linkedList.pop();   //再出棧一個(gè),不獲取結(jié)果
System.out.println(linkedList);// 剩下的元素：[渟, 淵]

使用雙端隊(duì)列功能時(shí)，如果你想將引用改為接口名，
?這樣寫是錯(cuò)的：List<String> linkedList = new LinkedList<>();
?得這樣寫才行：Deque<String> linkedList = new LinkedList<>();

1.3. ArrayDeque

Deque接口為雙端隊(duì)列接口，ArrayDeque實(shí)現(xiàn)了該接口。

ArrayDeque 看命名就知道是雙端隊(duì)列，并且底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組。ArrayDeque除了具有隊(duì)列（FIFO）功能，同時(shí)它還具備棧（LIFO）功能，所以它可以當(dāng)做棧來(lái)使用。

棧功能示例：

Deque<Integer> deque = new ArrayDeque<>();
deque.push(1);
deque.push(2);
deque.push(3);
System.out.println(deque); // [3, 2, 1]
int top = deque.peek();
System.out.println(top); // 3
int popped = deque.pop();
System.out.println(popped); // 3
System.out.println(deque); // [2, 1]

LinkedList在集合學(xué)習(xí)時(shí)已經(jīng)學(xué)過(guò)了，它的雙端隊(duì)列功能并不會(huì)影響底層數(shù)據(jù)結(jié)構(gòu)，僅僅是操作邏輯不同而已。

在雙端隊(duì)列功能上，LinkedList沒(méi)有ArrayDeque性能高，通常使用ArrayDeque更多，所以我們?cè)敿?xì)來(lái)學(xué)學(xué)ArrayDeque有什么獨(dú)特之處？

2. ArrayDeque底層原理

在Java中，可以通過(guò)雙端隊(duì)列Deque的實(shí)現(xiàn)類來(lái)實(shí)現(xiàn)棧功能，常用的有兩個(gè)：ArrayDeque 和 LinkedList。

兩個(gè)類繼承與實(shí)現(xiàn)：

// ArrayDeque
public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable
// LinkedList
public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable

LinkedList 實(shí)現(xiàn)類既是List集合、同時(shí)又是Deque雙端隊(duì)列，也就是說(shuō)，這個(gè)類具備多種功能：鏈?zhǔn)郊稀㈡準(zhǔn)疥?duì)列和鏈?zhǔn)綏ＨN功能。

ArrayDeque 實(shí)現(xiàn)類具備兩種功能：隊(duì)列和棧。

上一篇棧的文章也講述過(guò)使用單鏈表實(shí)現(xiàn)自定義棧，并使用自定義棧完成了有效括號(hào)匹配實(shí)戰(zhàn)，在此，主要完成ArrayDeque棧功能的學(xué)習(xí)。

2.1. ArrayDeque的數(shù)據(jù)結(jié)構(gòu)

看命名就知道是雙端隊(duì)列，并且底層數(shù)據(jù)結(jié)構(gòu)為數(shù)組。ArrayDeque類主要字段如下：

public class ArrayDeque<E> extends AbstractCollection<E>
                           implements Deque<E>, Cloneable, Serializable{
    // 數(shù)據(jù)就保存在這個(gè)數(shù)組，大小總是2的冪
    transient Object[] elements;
	// 頭索引
    transient int head;
	// 尾索引
    transient int tail;
    // 允許最小容量
    private static final int MIN_INITIAL_CAPACITY = 8;

	...
}

特別說(shuō)明下MIN_INITIAL_CAPACITY=8，這個(gè)最小容量是在你指定ArrayDeque大小時(shí)才會(huì)用到。比如你指定大小為7，那它創(chuàng)建出來(lái)的大小為8，它的計(jì)算邏輯和HashMap的一模一樣。ArrayDeque的默認(rèn)大小為16。相關(guān)代碼如下：

// 默認(rèn)構(gòu)造方法
public ArrayDeque() {
	elements = new Object[16];
}

// 指定大小構(gòu)造方法
public ArrayDeque(int numElements) {
	allocateElements(numElements);
}

private void allocateElements(int numElements) {
	elements = new Object[calculateSize(numElements)];
}

// 計(jì)算結(jié)果為2的冪次方，跟HashMap的計(jì)算邏輯一樣
private static int calculateSize(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)
			initialCapacity >>>= 1;
	}
	return initialCapacity;
}

2.2. 為什么大小設(shè)置為2的冪次方？

如果學(xué)過(guò)HashMap底層實(shí)現(xiàn)邏輯，那就非常容易理解，之前的HashMap文章還專門講了這個(gè)。

它是HashMap的哈希值映射數(shù)組下標(biāo)和ArrayDeque循環(huán)數(shù)組得以實(shí)現(xiàn)的基石。

使得通過(guò)與(&)運(yùn)算高效完成數(shù)組下標(biāo)映射，非常方便哈希值映射計(jì)算和循環(huán)索引計(jì)算。為得就是方便計(jì)算元素索引位置、提高計(jì)算效率，特別是擴(kuò)容后需要做的調(diào)整，也變得簡(jiǎn)單高效。

通過(guò)添加元素（入棧）、動(dòng)態(tài)擴(kuò)容和移除元素（出棧）這些操作感受與（&）運(yùn)算的巧妙之處。

2.3. 添加元素--入棧

從添加元素開(kāi)始，直到元素達(dá)到閾值后觸發(fā)動(dòng)態(tài)擴(kuò)容，再接著學(xué)習(xí)動(dòng)態(tài)擴(kuò)容。

元素入棧操作：

Deque<Integer> stack = new ArrayDeque<>();
stack.push(1);  // 相當(dāng)于 addFirst
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
stack.push(6);
stack.push(7);
stack.push(8);
System.out.println(stack);

執(zhí)行結(jié)果：

[8, 7, 6, 5, 4, 3, 2, 1]

結(jié)果怎么反過(guò)來(lái)的？？

我們看看源碼怎么寫的

public void push(E e) {
	addFirst(e);
}

public void addFirst(E e) {
	// 不允許存放 null 元素
	if (e == null)
		throw new NullPointerException();
	// 入棧元素位置計(jì)算
	elements[head = (head - 1) & (elements.length - 1)] = e;
	if (head == tail)
		doubleCapacity();
}

計(jì)算新的 head 索引并插入元素

elements[ head = (head - 1) & (elements.length - 1) ] = e;

head為int數(shù)據(jù)類型，成員變量默認(rèn)為：0；

head - 1：在當(dāng)前 head 之前的那個(gè)槽位，也就是“往左移一格”，第一次插入時(shí)為：-1；

& (elements.length - 1)：取模運(yùn)算，但因?yàn)?elements.length 總是 2 的冪，這里用位運(yùn)算更高效；

head = …：先更新 head 成新位置，再把 e 存入 elements[head];

這樣無(wú)論 head 從 0 跑到 -1，按位與都會(huì)自動(dòng)“回繞”到數(shù)組末尾，實(shí)現(xiàn)循環(huán)緩沖。

說(shuō)那么多也沒(méi)啥印象，來(lái)個(gè)計(jì)算過(guò)程圖示：

所以，push入棧是從數(shù)組的末端開(kāi)始，往回入棧的，ArrayDeque的數(shù)據(jù)結(jié)構(gòu)為循環(huán)數(shù)組。

循環(huán)數(shù)組數(shù)據(jù)結(jié)構(gòu)如圖：

2.4. 動(dòng)態(tài)擴(kuò)容

棧和隊(duì)列就像List集合那樣，使用時(shí)可能并不會(huì)知道集合大小為多少，所以ArrayDeque需要像ArrayList一樣需要?jiǎng)討B(tài)擴(kuò)容。

ArrayDeque的動(dòng)態(tài)擴(kuò)容像HashMap一樣，擴(kuò)容時(shí)候?yàn)?的倍數(shù)，確保大小一直為2的冪次方。

動(dòng)態(tài)擴(kuò)容只會(huì)在元素入棧的時(shí)候才會(huì)觸發(fā)，addFirst觸發(fā)擴(kuò)容條件的源碼

if (head == tail)
	doubleCapacity();

動(dòng)態(tài)擴(kuò)容關(guān)鍵源碼為

private void doubleCapacity() {
	assert head == tail;
	int p = head;
	// 數(shù)組大小
	int n = elements.length;
	// p右邊元素的個(gè)數(shù)
	int r = n - p;
	// 容量翻倍
	int newCapacity = n << 1;
	if (newCapacity < 0)
		throw new IllegalStateException("Sorry, deque too big");
	// 創(chuàng)建新數(shù)組
	Object[] a = new Object[newCapacity];
	// 元素第一次拷貝
	System.arraycopy(elements, p, a, 0, r);
	// 元素第二次拷貝
	System.arraycopy(elements, 0, a, r, p);
	// 更新數(shù)組為新對(duì)象
	elements = a;
	// 重置頭尾索引下標(biāo)
	head = 0;
	tail = n;
}

重點(diǎn)在于，為什么需要拷貝兩次？

/*
 * src     源數(shù)組
 * srcPos  源數(shù)組的起始位置
 * dest    目標(biāo)數(shù)組
 * destPos 目標(biāo)數(shù)據(jù)的起始位置
 * length  需要復(fù)制數(shù)組的長(zhǎng)度
 */
// 元素第一次拷貝
System.arraycopy(elements, p, a, 0, r);
// 元素第二次拷貝
System.arraycopy(elements, 0, a, r, p);

ArrayDeque使用的是雙端隊(duì)列，是一種循環(huán)數(shù)組，頭尾看做是相連的，做兩次拷貝的目的是：確保新數(shù)組中的元素保持原來(lái)入棧的順序。具體怎么個(gè)情況，繼續(xù)往下看，可視化一步步的講個(gè)明白。

2.5. 徹底搞懂循環(huán)數(shù)組

舉個(gè)例子：指定ArrayDeque的大小為8。先入棧1、2、3、4、5、6、7、8元素；再入棧A、B、C、D、E、F、G、H 元素。

源碼如下：

public class ArrayDequeStudy {
    public static void main(String[] args) {
        Deque<String> stack = new ArrayDeque<>(6);// 不能等于8，等于8初始大小會(huì)變?yōu)?6
        stack.push("1");
        stack.push("2");
        stack.push("3");
        stack.push("4");
        stack.push("5");
        stack.push("6");
        stack.push("7");
        stack.push("8");
        stack.push("A");
        stack.push("B");
        stack.push("C");
        stack.push("D");
        stack.push("E");
        stack.push("F");
        stack.push("G");
        stack.push("H");
        System.out.println(stack); // [H, G, F, E, D, C, B, A, 8, 7, 6, 5, 4, 3, 2, 1]
        String top = stack.peek();
        System.out.println(top);   // H
        String pop = stack.pop();
        System.out.println(pop);   // H
        System.out.println(stack.pop());// G
    }
}

通過(guò)圖形顯示處理過(guò)程就很好理解了。

1. 第一次擴(kuò)容的可視化

第一次擴(kuò)容很好理解，只需執(zhí)行一次元素拷貝，第二次的拷貝是空拷貝System.arraycopy(elements, 0, a, 8, 0)

2. 擴(kuò)容完成后，繼續(xù)插入元素（重點(diǎn)）：

在這里開(kāi)始會(huì)出現(xiàn)環(huán)繞的插入，就是數(shù)組中的元素拆分成了兩段。

也許這樣更好理解點(diǎn)，在邏輯處理上ArrayDeque的數(shù)據(jù)結(jié)構(gòu)是長(zhǎng)這樣的↓。

push 一個(gè)元素head逆時(shí)針走動(dòng)一格，寫入元素即可。

3. 第二次擴(kuò)容的可視化

出現(xiàn)兩端環(huán)繞的情況時(shí)，兩次拷貝是必不可少的，第一次拷貝的是head索引位置的后半段，第二次拷貝的是0至head的前半段，也就是剩下的那部分。不管是ArrayDeque的棧功能操作，還是雙端隊(duì)列操作，它們都會(huì)形成環(huán)繞形態(tài)的數(shù)組，需要進(jìn)行兩次拷貝，才能確保棧LIFO和隊(duì)列FIFO元素的順序正確。

2.6. 移除元素--出棧

出棧操作pop就是將head索引下的元素取出，將head右移一位。

主要源碼如下：

public E pollFirst() {
	int h = head;
	// 取出頭元素
	E result = (E) elements[h];
	if (result == null)
		return null;
	// 清空對(duì)應(yīng)數(shù)組
	elements[h] = null;
	// 將head右移一位
	head = (h + 1) & (elements.length - 1);
	return result;
}

整個(gè)操作過(guò)程非常高效，關(guān)鍵源碼還是head 右移一位。

比如：出棧元素D的過(guò)程

ArrayDeque是循環(huán)數(shù)組，在常規(guī)橫向的數(shù)組結(jié)構(gòu)上面展示并不直觀。

在首尾相連的圓形數(shù)組上，右移一位就像是在圓形的數(shù)組上順時(shí)針走動(dòng)一格，沒(méi)有首尾隔斷的感覺(jué)。

這樣看起來(lái)可能更符合循環(huán)數(shù)組的處理邏輯，出棧操作：

3. 總結(jié)

ArrayDeque 是基于循環(huán)數(shù)組的雙端隊(duì)列實(shí)現(xiàn)，既可用作隊(duì)列（FIFO）也可用作棧（LIFO）。通過(guò)兩個(gè)索引 head／tail 和位運(yùn)算自動(dòng)在固定大小（2 的冪）的底層數(shù)組中“回繞”操作，當(dāng)空間用盡時(shí)再將數(shù)組容量翻倍并平鋪原有元素，所有入、刪、取操作均為攤銷 O(1)，不支持存放 null 且非線程安全，但因無(wú)額外節(jié)點(diǎn)指針、緩存友好，通常比鏈表結(jié)構(gòu)性能更優(yōu)。

通過(guò)這篇文章，從棧功能使用到底層原理基本掌握，對(duì)ArrayDeque隊(duì)列操作功能感興趣的可以自行學(xué)習(xí)，底層和棧功能是共用的，相信你很快便可掌握雙端隊(duì)列。

文章配套的視頻也同步更新：https://www.bilibili.com/video/BV1zChGz8EVL/

想要可視化對(duì)比ArrayDeque的棧功能和隊(duì)列功能，可到視頻最后部分查看。

往期推薦

分類	往期文章
Java集合底層原理可視化	“子彈彈夾”裝彈和出彈的抽象原理實(shí)戰(zhàn)：掌握棧的原理與實(shí)戰(zhàn) TreeMap集合--底層原理、源碼閱讀及它在Java集合框架中扮演什么角色？ LinkedHashMap集合--原理可視化 HashMap集合--基本操作流程的源碼可視化 Java集合--HashMap底層原理可視化，秒懂?dāng)U容、鏈化、樹化 Java集合--從本質(zhì)出發(fā)理解HashMap Java集合--LinkedList源碼可視化 Java集合源碼--ArrayList的可視化操作過(guò)程
設(shè)計(jì)模式秘籍 （已全部開(kāi)源）	掌握設(shè)計(jì)模式的兩個(gè)秘籍 往期設(shè)計(jì)模式文章的：設(shè)計(jì)模式
軟件設(shè)計(jì)師	軟考中級(jí)--軟件設(shè)計(jì)師毫無(wú)保留的備考分享 通過(guò)軟考后卻領(lǐng)取不到實(shí)體證書？ 2023年下半年軟考考試重磅消息
Java學(xué)習(xí)路線 和相應(yīng)資源	Java全棧學(xué)習(xí)路線、學(xué)習(xí)資源和面試題一條龍

原創(chuàng)不易，覺(jué)得還不錯(cuò)的，三連支持：點(diǎn)贊、分享、推薦↓