arraydeque方法_双端队列如何理解

大家好，又见面了，我是你们的朋友全栈君。如果您正在找激活码,请点击查看最新教程,关注关注公众号 “全栈程序员社区” 获取激活教程,可能之前旧版本教程已经失效.最新Idea2022.1教程亲测有效,一键激活。

Jetbrains全系列IDE使用 1年只要46元售后保障童叟无欺

ArrayDeque双端队列完全解析

重点：

底层通过循环数组实现俩个重要属性 head tail
不能添加null值，不然会报空指针
每次扩容都是2的n次方
可以实现普通队列先进先出排序，也可以实现栈先进后出的排序
特别留意，它里面通过二进制方式判断数组是否已满
(tail = (tail + 1) & (elements.length – 1)) == head
注意操作插入和移除时，有Throws exception 和 return Special value 俩种情况

循环数组概念

我们知道，ArrayDeque是通过数组实现队列功能的；而且具有对数组头尾双端添加和移除对象的功能，但如果数组不能实现循环功能，会出现以下情况

图一

在构建一个ArrayDeque对象时，会初始化head和tail的值为0.当有对象加入数组时，tail的值加1，当有对象出列时，head的值会加1.
而head值 == tail值，可以帮我们判断数组是已经满。

如果数组容量固定的情况下，从尾追加数据，从头出列数据，会出现实际数组有空的单元，但却tail会超过数组容量的情况，这种现象称为“假溢出” ；但往往，不可能是一种容量固定的数组，一般会有实现自动扩容的方法，但即便可以扩容，按照上面的逻辑，数组容量不断扩大，tail值一直向后，但从头出列的数据越来起多，前面空的内存单造成的浪费更是不能忽略了。

再往下想，不是说Deque接口实现了头和尾添加和删除数据的功能吗？那它不是可以从头添加数据，不就可以利用到前面已经出列的空的单元吗？
但如果就是单纯的就是在往后追加数据呢？那前面空出的内存单元，就这样舍弃掉？简直“暴殄天物”。

所以，为了解决数组单元浪费的问题，就产生了循环数组。且看图
图二

从上图可知，当tail值超过数组索引后，就回到了索引为0的地方，实现了内存单元循环利用。
你可以想象成，数组尾和头尾首相连，形成逻辑上的”环形“。
但同时，你要清楚，上图中的例子，是头部已经有出列，有空的单元时，tail值回到的索引0的地方，但如果索引为0的地方有值时，此时，想要实现新对象的保存，也只能重新去扩容了。
可知，循环数组可以实现有限数组容量的的高效利用，但新值不会覆盖原值。

讲到这里，如果有细心猿会现，我图一在初始化时，tail和head都是对应索引为0的数组，我说数据从尾部追加，那应该调用的是addlast方法，但上图添加数据分明是从索引0开始追加的，是按照数组顺序的，和实际情况不相符啊。而且，如果从后面追加数据的话，你的tail值怎么移动？

正如猿发现的问题一样，确实，我上面的例子不够严谨，请看下图

图三

我先调用addLast方法，把1加入数组，1位于数组尾部
我再调用addLast方法，把2加入数组，2替换1的位置，追加尾部，1向前存储一个单元
我先调用addFirst方法，把A加入数组，A位于数组头部
我再调用addFirst方法，把B加入数组，B替换A的位置，放置数组头部，A向后存储一个单元

所以，严格来说，无论是addLast 还是addFirst方法，都不按照数组顺序加入数据的（按照索引顺序）；而是根据头尾，新追加数据会占用头尾位置，原来头尾位置的数据后移或前移；

那么，tail值和head值怎么移动呢？
其实，每增加一个对象，tail值就会+1 ，每移除一个对象，head值+1 ;
并非如图一那样，head和tail值都要从左到右移动的那种样式。
tail值和head值可以理作为一个标的，最后，通过tail和head值来确定数组是否已满

那么这个标的是怎么实现判断数组已满的呢？

循环数组已满判断

jdk源码里面，通过 (tail = (tail + 1) & (elements.length – 1)) == head 来判断数组已满，并且要求数组每次扩容的长度为2的n次方来使得上面的等式有效；

这个怎么理解呢？

注意，

上图选取是长度为8的数组
index[0,7]
上图中tail的值已为公式tail=(tail+1)中+1后的tail值

我们来看一个源码

   public void addLast(E e) {
        if (e == null)
            throw new NullPointerException();
        elements[tail] = e;
        if ( (tail = (tail + 1) & (elements.length - 1)) == head)
            doubleCapacity();
    }

在这个方法中，tail值的+1是放在if判断中的，并没有单独写tail++ 这样的语句，而不管if条件是否成立，tail的值都是会+1，而我上图中的标注的tail值是已+1过的。

情况一，数组未出列，往数组里添加8个元素后，tail值每次+1，最后值为8
代入公式中(tail = (tail + 1) & (elements.length – 1)) == head
为（8 & 7）==0 转为二进制为（1000 & 111 ）==0 000 结果返回true.

情况二，数组出列2个，往数里面加了10个数据，tail值变为10.代入公式为（10 & 7）==2 转为二进制为（1010 & 111）=10 ，返回true.

可见，上述公式是在数组为2的n次长度时，是成立的。但如果是非2的n次方容量呢，还成立吗？

举例

代入公式为（7 & 6）==0 转为二进制为（（111 & 110）=110 ）≠ 000

当然上面的例子你也可以再多找几个，你会发现真的只有当数组容量为2的n次方时，jdk提供的等式是成立的。

另外，ArrayDeque提供了可以指定数组容量的构造器，那我输入非2的n次方数值，内部会发生什么？

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

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)   // Too many elements, must back off
                initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements
        }
        return initialCapacity;
    }

它的内部是通过位移动算符 >>> 和位运算符 | 实现的
| = 这样的符号表示右边的值和左边的值通过位运算符 | 操作后赋值给左边的值。
通过一系列的运算符操作，随机输入的数值，最后转换成比原数值大，且和它最近的2的n次方数值。

费话不说，我们来举例传入 12