编辑“︁Java ArrayDeque”︁（章节）

= Java ArrayDeque =

`ArrayDeque`是Java集合框架中一个基于数组实现的双端队列（Double-Ended Queue），位于`java.util`包中。它同时实现了`Deque`和`Queue`接口，支持从队列两端高效地插入和删除元素。

== 核心特性 ==
* '''动态数组'''：底层采用可扩容的循环数组实现
* '''无容量限制'''：自动扩容（默认初始容量为16）
* '''非线程安全'''：多线程环境下需要外部同步
* '''性能优势'''：
** 头尾操作时间复杂度为O(1)
** 比`LinkedList`更节省内存（无节点开销）
** 随机访问性能优于`LinkedList`（O(n) vs O(n)但常数项更小）

== 类继承关系 ==
<mermaid>
classDiagram
    Collection <|-- Queue
    Queue <|-- Deque
    Deque <|-- ArrayDeque
    class Collection{
        <<interface>>
    }
    class Queue{
        <<interface>>
    }
    class Deque{
        <<interface>>
    }
    class ArrayDeque{
        +ArrayDeque()
        +ArrayDeque(int numElements)
    }
</mermaid>

== 基本操作 ==
=== 初始化 ===
<syntaxhighlight lang="java">
// 默认初始容量16
ArrayDeque<String> deque1 = new ArrayDeque<>();

// 指定初始容量
ArrayDeque<Integer> deque2 = new ArrayDeque<>(32);

// 从其他集合初始化
List<String> list = Arrays.asList("A", "B", "C");
ArrayDeque<String> deque3 = new ArrayDeque<>(list);
</syntaxhighlight>

=== 常用方法 ===
{| class="wikitable"
|+ 核心操作方法对比
! 操作类型 !! 队列首部 !! 队列尾部 !! 可能抛出异常 !! 返回特殊值
|-
! 插入
| <code>addFirst(e)</code> | <code>addLast(e)</code> | 队列满时抛出<code>IllegalStateException</code> | <code>offerFirst(e)</code>/<code>offerLast(e)</code>
|-
! 移除
| <code>removeFirst()</code> | <code>removeLast()</code> | 队列空时抛出<code>NoSuchElementException</code> | <code>pollFirst()</code>/<code>pollLast()</code>
|-
! 检查
| <code>getFirst()</code> | <code>getLast()</code> | 队列空时抛出<code>NoSuchElementException</code> | <code>peekFirst()</code>/<code>peekLast()</code>
|}

== 代码示例 ==
=== 基础用法 ===
<syntaxhighlight lang="java">
ArrayDeque<String> deque = new ArrayDeque<>();

// 添加元素
deque.addLast("Apple");
deque.offerFirst("Banana");  // 推荐使用offer系列方法
deque.addLast("Cherry");

System.out.println(deque);  // 输出: [Banana, Apple, Cherry]

// 访问元素
String first = deque.peekFirst();  // "Banana"
String last = deque.getLast();     // "Cherry"

// 移除元素
String removed1 = deque.pollFirst();  // 移除并返回"Banana"
String removed2 = deque.removeLast(); // 移除并返回"Cherry"

System.out.println(deque);  // 输出: [Apple]
</syntaxhighlight>

=== 循环数组实现原理 ===
`ArrayDeque`使用循环数组（circular array）技术实现高效操作：

<mermaid>
graph LR
    A[头指针: head] --> B[数组索引0]
    C[尾指针: tail] --> D[数组索引2]
    E[null] --> F[元素A]
    G[元素B] --> H[元素C]
    I[null] --> J[...]
</mermaid>

当数组空间不足时，扩容机制如下：
1. 当前容量加倍
2. 重新排列元素：<math>newCapacity = oldCapacity \times 2</math>
3. 复制元素到新数组并调整head/tail指针

== 高级应用 ==
=== 实现栈结构 ===
`syntaxhighlight lang="java">
// 比Stack类更高效的栈实现
ArrayDeque<Integer> stack = new ArrayDeque<>();

// 压栈
stack.push(1);
stack.push(2);
stack.push(3);

// 弹栈
while (!stack.isEmpty()) {
    System.out.println(stack.pop());  // 输出: 3, 2, 1
}
</syntaxhighlight>

=== 滑动窗口最大值 ===
解决Leetcode 239题的经典算法：
<syntaxhighlight lang="java">
public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    
    int n = nums.length;
    int[] result = new int[n - k + 1];
    ArrayDeque<Integer> deque = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // 移除超出窗口范围的索引
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }
        
        // 移除小于当前元素的索引
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }
        
        deque.offerLast(i);
        
        // 记录当前窗口最大值
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}
</syntaxhighlight>

== 性能比较 ==
{| class="wikitable"
|+ 不同实现的复杂度比较
! 操作 !! ArrayDeque !! LinkedList
|-
| 添加/删除(首尾) || O(1) || O(1)
|-
| 随机访问 || O(n) || O(n)
|-
| 内存占用 || 更优（连续内存） || 较差（节点开销）
|-
| 迭代性能 || 更快（缓存友好） || 较慢
|}

== 最佳实践 ==
1. '''优先选择`ArrayDeque`而非`LinkedList`'''：当只需要队列/栈功能时
2. '''预估初始容量'''：避免频繁扩容
3. '''多线程环境使用`ConcurrentLinkedDeque`'''
4. '''栈实现替代方案'''：比`Stack`类更高效

{{Warning|不要在多线程环境中直接使用`ArrayDeque`，必须通过`Collections.synchronizedDeque()`进行包装或使用外部同步机制。}}

== 常见问题 ==
=== 何时选择ArrayDeque vs LinkedList ===
* 需要频繁随机访问 → 考虑`ArrayList`
* 只需要队列/栈操作 → 优先`ArrayDeque`
* 需要频繁在中间插入/删除 → 选择`LinkedList`
* 内存敏感场景 → 优先`ArrayDeque`

=== 扩容机制详解 ===
扩容时：
1. 计算新容量：<math>newCapacity = n + (n \lt 64 ? n + 2 : n \gt\gt 1)</math>
2. 验证容量不超过<code>MAX_ARRAY_SIZE</code>（<math>2^{31}-1-8</math>）
3. 创建新数组并复制元素

== 总结 ==
`ArrayDeque`是Java集合框架中高效的双端队列实现：
* 适合作为栈和队列使用
* 比`LinkedList`更节省内存
* 头尾操作性能优异
* 注意非线程安全特性

{{Exercise|尝试使用`ArrayDeque`实现一个浏览器历史记录功能，支持前进(forward)和后退(back)操作}}

[[Category:编程语言]]
[[Category:Java]]
[[Category:Java集合框架]]