ArrayDeque双端队列--底层原理可视化

主要学习双端队列 ArrayDeque ，通过对其栈功能的使用，掌握循环数组底层原理
觉得文章枯燥的可以结合ArrayDeque 底层原理可视化视频：https://www.bilibili.com/video/BV1zChGz8EVL/

有环形的数组？同时具备栈功能和队列功能？

1. Java 中的栈实现

在Java中，栈类你可以直接找到的是Stack类。Stack类实在JDK 1.0 的时候就有了，但你会发现在Stack类头注释写着：建议优先使用Deque接口及其实现类，例如：ArrayDeque。
1.1. Stack

Stack 继承自 Vector，线程安全，但因每次操作都要加锁，性能较差。Vector 集合基本也不会用到的。
示例：

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

复制代码

1.2. LinkedList

LinkedList实现了Deque双端队列接口，具备了队列功能和栈功能，也就是说LinkedList 可以当做普通List集合来用，同时还可以当做栈或队列来使用。
以下是通过LinkedList 来实现入栈、出栈操作：

1. LinkedList<String> linkedList = new LinkedList<>();
2. // 入栈
3. linkedList.push("渊");
4. linkedList.push("渟");
5. linkedList.push("岳");
6. linkedList.push("Why?");
7. System.out.println(linkedList); // [Why?, 岳, 渟, 渊]
8. // 获取栈顶元素
9. String peek = linkedList.peek();//不会出栈
10. System.out.println(peek); // Why?
11. // 出栈
12. String pop = linkedList.pop();//出栈一个
13. System.out.println(pop);// Why?
14. linkedList.pop();   //再出栈一个,不获取结果
15. System.out.println(linkedList);// 剩下的元素：[渟, 渊]

复制代码

使用双端队列功能时，如果你想将引用改为接口名，
❌这样写是错的：List linkedList = new LinkedList();
✔得这样写才行：Deque linkedList = new LinkedList();
1.3. ArrayDeque

Deque接口为双端队列接口，ArrayDeque实现了该接口。
ArrayDeque 看命名就知道是双端队列，并且底层数据结构为数组。ArrayDeque除了具有队列（FIFO）功能，同时它还具备栈（LIFO）功能，所以它可以当做栈来使用。
栈功能示例：

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

复制代码

LinkedList在集合学习时已经学过了，它的双端队列功能并不会影响底层数据结构，仅仅是操作逻辑不同而已。
在双端队列功能上，LinkedList没有ArrayDeque性能高，通常使用ArrayDeque更多，所以我们详细来学学ArrayDeque有什么独特之处？
2. ArrayDeque底层原理

在Java中，可以通过双端队列Deque的实现类来实现栈功能，常用的有两个：ArrayDeque 和 LinkedList。
两个类继承与实现：

1. // ArrayDeque
2. public class ArrayDeque<E> extends AbstractCollection<E>
3.                            implements Deque<E>, Cloneable, Serializable
4. // LinkedList
5. public class LinkedList<E>
6.     extends AbstractSequentialList<E>
7.     implements List<E>, Deque<E>, Cloneable, java.io.Serializable

复制代码

LinkedList 实现类既是List集合、同时又是Deque双端队列，也就是说，这个类具备多种功能：链式集合、链式队列和链式栈三种功能。
ArrayDeque 实现类具备两种功能：队列和栈。
上一篇栈的文章也讲述过使用单链表实现自定义栈，并使用自定义栈完成了有效括号匹配实战，在此，主要完成ArrayDeque栈功能的学习。
2.1. ArrayDeque的数据结构

看命名就知道是双端队列，并且底层数据结构为数组。ArrayDeque类主要字段如下：

1. public class ArrayDeque<E> extends AbstractCollection<E>
2.                            implements Deque<E>, Cloneable, Serializable{
3.     // 数据就保存在这个数组，大小总是2的幂
4.     transient Object[] elements;
5.         // 头索引
6.     transient int head;
7.         // 尾索引
8.     transient int tail;
9.     // 允许最小容量
10.     private static final int MIN_INITIAL_CAPACITY = 8;
12.         ...
13. }

复制代码

