目录
1. ArrayDeque
Deque
是双端队列,既可以从队列头部增删元素,也可以从队列尾部增删元素。
ArrayDeque
是用数组实现的双端队列。
因为数组元素的位置是固定的,所以进行
头插
时,一般情况下常人思维就是把队列内已有的元素统一向后移动,给队首腾出地方。
但是这种操作耗时严重,所以本文的主角
ArrayDeque
就体现出了它的设计精妙之处。
public class ArrayDeque {
Object[] elements; // 默认长度16,后续扩容总是2的整数次幂(重要)
int head; // 指向队首元素索引,初始值0
int tail; // 指向队尾元素索引,初始值0
}
2. 新增
ArrayDeque
初始状态如下
2.1 只有头插
ArrayDeque
的头插不是直接插到头上,它做了这个操作
elements[head = (head - 1) & (elements.length - 1)] = e
分解一下
int index = (head - 1) & (elements.length - 1); // -1 & 15 = 15
head = index; //head = 15,tail = 0
elements[index] = e;
头插头插嘛,就得在当前队首前面插一个元素,但是直接
head - 1
会出问题,索引会变成负数,所以经过跟
elements.length
取余数后,得到的值就变成了正数,而且还是数组最后一个索引。
这么搞的好处是,避免了每次头插都将已有元素向后移动,时间花销变成常数级!
连续头插13次,会发现每次头插完毕
head
的值的变化是这样的
head = 15, 14, 13, ……, 3
直到
head
撞上
tail
,然后就该扩容了,后面说如何扩容。
2.2 只有尾插
elements[tail] = e;
tail = (tail + 1) & (elements.length - 1); //防止索引越界
连续尾插3次,会发现每次尾插完毕
tail
的值的变化是这样的
tail = 0, 1, 2, 3
直到
tail
撞上
head
,然后扩容。
2.3 头尾交插
根据上面两种插入元素的方式,即使是头尾交替插入元素也不会碰撞。
下图中
绿色
的表示头插元素,
黄色
的表示尾插元素
头 = 1
尾 = 2
头 = 3
尾 = 4
头 = 5
尾 = 6
头 = 7
尾 = 8
最后双端队列的
正向
遍历顺序是
7 5 3 1 2 4 6 8
3. 扩容
ArrayDeque
每次双倍扩容。
ArrayDeque
内部数组默认容量是16,为了方便演示,下面将默认容量修改为8,当数组被塞满后,扩容到16。
4. 删除
理解了
头插
和
尾插
原理后,删除操作只需
+ 变 -
- 变 +
4.1 删头
头插
是先对
head
做运算,然后再添加;添加完毕后
head
就指向首元素
删头
是先删
head
指向元素,然后把
head
指针向后移
// 头插
elements[head = (head - 1) & (elements.length - 1)] = e;
// 删头
E e = elements[head]; // 取出做备份
if (e == null) return null; // 证明队列已空 head == tail == null
elements[head] = null; // 释放槽位,避免内存泄漏
head = (head + 1) & (elements.length - 1); // 向后移动 head 指针
return e;
4.2 删尾
尾插
是先添加,后对
tail
做运算;添加完毕后
tail
指向下一个空闲位置
删尾
是先把
tail
指针向前移,然后删除
tail
指向元素
// 尾插
elements[tail] = e;
tail = (tail + 1) & (elements.length - 1);
// 删尾
int t = (tail - 1) & (elements.length - 1); // 向前移动 tail 指针
E e = elements[t]; // 取出做备份
if (e == null) return null; // 证明队列已空 tail == head == null
elements[t] = null; // 释放槽位,避免内存泄漏
tail = t;
return e;
5. 遍历
既然是双端队列,那必然有两种遍历方式:正向遍历(head > tail)和逆向遍历(tail > head)
ArrayDeque
没有实现
java.util.List
接口,所以不能按索引遍历,只能通过迭代器遍历
5.1 正向遍历
ArrayDeque
为了屏蔽内部实现细节,提供了
java.util.Iterator
的内部实现类
DeqIterator
,供外部正向遍历(head > tail)
正如你所想的一样,额外定义一个变量
cursor
最初指向
head
hasNext()
判断
cursor != tail
时才能
next()
next()
把
cursor
指向的元素返回给你,然后
cursor = (cursor + 1) & (elements.length - 1)
5.2 逆向遍历
ArrayDeque
提供了另一个内部类
DescendingIterator
,它同样实现了
java.util.Iterator
,用于逆向遍历(tail > head)
额外定义一个变量
cursor
最初指向
tail
hasNext()
判断
cursor != head
时才能
next()
next()
先
cursor = (cursor - 1) & (elements.length - 1)
,然后把
cursor
指向的元素返回给你
5.3 遍历删除
最后再补充一点。
迭代器遍历很简单,那如果想在迭代过程中删除元素怎么办呢?
废话,当然是使用 iterator.remove() 了
数组毕竟是数组,如果想删除中间部分的元素,而非头、尾元素,依然避免不了移动元素的操作
ArrayDeque
为了尽量减少移动元素的个数,在
delete()
方法内写了点
人类友好型
代码,不过我并不想分享出来,
一是因为它虽然简短,但是没有完全实现任何情况下都能达到它这么做的初衷;
二是因为我相信有一部分人看过这个方法之后,也会有像我写这篇博客时的心情。
如果让我设计,我也会考虑到移动元素过多影响效率的问题,虽然我写不出官方代码,但是思路都是差不多的~~。
5.3.1 一边倒
只进行
头插 / 尾插
,使
head = 0 / tail = 0
例如下面这种情况,想删除
4
,正常人想的肯定都是把
3 2 1
往前挪,然后
elements[tail = elements.length - 1] = null
如果你也是这么想的,那纯属雷同。
如果想删除
10
,就把
13 12 11
往后挪,然后
elements[head] = null; head++;
5.3.2 两边散
最麻烦的就是这样的,想删除
5
,就得判断
min(index - head, elements.length - index + tail)
说白了就是判断
index
离哪个指针更近,就移动哪边的元素
如果不幸的离
tail
更近,最多需要复制两次数组 —— 先把
[index ~ elements.length-1]
补齐,再折腾
[0 ~ tail-1]
画图不易,还请自行脑部,感谢浏览本文!
Over