积千里跬步,汇万里江河;每天进步一点点,终有一天将成大佬
上篇文章说LinkedList也可以实现 队列
和 栈
的功能,但是我们一般要用队列功能的话推荐使用 ArrayDeque
,因为他层是 数组 ,而队列和栈都是只要 操作头部或尾部 ,所以这样的话数组的性能就比链表快一点,因为它不要找,可以直接通过数组下标获取元素,而链表操作头部或尾部都要通过 二分查找算法
先找到头部或尾部,然后再进行操作。
LinkedList 和 ArrayDeque
都是通过实现了 Deque
这个接口来获得 队列
和 栈
的功能。而 Deque
这个接口通过继承 Queue
这个接口来取得队列功能,然后在这个基础进行扩展,实现了 双端队列
,由此可以获得 栈
的功能。为了空间能得到充分利用, ArrayDeque
使用了 循环队列
;还有LinkedList可以插入 null
值,而 ArrayDeque
是不能插入 null
的。
简单来说,就是两端都可以操作的队列(:new_moon_with_face:说了和没说一样…)。哈哈,还是看图吧
一般队列是这样的:
双端队列是这样的
不如说你定了个5容量大小的数组,你第一次插入的位置是下标为2,当你添加第4个元素的时候,他不会进行扩容,而是通过 头尾指针 进行对比,然后把数据插入到下标为0的位置上。当 头尾指针相等时 ,表示这个队列数组已经满了,这时才会扩容。
这里的数组从上向下的顺序,有人会问为什么头尾指针都指向第三个方格呢?因为这边演示的是第一个元素插入到下标为2的位置嘛。。当然, ArrayDeque
是从0开始的,所以初始化时头尾指针都是指向下标为0的位置上。
话不多说,看图:
ArrayDeque
具体实现的方法主要在蓝色的方框里,其他两个颜色的方框都是通过调用蓝色方框里的这些方法来实现相关功能的,可以再看一张我画的脑图:
这边队列的每种功能都有两个方法,其中 add()
, remove()
, element()
如果操作失败会 报异常 , offer()
, poll()
, peek()
操作失败会 返回null或者false
其实真正用到的就 深红色方框 里写的这些方法,所以本文我就说这四个方法, addLast()
, pollFirst
, getFirst()
, addFirst()
, peekFirst
;
ArrayDeque内部就只有4个变量, 对象数组element[] , 头指针head , 尾指针tail , MIN_INITIAL_CAPACITY表示最小初始化容量为8
构造方法和其他集合一样,有 有参构造 和 无参构造
很简单,直接初始化一个 容量为16 的对象数组
public ArrayDeque() { elements = new Object[16]; } 复制代码
public ArrayDeque(int numElements) { allocateElements(numElements); } 复制代码
private void allocateElements(int numElements) { elements = new Object[calculateSize(numElements)]; } 复制代码
循环队列
这个算法 public ArrayDeque(Collection<? extends E> c) { allocateElements(c.size()); addAll(c); } 复制代码
第一步调用了和上面一样的方法,这里多了个 addAll()
方法
这边复制时并没有用和 ArrayList
一样的 System.arraycopy()
方法,而是采用 for循环
来调用 add()
方法进行一个一个添加的;为什么这么做呢?因为 ArrayDeque
和其他集合不一样,它里面是不能有 null
值的,而其他集合里面有的是可以传 null
的,所以这边采用 add()
一个一个的加, add()
方法如果传入的值为空的话,就会 报异常 ;(add()实际调用的是addLast(),下面再讲)
这个方法的意思是添加数据到尾部,下面图片方框中的位与算法是实现循环队列这个功能的 核心算法
还记得上面初始化时候,不管传入的是什么数值,最后出来的都是 (整数次)方。这个算法就是 当 &
右边为 时, &
左边的数为正整数时,不管有多大,最后的结果永远<= ;当 &
左边的数为0时,结果为0;当 &
左边的数为负数时,-1=
举一些例子:当 ,
方便理解,我画下上扩容的流程图,比如head在中间:
移除头部数据
删除的时候并没有像 ArrayList
一样移动数据,而只是移动了 head
指向的位置
这两个方法都是一样的,都是直接返回 head
指向的数据,区别就是一个会抛异常,一个不会
public E getFirst() { @SuppressWarnings("unchecked") E result = (E) elements[head]; if (result == null) throw new NoSuchElementException(); return result; } 复制代码
public E peekFirst() { // elements[head] is null if deque empty return (E) elements[head]; } 复制代码
这里还是用了上面讲了位与算法,算出 head
的值,然后插入数据
清空这个操作是从 head
指向的元素开始删除,直到 head
= tail
,清空完成;
这个获取队列的大小也是用了上面讲的位与算法,用尾部减去了头部,然后位与数组的长度-1。为什么要这么弄呢?直接向 ArrayList
和 LinkedList
一样定义个size不好嘛? 你不觉得这样更方便吗?少了一个变量,就少维护了一个变量,就少了一个安全隐患啊
public int size() { return (tail - head) & (elements.length - 1); } 复制代码
上面的方法基本上有 位与
这个算法的身影,可见这个是核心了;如果不了解位运算的话,可以看位运算这篇文章;
核心算法:
&
右边为 时, &
左边的数为正整数时,不管有多大,最后的结果永远<= ;当 &
左边的数为0时,结果为0;当 &
左边的数为负数时,-1= ArrayDeque
无参构造方法是直接初始化一个容量为16的空数组,而上篇ArrayList文章里,它无参构造方法是初始化了一个 空数组 ,在第一次添加数据的时候才进行扩容到10;
ArrayDeque
每次扩容为原来数组长度的 2倍
ArrayDeque
不能插入 null
值