Java ArrayDeque应用示例

ArrayDeque 是一个非常高效的双端队列，适合多种场景。接下来列出几种最佳实践场景及代码示例，以帮助理解如何高效地使用 ArrayDeque。

一、栈的替代实现

ArrayDeque 可以替代 Stack 使用，因为它在不需要线程安全的情况下比 Stack 更高效。使用 addFirst 和 removeFirst 方法模拟“后进先出”的栈结构。

示例：

ArrayDeque<Integer> stack = new ArrayDeque<>();

// 压栈操作

stack.addFirst(1);

stack.addFirst(2);

stack.addFirst(3);

// 弹栈操作

while (!stack.isEmpty()) {

System.out.println(stack.removeFirst()); // 输出：3, 2, 1

}

二、队列的替代实现

与 LinkedList 不同，ArrayDeque 是基于数组实现的，避免了链表的节点开销。因此它适合用作普通的队列，在需要“先进先出”（FIFO）的队列操作时可以直接使用 addLast 和 removeFirst。

示例：

ArrayDeque<String> queue = new ArrayDeque<>();

// 入队操作

queue.addLast("A");

queue.addLast("B");

queue.addLast("C");

// 出队操作

while (!queue.isEmpty()) {

System.out.println(queue.removeFirst()); // 输出：A, B, C

}

三、双端队列操作

ArrayDeque 支持在两端添加和删除元素，非常适合需要在两端进行操作的场景。比如，模拟浏览器的前进和后退功能。

示例：

ArrayDeque<String> history = new ArrayDeque<>();

// 用户访问页面

history.addLast("Page1");

history.addLast("Page2");

history.addLast("Page3");

// 后退

System.out.println(history.removeLast()); // 输出：Page3

System.out.println(history.removeLast()); // 输出：Page2

// 重新访问新页面

history.addLast("Page4");

// 最终的历史记录

System.out.println(history); // 输出：[Page1, Page4]

四、广度优先搜索（BFS）算法

在图或树结构的广度优先搜索算法中，ArrayDeque 可以用作队列实现，其 addLast 和 removeFirst 操作非常适合 BFS 的 FIFO 特性。

示例：

class Node {

int value;

List<Node> neighbors;

Node(int value) {

this.value = value;

this.neighbors = new ArrayList<>();

}

}

void bfs(Node start) {

Set<Node> visited = new HashSet<>();

ArrayDeque<Node> queue = new ArrayDeque<>();

queue.addLast(start);

visited.add(start);

while (!queue.isEmpty()) {

Node node = queue.removeFirst();

System.out.println("Visited node: " + node.value);

for (Node neighbor : node.neighbors) {

if (!visited.contains(neighbor)) {

queue.addLast(neighbor);

visited.add(neighbor);

}

}

}

}

五、滑动窗口最大值

常见的滑动窗口算法通常涉及在窗口内的添加和移除操作，一般会使用 ArrayDeque 的双端特性来保持窗口的最大值、最小值或其他数据结构特性。

示例代码：

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

int resultIndex = 0;

ArrayDeque<Integer> deque = new ArrayDeque<>(); // 存储数组的索引

for (int i = 0; i < n; i++) {

// 移除滑动窗口之外的元素

if (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {

deque.pollFirst();

}

// 移除队列中所有比当前元素小的元素

while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {

deque.pollLast();

}

// 将当前元素添加到队列

deque.offerLast(i);

// 当窗口达到大小 k 时，记录窗口的最大值

if (i >= k - 1) {

result[resultIndex++] = nums[deque.peekFirst()];

}

}

return result;

}

滑动窗口的实现：每次滑动窗口向右移动时，只需将窗口左端的元素移出，右端的元素移入。

使用 ArrayDeque 进行入队和出队的操作时间复杂度均为 O(1)。

总体时间复杂度：每个元素最多被加入和移除一次，因此对于 n 个元素，总体时间复杂度为 O(n)。

这个方法也可以扩展用于其他滑动窗口问题，比如最小值、平均值等。

五、最后总结

使用 ArrayDeque 作为栈和队列的替代比 LinkedList 更高效，适用于栈、队列和双端队列操作。ArrayDeque 尤其适合滑动窗口等场景。由于它是基于数组的实现，ArrayDeque 不适合存储过大的数据结构（例如非常深的递归栈）