ArrayDeque底层实现

一、什么是ArrayDeque

1、Deque与Queue

了解这个之前，我们要先知道什么是Deque，它和Queue有什么区别：在java中，Queue被定义成单端队列使用，Deque被定义成双端队列 即Queue可以访问两端但是只能修改队头，而Deque可以访问两端并且可以在队首和队尾删除和插入元素。
基于Deque的特性，ArrayDeque即可以作为Queue来使用也可以作为栈来使用，而且可以决定队列那边受限或者栈哪边进出。

2、ArrayDeque的构造器

public ArrayDeque() {
    elements = new Object[16];
}

public ArrayDeque(int numElements) {
    allocateElements(numElements);//调用allocateElements方法
}

private void allocateElements(int numElements) {
	//初始化elements元数据数组，长度由calculateSize方法决定
    elements = new Object[calculateSize(numElements)];
}

// 找到大于需要长度的最小的2的幂整数，至少要大于8
private void allocateElements(int numElements) {
	// MIN_INITIAL_CAPACITY为8
    int initialCapacity = MIN_INITIAL_CAPACITY;
	// 假设用户输入的为9
    if (numElements >= initialCapacity) {
		// initialCapacity = 9; 
        initialCapacity = numElements;
		// initialCapacity = 9 | ( 9 >>> 1)
		// initialCapacity = ( 1001 ) | ( 0100 ) = 1101 = 13;
        initialCapacity |= (initialCapacity >>>  1);
		// initialCapacity = 13 | ( 13 >>> 2)
		// initialCapacity = ( 1101 ) | ( 0011 ) = 1111 = 15;
        initialCapacity |= (initialCapacity >>>  2);
		// initialCapacity = 15 | ( 15 >>> 4)
		// initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15;
        initialCapacity |= (initialCapacity >>>  4);
		// initialCapacity = 15 | ( 15 >>> 8)
		// initialCapacity = ( 1111 ) | ( 0000 ) = 1111 = 15;
        initialCapacity |= (initialCapacity >>>  8);
        initialCapacity |= (initialCapacity >>> 16);
		// 15+1 = 16;
        initialCapacity++;

        if (initialCapacity < 0)    // 超过int的上限了,即符号位为1，其它位全为0
            initialCapacity >>>= 1; // 设置为2^30次方
    }
	// 创建数组（数组的长度为：大于需要长度的最小的2的幂整数）
    elements = new Object[initialCapacity];
}

以上两个构造方法实现中：
第一个构造方法，创建一个默认长度为8的数组；

第二个构造方法，如代码中注释举例，其会通过allocateElements(numElements)将数组的长度定义为2的幂（找到大于需要长度的最小的2的幂整数）；
allocateElements(numElements)方法：可以将一个任意的初始值转化为2^n的值。
如果本身传进来的值就是2^n 的值，那么经过转化会变成2^(n+1)；
如果传入的值大于等于2^30，那么经过转化会变成负值，即< 0，此时会把初始值设置为2^30， 即最大的容量只有2^30；

补码变1原理

我们了解到要找到大于或等于整数 numElements 的最小的 2 的幂可以先把最高位及以下的所有低位「变」成 1，然后再加 1
一个问题就是如果这个数刚好是2的整数幂，那么这么操作后就会变为原数的两倍，但对于ArrayDequq，刚好满足要存的数显然是不行的，所以避免后面的扩容操作，不如在初始化的时候就设置为两倍大小。
如上面的例子，

• initialCapacity |= (initialCapacity >>> 1); 是将最高位右移1位使得最高位和次高位设置为1
• initialCapacity |= (initialCapacity >>> 2);在上一步的基础上，将最高位和次高位右移两位，使得前四位都为1，后面的步骤类似
• 一直到initialCapacity |= (initialCapacity >>> 16);操作后如果最高位在31位（因为如果32位为1那么就是负数，则会在最开始就设置为8）那么所有位都会变为1（除符号位）
• 执行加1操作，得到大于等于设置值得最小2的幂，然后判断是否小于0
• 小于0说明越界，即int无法存储这个数，此时我们得到的数应该是符号位位1，其它位为0的数，右移一位将数组容量设置为最大值2^30

二、ArrayDeque对数据的操作

注：因为Deque是Queue的实现类，所以以上12个方法Deque都有

上面两个表共定义了Deque的12个接口。添加，删除，取值都有两套接口，它们功能相同，区别是对失败情况的处理不同。一套接口遇到失败就会抛出异常，另一套遇到失败会返回特殊值（false或null）。除非某种实现对容量有限制，大多数情况下，添加操作是不会失败的。 虽然Deque的接口有12个之多，但无非就是对容器的两端进行操作，或添加，或删除，或查看。明白了这一点讲解起来就会非常简单。
摘自链接: Java ArrayDeque源码剖析.

三、ArrayDeque的底层实现

首先要知道ArrayDeque底层为数组，那么数组如何实现双端队列呢？

1、ArrayDeque成员变量

transient Object[] elements; //元数据数组
transient int head;//队列头部所在位置
transient int tail;//尾部所在位置

至于为何要给element数组使用transient修饰，原因和ArrayList一样，就是防止扩容后网络传输没用的数据影响效率。

2、ArrayDeque双端队列实现原理

ArrayDeque底层通过数组实现，为了满足可以同时在数组两端插入或删除元素的需求，该数组还必须是循环的，即循环数组（circular array），也就是说数组的任何一点都可能被看作起点或者终点。

如何实现循环数组？

在队头插入数据源码：

// 在队列前边 添加元素
public void addFirst(E e) {
	// 存入空数据时，抛出异常NullPointerException
    if (e == null)
        throw new NullPointerException();
    elements[head = (head - 1) & (elements.length - 1)] = e;
    
	// 空间不足
    if (head == tail)
        doubleCapacity(); // 扩容
}

head = head - 1即，将新数据赋值给head的前一个位置，所以head指向的是队头的第一个元素。

下标越界的处理解决起来非常简单，head = (head - 1) & (elements.length - 1)就可以了，这段代码相当于取余，同时解决了head为负值的情况。因为elements.length必需是2的指数倍，elements - 1就是二进制低位全1，跟head - 1相与之后就起到了取模的作用，如果head - 1为负数（其实只可能是-1），则相当于对其取相对于elements.length的补码。

在队尾插入数据源码

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

首先进行赋值，可以了解到tail指向的是队尾的第一个可以插入元素的空位，然后再将tail向后移一位。下标越界与head一样。

判断队满与扩容

当head和tail指向同一个位置时表示队满，调用doubleCapacity();方法，将容量扩大为原来的两倍。

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 = a;
    head = 0;
    tail = n;
}

首先复制head右边的数据，再复制head左边的数据，然后设置head为0，tail为原数组长度。

四、ArrayDeque与LinkedList的比较

ArrayDeque和LinkedList都实现了Deque，都能作为双端队列使用，但是ArrayDeque为变长数组，有要扩容的问题
LinkedList使用Node来存储数据，数据的插入伴随着对象的创建，使得插入操作速度较慢，占用空间大
一般来说，数据量少的建议使用LinkedList，数据量大的建议使用ArrayDeque。

ArrayDeque的缺点：

• ①不能存储null
• ②线程不安全，LinkedList可以通过Collections.synchronizedList()获取线程安全的LinkedList
• ③不支持随机访问和随机插入数据

注：ArrayDeque遍历采用iterator遍历。