---
url: https://www.chenlj.top/md/java-base/collections/ArrayDeque.md
---
# ArrayDeque 源码解析

## 简介

`ArrayDeque` 是 `Deque`（双端队列）的**基于数组**的实现，底层是一个**循环数组（环形缓冲区）**，可同时作为栈和队列使用。

* 不是线程安全的；并发双端队列请用 `ConcurrentLinkedDeque` 或 `LinkedBlockingDeque`。
* **不允许 `null` 元素**（否则无法区分「空槽」与「元素」）。
* 作为栈比 `Stack` 快，作为队列比 `LinkedList` 更省内存、性能更好（连续数组缓存友好）。
* 容量按需**翻倍**扩缩，且容量始终是 **2 的幂**，以便用位运算 `(i & (length-1))` 代替取模。

> 官方推荐：需要栈时用 `ArrayDeque` 替代遗留的 `Stack`；需要队列时优先 `ArrayDeque` 而非 `LinkedList`。

## 底层数据结构分析

`ArrayDeque` 用 `elements` 数组存储元素，`head` 指向队首，`tail` 指向队尾下一个可写位置；两者在数组上循环移动，当 `head == tail` 时表示「满」，触发扩容。

```java
transient Object[] elements; // 循环数组，容量恒为 2 的幂
transient int head;          // 队首下标
transient int tail;          // 队尾下一个可写位置的下标
```

因为是 2 的幂，下标计算用位与代替取模，效率更高：

```java
// 在 head 前插入：head 减 1 后对长度取模（位运算）
elements[head = (head - 1) & (elements.length - 1)] = e;
```

## 核心成员变量

```java
transient Object[] elements; // 循环数组
transient int head;          // 队首指针
transient int tail;          // 队尾指针（下一个写入位置）
```

## 源码分析

### 写入：addFirst / addLast

```java
public void addFirst(E e) {
    if (e == null) throw new NullPointerException(); // 不允许 null
    // head 前移一位（循环），写入
    elements[head = (head - 1) & (elements.length - 1)] = e;
    if (head == tail)        // 满则扩容为 2 倍
        doubleCapacity();
}

public void addLast(E e) {
    if (e == null) throw new NullPointerException();
    elements[tail] = e;      // 在 tail 处写入
    if ((tail = (tail + 1) & (elements.length - 1)) == head)
        doubleCapacity();    // 满则扩容
}
```

### 读取：pollFirst / pollLast

```java
public E pollFirst() {
    int h = head;
    E result = (E) elements[h];
    if (result == null) return null; // 空队列
    elements[h] = null;              // 取出后置空（避免内存泄漏）
    head = (h + 1) & (elements.length - 1); // head 后移
    return result;
}

public E pollLast() {
    int t = (tail - 1) & (elements.length - 1);
    E result = (E) elements[t];
    if (result == null) return null;
    elements[t] = null;
    tail = t;                 // tail 前移
    return result;
}
```

### 扩容：doubleCapacity

```java
private void doubleCapacity() {
    assert head == tail;
    int p = head;
    int n = elements.length;
    int r = n - p;            // head 右侧元素个数
    int newCapacity = n << 1; // 容量翻倍（仍保持 2 的幂）
    Object[] a = new Object[newCapacity];
    // 把循环数组「拉直」复制到新数组前半部分，再接上后半部分
    System.arraycopy(elements, p, a, 0, r);
    System.arraycopy(elements, 0, a, r, p);
    elements = a;
    head = 0; tail = n;      // 重置为 head=0
}
```

## 与 LinkedList / Stack 的对比

| 维度 | LinkedList | Stack（遗留） | ArrayDeque |
| --- | --- | --- | --- |
| 结构 | 双向链表 | 数组（Vector 子类） | 循环数组 |
| 线程安全 | 否 | 是（方法级锁，慢） | 否 |
| 用作队列 | 可以 | 不推荐 | **推荐** |
| 用作栈 | 可以 | 可用但慢 | **推荐** |
| 允许 null | 允许 | 允许 | 否 |

## 经典 Demo

```java
import java.util.ArrayDeque;

public class ArrayDequeDemo {
    public static void main(String[] args) {
        ArrayDeque<String> deque = new ArrayDeque<>();
        deque.addLast("b"); deque.addFirst("a"); // 双端插入
        System.out.println(deque);      // [a, b]
        deque.push("x");                // 作为栈：入栈
        System.out.println(deque.pop()); // x 出栈
        System.out.println(deque.poll()); // a 作为队列：出队
    }
}
```