【源码解析】你真的了解ArrayDeque嘛?

3,276 阅读6分钟

积千里跬步,汇万里江河;每天进步一点点,终有一天将成大佬

前言

上篇文章说LinkedList也可以实现队列的功能,但是我们一般要用队列功能的话推荐使用ArrayDeque,因为他底层是数组,而队列和栈都是只要操作头部或尾部,所以这样的话数组的性能就比链表快一点。

LinkedListArrayDeque都是通过实现了Deque这个接口来获得队列的功能。而Deque这个接口通过继承Queue这个接口来取得队列功能,然后在这个基础进行扩展,实现了双端队列,由此可以获得的功能。为了空间能得到充分利用,ArrayDeque使用了循环队列;还有LinkedList可以插入null值,而ArrayDeque是不能插入null的。

什么是双端队列?

简单来说,就是两端都可以操作的队列(🌚说了和没说一样…)。哈哈,还是看图吧

一般队列是这样的:

双端队列是这样的

总的来说,普通队列只可在头部删除元素和尾部添加元素,而双端队列头部和尾部都可以添加和删除元素

什么是循环队列?

不如说你定了个5容量大小的数组,你第一次插入的位置是下标为2,当你添加第4个元素的时候,他不会进行扩容,而是通过头尾指针进行对比,然后把数据插入到下标为0的位置上。当头尾指针相等时,表示这个队列数组已经满了,这时才会扩容。

这里的数组从上向下的顺序,有人会问为什么头尾指针都指向第三个方格呢?因为这边演示的是第一个元素插入到下标为2的位置嘛。。当然,ArrayDeque是从0开始的,所以初始化时头尾指针都是指向下标为0的位置上。

Deque有什么?

话不多说,看图:

ArrayDeque具体实现的方法主要在蓝色的方框里,其他两个颜色的方框都是通过调用蓝色方框里的这些方法来实现相关功能的,可以再看一张我画的脑图:

这边队列的每种功能都有两个方法,其中add()remove()element()如果操作失败会报异常offer()poll()peek()操作失败会返回null或者false

其实真正用到的就深红色方框里写的这些方法,所以本文我就说这四个方法,addLast()pollFirstgetFirst()addFirst()peekFirst

内部变量

ArrayDeque内部就只有4个变量,对象数组element[]头指针head尾指针tailMIN_INITIAL_CAPACITY表示最小初始化容量为8

构造方法

构造方法和其他集合一样,有有参构造无参构造

无参构造

很简单,直接初始化一个容量为16的对象数组

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

有参构造

传入参数为int数

public ArrayDeque(int numElements) {
    allocateElements(numElements);
}
  • allocateElements(int numElements)分配空数组以容纳给定数量的元素。
private void allocateElements(int numElements) {
    elements = new Object[calculateSize(numElements)];
}
  • calculateSize(int numElements)调整传入的值大小

上面的算法中用到了位运算,如果不了解位运算的话,可以看位运算这篇文章。这里把数值设置成2的n次方(是整数次),是为了满足下面要说的循环队列这个算法

传入的参数为集合对象

public ArrayDeque(Collection<? extends E> c) {
    allocateElements(c.size());
    addAll(c);
}

第一步调用了和上面一样的方法,这里多了个addAll()方法

  • addAll(Collection c)

这边复制时并没有用和ArrayList一样的System.arraycopy()方法,而是采用for循环来调用add()方法进行一个一个添加的;为什么这么做呢?因为ArrayDeque和其他集合不一样,它里面是不能有null值的,而其他集合里面有的是可以传null的,所以这边采用add()一个一个的加,add()方法如果传入的值为空的话,就会报异常;(add()实际调用的是addLast(),下面再讲)

addLast()

源码解析

这个方法的意思是添加数据到尾部,下面图片方框中的位与算法是实现循环队列这个功能的核心算法

还记得上面初始化时候,不管传入的是什么数值,最后出来的都是(整数次)方。这个算法就是&右边为时,&左边的数为正整数时,不管有多大,最后的结果永远<=;当&左边的数为0时,结果为0;当&左边的数为负数时,-1=

举一些例子:当

  • 4&7=4 9&7=1 22&7=6
  • 0&7=0
  • -1&7=7 -2&7=6 -8&7=0
  • doubleCapacity()扩容为原来的2倍

流程图

方便理解,我画下上扩容的流程图,比如head在中间:

pollFirst()

移除头部数据

源码解析

删除的时候并没有像ArrayList一样移动数据,而只是移动了head指向的位置

流程图

getFirst()和peekFirst()

这两个方法都是一样的,都是直接返回head指向的数据,区别就是一个会抛异常,一个不会

源码分析

  • getFirst()
public E getFirst() {
    @SuppressWarnings("unchecked")
    E result = (E) elements[head];
    if (result == null)
        throw new NoSuchElementException();
    return result;
}
  • peekFirst()
public E peekFirst() {
    // elements[head] is null if deque empty
    return (E) elements[head];
}

addFirst()

源码解析

这里还是用了上面讲了位与算法,算出head的值,然后插入数据

流程图

clear()

源码解析

清空这个操作是从head指向的元素开始删除,直到head=tail,清空完成;

size()

这个获取队列的大小也是用了上面讲的位与算法,用尾部减去了头部,然后位与数组的长度-1。为什么要这么弄呢?直接向ArrayListLinkedList一样定义个size不好嘛?你不觉得这样更方便吗?少了一个变量,就少维护了一个变量,就少了一个安全隐患啊

public int size() {
    return (tail - head) & (elements.length - 1);
}

总结

上面的方法基本上有位与这个算法的身影,可见这个是核心了;如果不了解位运算的话,可以看位运算这篇文章;

核心算法:

&右边为时,&左边的数为正整数时,不管有多大,最后的结果永远<=;当&左边的数为0时,结果为0;当&左边的数为负数时,-1=

ArrayDeque无参构造方法是直接初始化一个容量为16的空数组,而上篇ArrayList文章里,它无参构造方法是初始化了一个空数组,在第一次添加数据的时候才进行扩容到10;

ArrayDeque每次扩容为原来数组长度的2倍

ArrayDeque不能插入null