关于算法:ArrayDequeJDK双端队列源码深度剖析

在本篇文章当中次要跟大家介绍 JDK 给咱们提供的一种用数组实现的 双端队列 ，在之前的文章 LinkedList 源码分析当中咱们曾经介绍了一种 双端队列 ，不过与ArrayDeque 不同的是，LinkedList的双端队列应用双向链表实现的。

咱们通常所议论到的队列都是一端进一端出，而双端队列的两端则都是可进可出。上面是双端队列的几个操作：

数据从双端队列左侧进入。
数据从双端队列右侧进入。

数据从双端队列左侧弹出。

数据从双端队列右侧弹出。

而在 ArrayDeque 当中也给咱们提供了对应的办法去实现，比方上面这个例子就是上图对应的代码操作：

public void test() {ArrayDeque<Integer> deque = new ArrayDeque<>();
    deque.addLast(100);
    System.out.println(deque);
    deque.addFirst(55);
    System.out.println(deque);
    deque.addLast(-55);
    System.out.println(deque);
    deque.removeFirst();
    System.out.println(deque);
    deque.removeLast();
    System.out.println(deque);
}
// 输入后果
[100]
[55, 100]
[55, 100, -55]
[100, -55]
[100]

ArrayDeque底层是应用数组实现的，而且数组的长度必须是 2 的整数次幂，这么操作的起因是为了前面位运算好操作。在 ArrayDeque 当中有两个整形变量 head 和tail，别离指向右侧的第一个进入队列的数据和左侧第一个进行队列的数据，整个内存布局如下图所示：

其中 tail 指的地位没有数据，head指的地位存在数据。

当咱们须要从左往右减少数据时（入队），内存当中数据变动状况如下：

当咱们须要从右往做左减少数据时（入队），内存当中数据变动状况如下：

当咱们须要从右往左删除数据时（出队），内存当中数据变动状况如下：

当咱们须要从左往右删除数据时（出队），内存当中数据变动状况如下：

下面次要议论到的数组在内存当中的布局，然而他是具体的物理存储数据的程序，这个程序和咱们的逻辑上的程序是不一样的，依据下面的插入程序，咱们能够画出上面的图，大家能够仔细分析一下这个图的程序问题。

上图当中队列左侧的如队程序是 0, 1, 2, 3，右侧入队的程序为 15, 14, 13, 12, 11, 10, 9, 8，因而在逻辑上咱们的队列当中的数据布局如下图所示：

依据后面一大节谈到的输出在入队的时候数组当中数据的变动咱们能够晓得，数据在数组当中的布局为：

// 底层用于存储具体数据的数组
transient Object[] elements;
// 这就是后面谈到的 head
transient int head;
// 与上文谈到的 tail 含意一样
transient int tail;
// MIN_INITIAL_CAPACITY 示意数组 elements 的最短长度
private static final int MIN_INITIAL_CAPACITY = 8;

以上就是 ArrayDeque 当中的最次要的字段，其含意还是比拟容易了解的！

默认构造函数，数组默认申请的长度为16。

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

指定数组长度的初始化长度，上面列出了改构造函数波及的所有函数。

public ArrayDeque(int numElements) {allocateElements(numElements);
}

private void allocateElements(int numElements) {elements = new Object[calculateSize(numElements)];
}
private static int calculateSize(int numElements) {
    int initialCapacity = MIN_INITIAL_CAPACITY;
    // Find the best power of two to hold elements.
    // Tests "<=" because arrays aren't kept full.
    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;
}

下面的最难了解的就是函数 calculateSize 了，他的次要作用是如果用户输出的长度小于 MIN_INITIAL_CAPACITY 时，返回 MIN_INITIAL_CAPACITY。否则返回比initialCapacity 大的第一个是 2 的整数幂的整数，比如说如果输出的是 9 返回的 16，输出4 返回8。

calculateSize的代码还是很难了解的，让咱们一点一点的来剖析。首先咱们应用一个 2 的整数次幂的数进行下面 移位操作 的操作！

从上图当中咱们会发现，咱们在一个数的二进制数的 32 位放一个 1，通过移位之后最终32 位的比特数字全副变成了 1。依据下面数字变动的法则咱们能够发现，任何一个比特通过下面移位的变动，这个比特前面的31 个比特位都会变成1，像下图那样：

