Java ArrayDeque
字数: 0 字 时长: 0 分钟
1. ArrayDeque 概述
Java 中有一个叫做：
Stack的类，却没有一个叫做：
Queue的类，因为 Queue 本身是一个接口：
public interface Queue<E>
extends Collection<E> {
}当需要使用栈时，Java 已经不推荐继续使用 Stack，而是更推荐使用：
ArrayDeque也就是：
双端队列原因前面在 Stack 中已经提到过。
Stack 是一个比较早期的类，它继承自 Vector，核心操作中使用了：
synchronized来保证线程安全。
当我们本身不需要线程安全，例如单线程环境时，这些同步操作会带来额外开销。
所以，当需要使用栈时，可以优先考虑：
ArrayDeque1.1 ArrayDeque 作为栈
public static void main(
String[] args) {
// 声明一个双端队列
ArrayDeque<String> stack =
new ArrayDeque<>();
// 压入元素
stack.push(
"张无忌"
);
stack.push(
"周芷若"
);
stack.push(
"赵敏"
);
// 获取栈顶元素
String top =
stack.peek();
System.out.println(
"栈顶元素为："
+ top
);
// 弹出栈顶元素
String pop =
stack.pop();
System.out.println(
"弹出的元素为："
+ pop
);
// 修改栈顶元素
stack.pop();
stack.push(
"小明"
);
System.out.println(
"修改后的栈为："
+ stack
);
// 遍历并查找元素
Iterator<String> iterator =
stack.iterator();
int index =
-1;
String target =
"张无忌";
while (
iterator.hasNext()
) {
String element =
iterator.next();
index++;
if (
element.equals(
target
)
) {
break;
}
}
if (index == -1) {
System.out.println(
"元素 "
+ target
+ " 不存在于队列中"
);
} else {
System.out.println(
"元素 "
+ target
+ " 在队列中的位置为："
+ index
);
}
}输出：
栈顶元素为：赵敏
弹出的元素为：赵敏
修改后的栈为：[小明, 张无忌]
元素 张无忌 在队列中的位置为：1在上面的示例中：
push()
↓
向栈中压入元素
peek()
↓
获取栈顶元素
pop()
↓
弹出栈顶元素修改栈顶元素时，可以：
pop()
↓
删除原栈顶元素
↓
push()
↓
压入新的栈顶元素查找元素时，则通过：
Iterator进行遍历。
1.2 ArrayDeque 作为队列
ArrayDeque 实现了：
Deque而：
Deque又继承了：
QueueArrayDeque 的定义：
public class ArrayDeque<E>
extends AbstractCollection<E>
implements Deque<E>,
Cloneable,
Serializable {
}所以，当需要使用队列时，也可以使用：
ArrayDeque例如：
public static void main(
String[] args) {
ArrayDeque<String> queue =
new ArrayDeque<>();
// 添加元素
queue.offer(
"赵敏"
);
queue.offer(
"小昭"
);
queue.offer(
"周芷若"
);
// 获取队首元素
String front =
queue.peek();
System.out.println(
"队首元素为："
+ front
);
// 弹出队首元素
String poll =
queue.poll();
System.out.println(
"弹出的元素为："
+ poll
);
// 修改队列中的元素
queue.poll();
queue.offer(
"小明"
);
System.out.println(
"修改后的队列为："
+ queue
);
// 查找元素
Iterator<String> iterator =
queue.iterator();
int index =
0;
while (
iterator.hasNext()
) {
String element =
iterator.next();
if (
element.equals(
"周芷若"
)
) {
System.out.println(
"元素在队列中的位置为："
+ index
);
break;
}
index++;
}
}输出：
队首元素为：赵敏
弹出的元素为：赵敏
修改后的队列为：[周芷若, 小明]
元素在队列中的位置为：0在上面的示例中：
offer()
↓
向队列中添加元素
peek()
↓
获取队首元素
poll()
↓
删除并返回队首元素修改元素时：
poll()
↓
删除原来的元素
↓
offer()
↓
添加新的元素查找元素时，同样可以使用：
Iterator进行遍历。
1.3 LinkedList 作为队列
前面讲过，LinkedList 不只是一个：
List它还实现了：
Deque源码：
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>,
Deque<E>,
Cloneable,
Serializable {
}所以，当需要使用队列时，同样可以选择：
LinkedList例如：
public static void main(
String[] args) {
// 创建 LinkedList
LinkedList<String> queue =
new LinkedList<>();
// 添加元素
queue.offer(
"小昭"
);
queue.offer(
"赵敏"
);
queue.offer(
"周芷若"
);
System.out.println(
queue
);
// 删除元素
queue.poll();
System.out.println(
queue
);
// 修改元素
queue.poll();
queue.offer(
"张三丰"
);
System.out.println(
queue
);
// 根据下标查找
System.out.println(
queue.get(0)
);
System.out.println(
queue.contains(
"张无忌"
)
);
// 使用迭代器查找元素
Iterator<String> iterator =
queue.iterator();
while (
iterator.hasNext()
) {
String element =
iterator.next();
if (
element.equals(
"周芷若"
)
) {
System.out.println(
"找到了："
+ element
);
break;
}
}
}在使用 LinkedList 作为队列时：
offer()
↓
向队列尾部添加元素
poll()
↓
从队列头部删除元素也可以使用：
Iterator
poll()依次遍历元素。
2. 栈和队列
要理解栈和队列，首先需要理解：
DequeDeque 的意思是：
Double Ended Queue
双端队列它既可以作为：
栈使用，也可以作为：
队列使用。
2.1 Deque 和 Queue
Deque 与 Queue 对应的方法：
| Queue 方法 | Deque 方法 | 说明 |
|---|---|---|
add(e) | addLast(e) | 向队尾插入元素，失败时抛出异常 |
offer(e) | offerLast(e) | 向队尾插入元素，失败时返回 false |
remove() | removeFirst() | 获取并删除队首元素，失败时抛出异常 |
poll() | pollFirst() | 获取并删除队首元素，失败时返回 null |
element() | getFirst() | 获取但不删除队首元素，失败时抛出异常 |
peek() | peekFirst() | 获取但不删除队首元素，失败时返回 null |
2.2 Deque 和 Stack
Deque 与 Stack 对应的方法：
| Stack 方法 | Deque 方法 | 说明 |
|---|---|---|
push(e) | addFirst(e) | 向栈顶插入元素，失败时抛出异常 |
| 无 | offerFirst(e) | 向栈顶插入元素，失败时返回 false |
pop() | removeFirst() | 获取并删除栈顶元素，失败时抛出异常 |
| 无 | pollFirst() | 获取并删除栈顶元素，失败时返回 null |
peek() | getFirst() | 获取但不删除栈顶元素，失败时抛出异常 |
| 无 | peekFirst() | 获取但不删除栈顶元素，失败时返回 null |
上面两组一共定义了 Deque 常见的 12 个操作。
对于：
添加
删除
获取通常都有两套接口。
区别主要在于：
一套接口操作失败时抛出异常，另一套接口操作失败时返回特殊值，例如
false或null。
除非具体实现本身存在容量限制，否则大多数情况下添加操作并不会失败。
虽然 Deque 的接口不少，但本质上就是：
操作容器两端
├── 添加
├── 删除
└── 查看理解这一点以后，就比较容易掌握。
ArrayDeque 和 LinkedList 都是：
Deque的通用实现。
由于前面已经详细介绍过 LinkedList，这里主要继续分析：
ArrayDeque3. ArrayDeque 底层结构
从名字就能看出来：
ArrayDeque
↓
Array
↓
数组ArrayDeque 底层通过数组实现。
为了支持：
数组两端插入
数组两端删除这个数组需要按照：
循环数组
Circular Array的方式使用。
也就是说：
数组中的任何位置都有可能成为逻辑上的起点或者终点。
ArrayDeque：
非线程安全
Not Thread-Safe如果多个线程同时使用，需要手动进行同步。
另外：
ArrayDeque 不允许保存 null结构示意图：
其中：
head
↓
指向首端第一个有效元素
tail
↓
指向尾端下一个可以插入元素的空位因为使用的是循环数组，所以：
head 不一定等于 0
tail 也不一定始终大于 head4. 方法剖析
4.1 addFirst()
addFirst(E e) 的作用是：
在 Deque 首端插入元素也就是在：
head之前插入。
如果暂时不考虑：
空间不足
数组越界核心操作可以理解成：
elements[--head] =
e;示意图：
实际实现需要考虑两个问题：
- 空间是否足够。
- 下标是否越界。
例如：
head = 0继续执行：
addFirst()如果直接：
head - 1就会得到：
-1发生数组下标越界。
源码通过位运算解决：
public void addFirst(
E e) {
// 不允许 null
if (e == null) {
throw new NullPointerException();
}
// 处理循环数组下标
elements[
head =
(
head - 1
)
& (
elements.length - 1
)
] = e;
// 空间不足时扩容
if (head == tail) {
doubleCapacity();
}
}可以看到，空间问题是在插入以后解决的。
因为：
tail始终指向下一个可以插入元素的空位。
所以数组中至少会保留一个：
空位下标越界通过：
head =
(
head - 1
)
& (
elements.length - 1
);解决。
这段代码相当于利用：
取模实现循环下标。
因为：
elements.length是：
2 的幂所以：
elements.length - 1的二进制低位会全部是：
1和：
head - 1进行 & 运算以后，就可以实现类似取模的效果，同时处理：
head - 1 = -1的情况。
4.1.1 doubleCapacity()
当数组空间不足时，会调用：
doubleCapacity()进行扩容。
基本思路：
创建一个更大的数组
↓
容量扩大为原来的两倍
↓
复制原数组元素扩容过程：
因为 ArrayDeque 使用的是循环数组，所以复制会分成两部分：
第一次
↓
复制 head 右边的元素
第二次
↓
复制 head 左边的元素源码：
private void doubleCapacity() {
assert head == tail;
int p =
head;
int n =
elements.length;
// head 右边元素数量
int r =
n - p;
// 新容量扩大为原来的两倍
int newCapacity =
n << 1;
if (newCapacity < 0) {
throw new IllegalStateException(
"Sorry, deque too big"
);
}
Object[] newArray =
new Object[
newCapacity
];
// 复制 head 右侧元素
System.arraycopy(
elements,
p,
newArray,
0,
r
);
// 复制 head 左侧元素
System.arraycopy(
elements,
0,
newArray,
r,
p
);
elements =
(E[]) newArray;
head =
0;
tail =
n;
}首先：
head
tail处于需要扩容的状态。
然后：
int r =
n - p;计算：
head 右侧元素数量新的容量：
int newCapacity =
n << 1;也就是：
原容量 × 2然后创建：
Object[] newArray第一次：
System.arraycopy()复制：
head 右侧部分第二次复制：
head 左侧部分最终：
elements
↓
指向新数组
head
↓
0
tail
↓
原数组长度 n原来的 elements 数组失去引用以后，就可以由垃圾回收器进行回收。
4.2 addLast()
addLast(E e) 的作用：
在 Deque 尾端插入元素也就是：
tail指向的位置。
由于 tail 始终指向：
下一个可以插入的空位所以核心操作：
elements[tail] =
e;插入完成以后：
tail
↓
向后移动如果空间已经耗尽：
doubleCapacity()进行扩容。
源码：
public void addLast(
E e) {
// 不允许 null
if (e == null) {
throw new NullPointerException();
}
// 写入 tail
elements[tail] =
e;
// tail 向后移动
if (
(
tail =
(
tail + 1
)
& (
elements.length - 1
)
) == head
) {
doubleCapacity();
}
}下标循环处理方式与：
addFirst()相同。
4.3 pollFirst()
pollFirst() 的作用：
删除并返回 Deque 首端元素也就是：
head位置上的元素。
如果容器不为空：
返回 elements[head]并让：
head向后移动。
由于：
ArrayDeque 不允许保存 null所以：
elements[head] == null就意味着：
Deque 为空源码：
public E pollFirst() {
E result =
elements[head];
// null 表示队列为空
if (result == null) {
return null;
}
// 清除原来的引用
elements[head] =
null;
// head 向后移动
head =
(
head + 1
)
& (
elements.length - 1
);
return result;
}整个过程：
读取 head 元素
↓
为空则返回 null
↓
原位置置为 null
↓
head 向后移动
↓
返回原元素4.4 pollLast()
pollLast() 的作用：
删除并返回 Deque 尾端元素真正的最后一个元素位于：
tail 的前一个位置所以首先计算：
int t =
(
tail - 1
)
& (
elements.length - 1
);源码：
public E pollLast() {
// tail 前一个位置才是最后一个元素
int t =
(
tail - 1
)
& (
elements.length - 1
);
E result =
elements[t];
// null 表示队列为空
if (result == null) {
return null;
}
// 清除引用
elements[t] =
null;
tail =
t;
return result;
}整个过程：
找到 tail 前一个位置
↓
读取元素
↓
为空则返回 null
↓
原位置置为 null
↓
tail 前移
↓
返回元素4.5 peekFirst()
peekFirst() 的作用：
返回但不删除 Deque 首端元素也就是：
head位置上的元素。
源码：
public E peekFirst() {
return elements[head];
}如果 Deque 为空：
elements[head]
↓
null所以直接返回 null。
4.6 peekLast()
peekLast() 的作用：
返回但不删除 Deque 尾端元素也就是：
tail 前一个位置源码：
public E peekLast() {
return elements[
(
tail - 1
)
& (
elements.length - 1
)
];
}5. 小结
当需要实现：
FIFO
先进先出或者：
LIFO
后进先出的数据结构时，都可以考虑使用：
ArrayDeque一些常见场景：
- 管理任务队列：使用 ArrayDeque 保存任务元素，从一端添加任务，再从另一端取出任务，可以按照先进先出的顺序进行处理。
- 实现栈：ArrayDeque 支持
push()、pop()、peek()等操作，可以用于后进先出的场景。 - 实现缓存：当缓存数量超过限制时，可以从队列一端删除旧数据，从另一端添加新数据。
- 实现事件处理器：可以从队列头部取出事件进行处理，再从尾部添加新的事件。
ArrayDeque 是 Java 标准库中的一种：
双端队列底层基于：
数组实现。
与 LinkedList 相比：
ArrayDeque
↓
底层数组
LinkedList
↓
底层链表数组使用连续的存储空间保存元素引用，可以更好地利用 CPU 缓存。
而 LinkedList 由多个节点组成，每一个节点都需要保存：
数据
前后节点引用在使用过程中也会涉及节点对象的创建。
现代 CPU 对数据局部性比较敏感，如果需要访问的数据在内存中比较连续，就可以更好地利用 CPU Cache。
当然，ArrayDeque 同样需要考虑：
数组扩容带来的成本。
当元素数量达到当前数组容量限制时：
创建新数组
↓
容量扩大
↓
复制旧数组数据数组复制的时间复杂度：
O(n)不过，通过扩容策略可以减少数组频繁复制带来的消耗。
ArrayDeque 不仅支持普通队列操作：
添加元素
删除元素
获取队首元素
获取队尾元素同时也支持栈操作：
push()
pop()
peek()因此：
ArrayDeque 既可以作为双端队列使用，也可以作为普通队列或者栈使用。