Java ArrayDeque[编辑 | 编辑源代码]

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

核心特性[编辑 | 编辑源代码]

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

类继承关系[编辑 | 编辑源代码]

基本操作[编辑 | 编辑源代码]

初始化[编辑 | 编辑源代码]

// 默认初始容量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);

常用方法[编辑 | 编辑源代码]

核心操作方法对比
操作类型	队列首部	队列尾部	可能抛出异常	返回特殊值
插入	`addLast(e)` \| 队列满时抛出`IllegalStateException` \| `offerFirst(e)`/`offerLast(e)`
移除	`removeLast()` \| 队列空时抛出`NoSuchElementException` \| `pollFirst()`/`pollLast()`
检查	`getLast()` \| 队列空时抛出`NoSuchElementException` \| `peekFirst()`/`peekLast()`

代码示例[编辑 | 编辑源代码]

基础用法[编辑 | 编辑源代码]

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]

循环数组实现原理[编辑 | 编辑源代码]

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

当数组空间不足时，扩容机制如下： 1. 当前容量加倍 2. 重新排列元素： $n e w C a p a c i t y = o l d C a p a c i t y \times 2$ 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题的经典算法：

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;
}

性能比较[编辑 | 编辑源代码]

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

最佳实践[编辑 | 编辑源代码]

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

页面模块:Message box/ambox.css没有内容。

常见问题[编辑 | 编辑源代码]

何时选择ArrayDeque vs LinkedList[编辑 | 编辑源代码]

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

扩容机制详解[编辑 | 编辑源代码]

扩容时： 1. 计算新容量：解析失败 (语法错误): {\displaystyle newCapacity = n + (n \lt 64 ? n + 2 : n \gt\gt 1)} 2. 验证容量不超过MAX_ARRAY_SIZE（ $2^{31} - 1 - 8$ ） 3. 创建新数组并复制元素

总结[编辑 | 编辑源代码]

`ArrayDeque`是Java集合框架中高效的双端队列实现：

适合作为栈和队列使用
比`LinkedList`更节省内存
头尾操作性能优异
注意非线程安全特性

模板:Exercise