特别说明下MIN_INITIAL_CAPACITY=8，这个最小容量是在你指定ArrayDeque大小时才会用到。比如你指定大小为7，那它创建出来的大小为8，它的计算逻辑和HashMap的一模一样。ArrayDeque的默认大小为16。相关代码如下：

1. // 默认构造方法
2. public ArrayDeque() {
3.         elements = new Object[16];
4. }
6. // 指定大小构造方法
7. public ArrayDeque(int numElements) {
8.         allocateElements(numElements);
9. }
11. private void allocateElements(int numElements) {
12.         elements = new Object[calculateSize(numElements)];
13. }
15. // 计算结果为2的幂次方，跟HashMap的计算逻辑一样
16. private static int calculateSize(int numElements) {
17.         int initialCapacity = MIN_INITIAL_CAPACITY;
18.        
19.         if (numElements >= initialCapacity) {
20.                 initialCapacity = numElements;
21.                 initialCapacity |= (initialCapacity >>>  1);
22.                 initialCapacity |= (initialCapacity >>>  2);
23.                 initialCapacity |= (initialCapacity >>>  4);
24.                 initialCapacity |= (initialCapacity >>>  8);
25.                 initialCapacity |= (initialCapacity >>> 16);
26.                 initialCapacity++;
28.                 if (initialCapacity < 0)
29.                         initialCapacity >>>= 1;
30.         }
31.         return initialCapacity;
32. }

复制代码

2.2. 为什么大小设置为2的幂次方？

如果学过HashMap底层实现逻辑，那就非常容易理解，之前的HashMap文章还专门讲了这个。
它是HashMap的哈希值映射数组下标和ArrayDeque循环数组得以实现的基石。
使得通过与(&)运算高效完成数组下标映射，非常方便哈希值映射计算和循环索引计算。为得就是方便计算元素索引位置、提高计算效率，特别是扩容后需要做的调整，也变得简单高效。
通过添加元素（入栈）、动态扩容和移除元素（出栈）这些操作感受与（&）运算的巧妙之处。
2.3. 添加元素--入栈

从添加元素开始，直到元素达到阈值后触发动态扩容，再接着学习动态扩容。
元素入栈操作：

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

复制代码

执行结果：

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

结果怎么反过来的？？
我们看看源码怎么写的

1. public void push(E e) {
2.         addFirst(e);
3. }
5. public void addFirst(E e) {
6.         // 不允许存放 null 元素
7.         if (e == null)
8.                 throw new NullPointerException();
9.         // 入栈元素位置计算
10.         elements[head = (head - 1) & (elements.length - 1)] = e;
11.         if (head == tail)
12.                 doubleCapacity();
13. }

复制代码

计算新的 head 索引并插入元素

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

复制代码

head为int数据类型，成员变量默认为：0；
head - 1：在当前 head 之前的那个槽位，也就是“往左移一格”，第一次插入时为：-1；
& (elements.length - 1)：取模运算，但因为 elements.length 总是 2 的幂，这里用位运算更高效；
head = …：先更新 head 成新位置，再把 e 存入 elements[head];
这样无论 head 从 0 跑到 -1，按位与都会自动“回绕”到数组末尾，实现循环缓冲。
说那么多也没啥印象，来个计算过程图示：

所以，push入栈是从数组的末端开始，往回入栈的，ArrayDeque的数据结构为循环数组。
循环数组数据结构如图：

2.4. 动态扩容

栈和队列就像List集合那样，使用时可能并不会知道集合大小为多少，所以ArrayDeque需要像ArrayList一样需要动态扩容。
ArrayDeque的动态扩容像HashMap一样，扩容时候为2的倍数，确保大小一直为2的幂次方。
动态扩容只会在元素入栈的时候才会触发，addFirst触发扩容条件的源码

1. if (head == tail)
2.         doubleCapacity();

复制代码

动态扩容关键源码为
[code]private void doubleCapacity() {        assert head == tail;        int p = head;        // 数组大小        int n = elements.length;        // p右边元素的个数        int r = n - p;        // 容量翻倍        int newCapacity = n

不错，里面软件多更新就更好了

懂技术并乐意极积无私分享的人越来越少。珍惜

热心回复！

新版吗？好像是停更了吧。