因而上述的移位操作的后果只取决于最高一位的比特值为 1，移位操作后它前面的所有比特位的值全为1，而在下面函数的最初，咱们返回的后果就是下面移位之后的后果 +1。又因为移位之后最高位的1 到最低位的 1 之间的比特值全为 1，当咱们+1 之后他会一直的进位，最终只有一个比特地位是 1，因而它是2 的整数倍。

通过上述过程剖析，咱们就能够立刻函数 calculateSize 了。

// tail 的初始值为 0 
public void addLast(E e) {if (e == null)
        throw new NullPointerException();
    elements[tail] = e;
    // 这里进行的 & 位运算 相当于取余数操作
    // (tail + 1) & (elements.length - 1) == (tail + 1) % elements.length
    // 这个操作次要是用于判断数组是否满了，如果满了则须要扩容
    // 同时这个操作将 tail + 1，即 tail = tail + 1
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();}

代码 (tail + 1) & (elements.length - 1) == (tail + 1) % elements.length 成立的起因是任意一个数 $a$ 对 $2^n$ 进行取余数操作和 $a$ 跟 $2^n – 1$ 进行 & 运算的后果相等，即：

$$
a\% 2^n = a \& (2^n – 1)
$$

从下面的代码来看下标为 tail 的地位是没有数据的，是一个空地位。

// head 的初始值为 0 
public void addFirst(E e) {if (e == null)
        throw new NullPointerException();
    // 若此时数组长度 elements.length = 16
    // 那么上面代码执行过后 head = 15
    // 上面代码的操作后果和上面两行代码含意统一
    // elements[(head - 1 + elements.length) % elements.length] = e
    // head = (head - 1 + elements.length) % elements.length
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)
        doubleCapacity();}

下面代码操作后果和上文当中咱们提到的，在队列当中从右向左退出数据一样。从下面的代码看，咱们能够发现下标为 head 的地位是存在数据的。

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];
    // arraycopy(Object src,  int  srcPos,
                                        Object dest, int destPos,
                                        int length)
    // 下面是函数 System.arraycopy 的函数参数列表
    // 大家能够参考下面了解上面的拷贝代码
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0;
    tail = n;
}

下面的代码还是比较简单的，这里给大家一个图示，大家就更加容易了解了：

扩容之后将原来数组的数据拷贝到了新数组当中，尽管数据在旧数组和新数组当中的程序发生变化了，然而他们的绝对程序却没有发生变化，他们的逻辑程序也是一样的，这里的逻辑可能有点绕，大家在这里能够好好思考一下。

pollLast 和 pollFirst 函数剖析

这两个函数的代码就比较简单了，大家能够依据前文所谈到的内容和图示去了解上面的代码。

public E pollLast() {
    // 计算出待删除的数据的下标
    int t = (tail - 1) & (elements.length - 1);
    @SuppressWarnings("unchecked")
    E result = (E) elements[t];
    if (result == null)
        return null;
    // 将须要删除的数据的下标值设置为 null 这样这块内存就
    // 能够被回收了
    elements[t] = null;
    tail = t;
    return result;
}

public E pollFirst() {
    int h = head;
    @SuppressWarnings("unchecked")
    E result = (E) elements[h];
    // Element is null if deque empty
    if (result == null)
        return null;
    elements[h] = null;     // Must null out slot
    head = (h + 1) & (elements.length - 1);
    return result;
}

在本篇文章当中，次要跟大家分享了 ArrayDeque 的设计原理，和他的底层实现过程。ArrayDeque底层数组当中的数据程序和队列的逻辑程序这部分可能比拟形象，大家能够依据图示好好领会一下！！！

以上就是本篇文章的所有内容了，心愿大家有所播种，我是 LeHung，咱们下期再见！！！都看到这里了，给孩子一个赞（start）吧，收费的哦!!!

更多精彩内容合集可拜访我的项目：https://github.com/Chang-LeHu…

关注公众号：一无是处的钻研僧，理解更多计算机（Java、Python、计算机系统根底、算法与数据结构）常识。

关于算法:ArrayDequeJDK双端队列源码深度剖析

ArrayDeque（JDK 双端队列）源码深度分析

前言

双端队列整体剖析

数组实现 ArrayDeque(双端队列)的原理

底层数据遍历程序和逻辑程序

ArrayDeque 类关键字段剖析

ArrayDeque 构造函数剖析

ArrayDeque 要害函数剖析

addLast 函数剖析

addFirst 函数剖析

doubleCapacity 函数剖析

pollLast 和 pollFirst 函数剖析

总结