---
title: "01-ArrayDeque"
created: 2025-12-02
tags:
  - Java
---
# ArrayDeque

> [!note] 定位说明
> Queue 系列第 1 篇详篇。**官方推荐的栈/队列实现**：循环数组，头尾操作均摊 O(1)，比 LinkedList 快（无节点分配、内存连续）。本篇含循环数组的扩容与下标回绕机制。

## ArrayDeque：高性能双端队列

### 一、基本概念

ArrayDeque 是 Java 提供的一种基于动态数组实现的双端队列（Deque），支持高效的栈（LIFO）与队列（FIFO）操作，是 `Deque` 接口的一个重要实现类。

```java
public class ArrayDeque<E> extends AbstractCollection<E>

        implements Deque<E>, Cloneable, Serializable
```

它具备以下特点：

| 特性 | 说明 |
| --- | --- |
| 底层结构 | 循环数组（动态扩容） |
| 支持双端操作 | 支持从头尾插入和删除 |
| 非线程安全 | 多线程下需手动同步 |
| 不允许 null 元素 | 防止和空返回值歧义 |
| 相比 LinkedList 更高效 | 访问局部性更好，GC 压力更小，操作更快 |

### 二、底层结构与数据模型

ArrayDeque 使用一个循环数组 `elements[]` 来存储数据，并用两个指针标记头尾：

- `head`: 指向队首元素位置
- `tail`: 指向下一个插入队尾的位置

数组逻辑结构示意：

```
    tail

     ↓

[ _ _ B C D _ _ A ]

         ↑

       head
```

插入或删除时通过环形偏移计算位置，从而实现 O(1) 的效率。

### 三、添加元素 —— offerFirst / offerLast

```java
public void addFirst(E e) {

    if (e == null) throw new NullPointerException();

    elements[head = (head - 1) & (elements.length - 1)] = e;

    if (head == tail) resize();

}
```

```java
public void addLast(E e) {

    if (e == null) throw new NullPointerException();

    elements[tail] = e;

    tail = (tail + 1) & (elements.length - 1);

    if (tail == head) resize();

}
```

说明：

- 采用位运算 `(index ± 1) & (length - 1)` 代替取模 `%`，更高效（前提是数组长度为
  2 的幂）
- 判断队满：插入后 `head == tail`，说明已满，触发扩容
- 插入前不允许为 null，防止与 `poll()` 返回 null 混淆

### 四、删除元素 —— pollFirst / pollLast

```java
public E pollFirst() {

    int h = head;

    E result = elements[h];

    if (result == null) return null;

    elements[h] = null; // 清除引用，便于 GC

    head = (h + 1) & (elements.length - 1);

    return result;

}
```

```java
public E pollLast() {

    int t = (tail - 1) & (elements.length - 1);

    E result = elements[t];

    if (result == null) return null;

    elements[t] = null;

    tail = t;

    return result;

}
```

说明：

- 删除后指针推进，释放数组槽位，避免内存泄漏
- 仍采用环形偏移保证索引安全

### 五、扩容机制 —— resize()

扩容触发时，ArrayDeque 会将旧数据从 `head` 开始顺序复制到新数组中：

```java
private void resize() {

    int oldCapacity = elements.length;

    int newCapacity = oldCapacity << 1; // 扩容为原来的2倍

    Object[] newArray = new Object[newCapacity];

    int r = oldCapacity - head; // 从head到数组末尾的元素个数

    System.arraycopy(elements, head, newArray, 0, r);

    System.arraycopy(elements, 0, newArray, r, head);

    elements = newArray;

    head = 0;

    tail = oldCapacity;

}
```

核心要点：

- 扩容为原数组的 2 倍（比 ArrayList 的 1.5 倍更保守）
- 采用双段拷贝的方式解决循环结构问题
- 拷贝代价较大，建议合理初始化容量

### 六、典型应用场景

| 场景 | 示例 |
| --- | --- |
| 栈（LIFO） | `push()` / `pop()` |
| 队列（FIFO） | `offerLast()` / `pollFirst()` |
| 双端队列 | 支持头尾任意插入删除 |
| 缓存/滑动窗口 | 固定容量 + 头部淘汰策略实现 |

### 七、和 LinkedList 的对比

| 维度 | ArrayDeque | LinkedList |
| --- | --- | --- |
| 底层结构 | 循环数组 | 双向链表 |
| 头尾插入删除效率 | O(1) | O(1) |
| 中间插入删除 | 不支持 | O(n) |
| 内存占用 | 紧凑（数组） | 高（每个节点有两个引用） |
| 是否支持 null | ❌（抛出异常） | ✅ |
| 线程安全 | ❌ | ❌ |

推荐：一般建议使用 ArrayDeque 替代 LinkedList 作为栈或队列的实现。

### 八、示例代码

```java
Deque<String> deque = new ArrayDeque<>();

// 队列用法

deque.offerLast("a");

deque.offerLast("b");

System.out.println(deque.pollFirst()); // 输出 a

// 栈用法

deque.push("x");

deque.push("y");

System.out.println(deque.pop()); // 输出 y
```

### 九、注意事项总结

- 不允许存储 null 元素
- 非线程安全，需外部加锁或使用并发容器（如 ConcurrentLinkedDeque）
- 不支持元素随机访问（无索引）
- 插入删除性能优越，推荐作为双端队列使用
---
⬅️ [[00-Queue和Deque总览|00-Queue和Deque总览]] 🏠 [[00-Java|00-Java]] ➡️ [[02-PriorityQueue|PriorityQueue]]