Deque 接口表示一个双端队列（Double Ended Queue），允许在队列的首尾两端操作，所以既能实现队列行为，也能实现栈行为。
Deque常用的两种实现ArrayDeque和LinkedList，这篇主要介绍下Deque的常用操作，并重点看下ArrayDeque的实现逻辑。
1、接口API
1.1、Queue接口
Queue 的 API 可以分为 2 类，区别在于方法的拒绝策略上：
- 抛异常：
- 向空队列取数据，会抛出 NoSuchElementException 异常；
- 向容量满的队列加数据，会抛出 IllegalStateException 异常。
- 返回特殊值：
- 向空队列取数据，会返回 null；
- 向容量满的队列加数据，会返回 false。
| 拒绝策略 | 抛异常 | 返回特殊值 |
|---|---|---|
| 入队（队尾） | add(e) | offer(e) |
| 出队（队头） | remove() | poll() |
| 观察（队头） | element() | peek() |
1.2、Deque接口（继承于Queue接口）
Java 没有提供标准的栈接口，而是放在 Deque 接口中：
| 拒绝策略 | 抛异常 | 等价于 |
|---|---|---|
| 入栈 | push(e) | addFirst(e) |
| 出栈 | pop() | removeFirst() |
| 观察（栈顶） | peek() | peekFirst() |
除了标准的队列和栈行为，Deque 接口还提供了 12 个在两端操作的方法：
| 拒绝策略 | 抛异常 | 返回值 |
|---|---|---|
| 增加 | addFirst(e)/ addLast(e) | offerFirst(e)/ offerLast(e) |
| 删除 | removeFirst()/ removeLast() | pollFirst()/ pollLast() |
| 观察 | getFirst()/ getLast() | peekFirst()/ peekLast() |
public void addFirst(E e) {
if (e == null)
throw new NullPointerException();
elements[head = (head - 1) & (elements.length - 1)] = e;
if (head == tail)
doubleCapacity();
}
public boolean offerFirst(E e) {
addFirst(e);
return true;
}
从源码也可以看出，offerFirst(e) 只是调用了 addFirst(e)，然后返回了一个true，失败时还是会抛异常的。
2、ArrayDeque的实现
2.1、ArrayQueue的特点
- 1、ArrayDeque 是基于动态数组实现的 Deque 双端队列，内部封装了扩容和数据搬运的逻辑；
- 2、ArrayDeque 的数组容量保证是 2 的整数幂；
- 3、ArrayDeque 不是线程安全的；
- 4、ArrayDeque 不支持 null 元素；
- 5、ArrayDeque 虽然入栈和入队有可能会触发扩容，但从均摊分析上看依然是 O(1) 时间复杂度；
2.2、ArrayDeque和LinkedList的区别
-
1、数据结构： 在数据结构上，ArrayDeque 和 LinkedList 都实现了 Deque 双端队列接口。但 ArrayDeque 没有实现了 List 列表接口，所以不具备根据索引位置操作的行为；
-
2、线程安全： ArrayDeque 和 LinkedList 都不考虑线程同步，不保证线程安全；
-
3、底层实现： 在底层实现上，ArrayDeque 是基于动态数组的，而 LinkedList 是基于双向链表的。
-
在遍历速度上： ArrayDeque 是一块连续内存空间，基于局部性原理能够更好地命中 CPU 缓存行，而 LinkedList 是离散的内存空间对缓存行不友好；
-
在操作速度上： ArrayDeque 和 LinkedList 的栈和队列行为都是 O(1) 时间复杂度，ArrayDeque 的入栈和入队有可能会触发扩容，但从均摊分析上看依然是 O(1) 时间复杂度；
-
额外内存消耗上： ArrayDeque 在数组的头指针和尾指针外部有闲置空间，而 LinkedList 在节点上增加了前驱和后继指针。
-
3、如何使用数组实现栈和队列
我们知道栈和队列都是 “操作受限” 的线性表：栈是 LIFO，限制在表的一端入栈和出栈。而队列是 FIFO，限制在表的一端入队，在另一端出队。栈和队列既可以用数组实现，也可以用链表实现：
- 数组：用数组实现时叫作顺序栈和顺序队列；
- 链表：用链表实现时叫作链式栈和链式队列。
3.1、ArrayList相对于LinkedList的局限性
LinkedList既作为 List 的链式表，又作为 Queue 的链式队列，又作为 “Stack” 的链式栈，功能很全面。相较之下，ArrayList 却只作为实现了 List 的顺序表，为什么呢？
这是因为在数组上同时实现 List 和 Queue 时，无法平衡这两个行为的性能矛盾。具体来说：ArrayList 不允许底层数据有空洞，所有的有效数据都会 “压缩” 到底层数组的首部。所以，使用 ArrayList 开发栈的结构或许合适，可以在数组的尾部操作数据。但使用 ArrayList 开发队列就不合适，因为在数组的首部入队或出队需要搬运数据。
3.2、使用数组实现栈结构
使用数组实现栈相对容易，因为栈结构的操作被限制在数组的一端，所以我们可以选择数组的尾部作为栈顶，并且使用一个 top 指针记录栈顶位置：
- 栈空： top == 0；
- 栈满： top == n；
- 入栈： 将数据添加到栈顶位置，均摊时间复杂度是 O(1)；
- 出栈： 将栈顶位置移除，时间复杂度是 O(1)；
对于出栈而言，时间复杂度总是 O(1)，但是对于入栈而言，却不一定。因为当数组的空间不足（top == n）时，就需要扩容和搬运数据来容纳新的数据。此时，时间复杂度就从 O(1) 退化到 O(n)。
对于这种大部分操作时间复杂度很低，只有个别情况下时间复杂度会退化，而且这些操作之间存在很强烈的顺序关系的情况，就很适合用 “均摊时间复杂度分析” 了：
假设我们的扩容策略是将数组扩大到旧数组的 2 倍，用均摊分析法：
- 1、对于一个大小为 K 的空数组，在前 K - 1 次入栈操作中，时间复杂度都是 O(1)；
- 2、在第 K 次入栈中，由于数组容量不足，所以我们将数组扩大为 2K，并且搬运 K 个数据，时间复杂度退化为 O(K)；
- 3、对于一个大小为 2K 的数组，在接下来的 K - 1 次入栈操作中，时间复杂度都是 O(1)；
- 4、在第 2K 次入栈中，由于数组容量不足，所以我们将数组扩大为 4K，并且搬运 2K 个数据，时间复杂度再次退化为 O(K)；
- 5、依此类推。
可以看到，在每次搬运 K 个次数后，随后的 K - 1 次入栈操作就只是简单的 O(1) 操作，K 次入栈操作涉及到 K 个数据搬运和 K 次赋值操作。那我们从整体看，如果把复杂度较高的 1 次入栈操作的耗时，均摊到其他复杂度较低的操作上，就等于说 1 次入栈操作只需要搬运 1 个数据和 1 次赋值操作，所以入栈的均摊时间复杂度就是 O(1)。
3.3、使用数组实现队列结构
使用数组实现队列相对复杂，我们需要一个队头指针和一个队尾指针：
- 队空： head == tail；
- 队满： tail == n（并不是真的满，只是无法填充新数据）；
- 入队： 将数据添加到队尾位置，均摊时间复杂度是 O(1)；
- 出队： 将队头位置移除，时间复杂度是 O(1)。
对于出队而言，时间复杂度总是 O(1)。对于入队而言，当 tail == n 时，就需要扩容和搬运数据来容纳新的数据，我们用均摊分析法得出均摊时间复杂度依然是 O(1)，就不重复了。
但是我们发现，栈的 top == n 表示栈空间不足，扩容没有问题，而队列的 tail == n 却不一定表示队列空间不足。因为入队和出队发生在不同方向，有可能出现 tail == n 但队头依然有非常多剩余空间的情况。此时，扩容显得没有必要。
那么，怎么避免没有必要的扩容和数据搬移呢？—— 循环数组。
我们在逻辑上将数组的首尾相连，当 tail == n 时，如果数组头部还有空闲位置，我们就把 tail 指针调整到数组头部，在数组头部添加数据。我们下面要分析的 ArrayDeque 数据结构，就是采用了循环数组的实现。
使用循环数组后，队列空和队列满的判断条件会发生变化：
- 队列空： head == tail；
- 队列满： (tail + 1)%size == head，如果 size 是 2 的整数幂，还可以用位运算判断：(tail + 1) & (size - 1) == head。
理解了使用数组实现栈和队列的思路后，下面再来分析 ArrayDeque 的实现原理，就显得游刃有余了。
4、ArrayDeque源码分析
来分析下ArrayDeque主要流程的源码。
4.1、ArrayDeque的属性
- ArrayDeque 底层是一个 Object 数组；
- ArrayDeque 用
head和tail指针指向数组的 “队头位置” 和 “队尾位置”，需要注意 tail 队尾指针实际上是指向队尾最后一个有效元素的下一位。
ArrayDeque 的属性很好理解的，然后我先抛出几个问题：