Java双端队列 ArrayDeque(全彩图,看完都想自己实现一遍)

  • Post author:
  • Post category:java




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

头插13次

直到

head

撞上

tail

,然后就该扩容了,后面说如何扩容。



2.2 只有尾插

elements[tail] = e;
tail = (tail + 1) & (elements.length - 1); //防止索引越界

连续尾插3次,会发现每次尾插完毕

tail

的值的变化是这样的

tail = 0, 1, 2, 3

尾插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



版权声明:本文为qq_44676331原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。