Java ArrayDeque

Java ArrayDeque

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

核心特性

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

类继承关系

classDiagram Collection <|-- Queue Queue <|-- Deque Deque <|-- ArrayDeque class Collection{ <<interface>> } class Queue{ <<interface>> } class Deque{ <<interface>> } class ArrayDeque{ +ArrayDeque() +ArrayDeque(int numElements) }

基本操作

初始化

// 默认初始容量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）技术实现高效操作：

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

当数组空间不足时，扩容机制如下： 1. 当前容量加倍 2. 重新排列元素：$newCapacity=oldCapacity\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`类更高效

常见问题

何时选择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`更节省内存
• 头尾操作性能优异
• 注意非线程安全特性