深入解析 Java 中的 ArrayDeque：高效双端队列的实战指南

2026-02-04 18:43:08 0条评论 2次阅读 0人点赞

在日常的 Java 开发中，你是否经常需要在数据结构的首尾两端频繁地插入或删除元素？或者你是否在寻找比 INLINECODE3c1a5edf 性能更好、占用内存更低的队列实现？如果我们对性能有较高的要求，那么 INLINECODE9af38cec 包中的 ArrayDeque 绝对是一个不可多得的神兵利器。

在这篇文章中，我们将深入探讨 INLINECODE93e25cb0 的内部工作原理、它与 INLINECODEd6f2640a 和 Stack 的区别，以及如何在实际代码中高效地使用它。无论你是正在准备面试，还是正在构建高性能的系统，这篇文章都将为你提供详尽的实战指南。

为什么选择 ArrayDeque？

在 Java 集合框架的早期版本中，INLINECODE1210e65b 类曾经是处理栈操作的标准，但它继承自 INLINECODE5573bc6c，继承了同步锁带来的性能开销。而 INLINECODEa47b6d92 虽然实现了 INLINECODE4c48eda8 接口，但它在内存中需要为每个元素维护节点指针。

INLINECODE5f440dda 的出现解决了这些问题。它是 INLINECODEa402db73 接口的一种可变数组的实现。这就意味着，它在内部使用了一个数组，并通过一种巧妙的方式（我们稍后会详细讲解）来模拟双端队列的行为。当你不需要线程安全，但需要极致的读写性能时，它通常是首选。

让我们总结一下它的核心特性：

无容量限制：它会根据需要自动增长，通常容量翻倍。这意味着我们不用担心 IndexOutOfBoundsException（除非内存耗尽）。
极速操作：相比于 LinkedList，它通常更快。为什么？因为它利用了 CPU 缓存的局部性原理（数组在内存中是连续的），并且不需要像链表那样处理复杂的节点引用。
时间复杂度：像 INLINECODEee32dc0f、INLINECODE50aca660、INLINECODE45e73b4a、INLINECODE2b58a961 这样的操作，均摊时间复杂度都是 O(1)。这是非常高效的。
非线程安全：这一点非常重要。INLINECODE326485f7 不是线程安全的。如果在多线程环境下使用，你需要考虑手动加锁或者使用 INLINECODEcb838afa 的实现类（如 LinkedBlockingDeque）。

ArrayDeque 的类层次结构

在 Java 集合框架中，INLINECODEf9a32ddf 实现了 INLINECODE765e23ac 接口，而 INLINECODE58c876d0 接口又继承自 INLINECODE64244107 接口。这意味着 ArrayDeque 既可以作为双端队列使用，也可以作为栈（LIFO）或普通队列（FIFO）使用。

它位于 INLINECODE9a71a125 包中，我们可以直接导入使用。值得注意的是，它不继承自 INLINECODE226a0638 或 INLINECODE74ab221f 的标准子类，而是直接继承自 INLINECODEda5771c2，并实现了 Deque 接口。

如何声明与初始化

在 Java 中，声明一个 INLINECODE28a769b4 非常简单。我们需要指定它将要存储的元素类型。由于 INLINECODEf46304d8 是一个接口，我们通常将其引用类型声明为 INLINECODE3a8eda9e，而实现类指定为 INLINECODEca6c9dd4，这是一种良好的编程习惯（面向接口编程）。

基本语法如下：

// 泛型语法：Type 指的是我们想要存储的数据类型
Deque deque = new ArrayDeque();

让我们来看一个最基础的入门示例，感受一下它的双端操作能力：

import java.util.ArrayDeque;
import java.util.Deque;

public class BasicDequeDemo {
    public static void main(String[] args) {
        // 创建一个用于存储 Integer 的双端队列
        Deque d = new ArrayDeque();

        // 在队头添加元素 1
        d.addFirst(1); 
        // 在队尾添加元素 2
        d.addLast(2);  

        // 此时队列顺序为: [1, 2]

        // 从队头移除并返回元素
        int f = d.removeFirst(); // f = 1
        // 从队尾移除并返回元素
        int l = d.removeLast();  // l = 2

        System.out.println("移除的队头: " + f + ", 移除的队尾: " + l);
    }
}

输出结果：

移除的队头: 1, 移除的队尾: 2

深入构造方法

ArrayDeque 提供了三个构造方法，理解它们有助于我们优化内存使用。

#### 1. 默认构造方法

public ArrayDeque()

这是最常用的方式。它会创建一个空的 ArrayDeque。其内部的初始数组容量默认是 16 个元素。这意味着，在我们添加第 1 到第 16 个元素时，不需要进行扩容操作。

// 创建一个初始容量为 16 的双端队列
ArrayDeque deque = new ArrayDeque();

#### 2. 指定初始容量的构造方法

public ArrayDeque(int numElements)

如果你能够预估将要存储的大致元素数量，使用这个构造方法是一个极佳的性能优化手段。它可以避免在添加元素过程中频繁的数组扩容和数据复制。

注意：ArrayDeque 会将你指定的容量调整为 2 的幂次方（例如，你指定 25，它可能会创建容量为 32 的数组），以便进行高效的位运算。

// 创建一个初始容量足以容纳 25 个元素的 ArrayDeque
// 实际分配的内存可能会调整为 32 (2的5次方)
ArrayDeque deque = new ArrayDeque(25);

#### 3. 从集合创建

public ArrayDeque(Collection c)

这个构造方法允许我们将任何集合（如 INLINECODE902e58a1, INLINECODE3d35e955）转换为 ArrayDeque。它会将集合中的所有元素按照迭代器的顺序添加到新的双端队列中。

List list = new ArrayList();
list.add("Java");
list.add("Python");

// 从 List 创建 ArrayDeque
ArrayDeque deque = new ArrayDeque(list);

核心操作详解与实战

作为双端队列，ArrayDeque 的方法非常丰富。我们可以将其操作分为四大类：添加、访问、删除、以及遍历。让我们逐一攻克。

#### 1. 添加元素

我们可以使用 INLINECODEc08cffbe, INLINECODEd8721314, INLINECODE62f440e0, INLINECODEa962b7ea, INLINECODE65820c2b, INLINECODEafe236d0 等方法。

关键区别： INLINECODEc8ab202d 系列方法在容量受限（虽然 ArrayDeque 不受限）时可能会抛出异常，而 INLINECODE4525687b 系列方法通常返回 INLINECODE8ed90f17。但在 INLINECODEb4123873 中，由于容量是动态增长的，它们基本等效，都会成功添加元素。

下面是一个综合的添加示例：

import java.util.*;
import java.io.*;

public class AddingElements {
    public static void main(String[] args) {
        // 初始化
        Deque d = new ArrayDeque();

        // 使用 add() 方法 - 默认添加到队尾
        d.add("The");
        d.add("Geeks");

        // 使用 addFirst() - 添加到队头
        d.addFirst("To");

        // 使用 addLast() - 添加到队尾 (等同于 add)
        d.addLast("For");

        // 使用 offer() 系列方法 - 也是插入，语义上更偏向于队列操作
        d.offer("Coding");
        d.offerFirst("Welcome");
        d.offerLast("Practice");

        System.out.println("当前的 ArrayDeque 内容: " + d);
    }
}

输出结果：

当前的 ArrayDeque 内容: [Welcome, To, The, Geeks, For, Coding, Practice]

#### 2. 访问元素

当我们只想查看元素而不想删除它时，可以使用 INLINECODE4441e80a, INLINECODE3c843ea9, INLINECODEae6fa75c, INLINECODE962bdca0, peekLast()。

关键区别： INLINECODEd8e8ae2b 方法如果队列为空会抛出 INLINECODE7b5213e5，而 INLINECODE73bd10a8 方法如果队列为空则返回 INLINECODE3ba5b3bb。在进行空队列检查时，使用 peek 是更安全的做法。

import java.util.*;

public class AccessingElements {
    public static void main(String[] args) {
        ArrayDeque d = new ArrayDeque();

        d.add("Welcome");
        d.add("To");
        d.add("Java");
        d.add("World");

        System.out.println("初始 ArrayDeque: " + d);

        // peek() - 检索并返回队头，但不删除。如果为空返回 null。
        String head = d.peek();
        System.out.println("队头元素: " + head);

        // getFirst() - 检索并返回队头，但不删除。如果为空抛出异常。
        String first = d.getFirst();
        System.out.println("第一个元素: " + first);

        // getLast() - 检索并返回队尾，但不删除。
        String last = d.getLast();
        System.out.println("最后一个元素: " + last);
        
        // 验证 peek 不会删除元素
        System.out.println("调用 peek 后的 ArrayDeque: " + d);
    }
}

输出结果：

初始 ArrayDeque: [Welcome, To, Java, World]
队头元素: Welcome
第一个元素: Welcome
最后一个元素: World
调用 peek 后的 ArrayDeque: [Welcome, To, Java, World]

#### 3. 删除元素

从队列中移除元素主要有 INLINECODE3b357fb5, INLINECODEafd4a38d, INLINECODE5a793e06, INLINECODE011348e5, INLINECODEe272d672, INLINECODEebfec550。

关键区别： 同样是异常处理。INLINECODE102e8c73 系列在队列为空时抛出异常，INLINECODEbc96df18 系列返回 INLINECODE31f7acc1。还有一个特殊的方法 INLINECODE0aba1303 和 removeLastOccurrence()，可以删除第一次或最后一次出现的指定元素。

import java.util.*;

public class RemovingElements {
    public static void main(String[] args) {
        ArrayDeque d = new ArrayDeque();

        d.add("Apple");
        d.add("Banana");
        d.add("Cherry");
        d.add("Date");

        System.out.println("初始队列: " + d);

        // poll() - 获取并移除队头
        String head = d.poll();
        System.out.println("被 poll 移除的元素: " + head);

        // removeLast() - 获取并移除队尾
        String tail = d.removeLast();
        System.out.println("被 removeLast 移除的元素: " + tail);
        
        // remove() - 默认移除队头 (等同于 removeFirst())
        d.remove();

        System.out.println("所有操作后的队列: " + d);
    }
}

输出结果：

初始队列: [Apple, Banana, Cherry, Date]
被 poll 移除的元素: Apple
被 removeLast 移除的元素: Date
被 remove() 移除的元素: Banana
所有操作后的队列: [Cherry]

#### 4. 迭代与遍历

INLINECODEe091961e 实现了 INLINECODEd8125b96 接口，因此我们可以使用 INLINECODE074a5e86 循环或迭代器来遍历它。这里有一个陷阱：INLINECODE3a3b8cdd 的迭代器是快速失败 的。如果在迭代过程中，除了迭代器自己的 INLINECODE3d812fb8 方法外，我们修改了队列的结构（添加或删除元素），迭代器将立即抛出 INLINECODE72611e0f。

import java.util.*;

public class IteratingDeque {
    public static void main(String[] args) {
        ArrayDeque d = new ArrayDeque();
        d.add("A");
        d.add("B");
        d.add("C");
        d.add("D");

        // 1. 使用 for-each 循环
        System.out.println("For-Each 循环遍历:");
        for (String str : d) {
            System.out.println(str);
        }

        // 2. 使用 Iterator 逆序遍历 (使用 descendingIterator)
        System.out.println("
使用 Iterator 逆序遍历:");
        Iterator descItr = d.descendingIterator();
        while (descItr.hasNext()) {
            System.out.println(descItr.next());
        }
    }
}

内部实现原理：它是如何工作的？

为了真正掌握 INLINECODEcafc5c90，我们需要了解它的“引擎”。INLINECODE67151ae8 内部维护了一个动态数组（Object[] elements）。但与 ArrayList 不同，它并不是简单的从索引 0 填充到 length-1。

它使用了循环数组 的概念。它有两个重要的指针：

head：指向队首元素的索引。
tail：指向队尾元素下一个位置的索引。

当我们调用 INLINECODEc1e50aaa 时，INLINECODE6eedff8b 指针会向前移动（并处理回绕），当调用 INLINECODE8883af43 时，INLINECODE71bf0584 指针会向后移动。这种设计使得在两端添加元素的时间复杂度都是 O(1)。

当数组被填满时，它会进行扩容（通常翻倍），并将所有元素重新排列到新数组的正确位置。虽然这个过程（INLINECODE7df5b666 和 INLINECODE79a5127c）是 O(n) 的，但由于它是均摊发生的，整体性能依然保持 O(1)。

常见应用场景与最佳实践

替代 Stack：如前所述，Java 官方文档明确建议，对于栈的操作，应该优先使用 INLINECODE4957ede6 而不是 INLINECODEe3d12419 类。INLINECODE5df6c4e5 比 INLINECODE8d3ff7e7 更高效。

* 入栈操作：INLINECODEa7a54d04 (等同于 INLINECODE77fdd0e4)

* 出栈操作：INLINECODEbfe85222 (等同于 INLINECODEd8369bd7)

    // 使用 ArrayDeque 实现一个简单的栈
    Deque stack = new ArrayDeque();
    stack.push("Page 1");
    stack.push("Page 2");
    System.out.println(stack.pop()); // 输出 Page 2

工作窃取算法：在很多线程池的实现中（如 Java 7 引入的 ForkJoinPool），ArrayDeque 被用作工作窃取双端队列的基础，因为它支持极其高效的两端操作。

滑动窗口问题：在处理数组或流的滑动窗口最大/最小值问题时，双端队列是用来维护索引的标准数据结构。

性能优化建议

预估大小：如果你知道大概要存储多少数据，一定要在构造函数中指定初始容量。这能避免多次扩容带来的性能损耗。
避免 null 元素：INLINECODE1f3f7fc0 不允许 插入 INLINECODEbe8ca09b 值。如果你尝试 INLINECODE021fea83，它会抛出 INLINECODE8cfef32a。这是因为 INLINECODE5f61e5d5 和 INLINECODE54107286 方法利用 null 作为返回值来表示“队列为空”的特殊情况。

总结

让我们回顾一下这篇文章的要点：

INLINECODEf728ea1d 是 Java 集合框架中 INLINECODEca2a34f8 接口的高效可变数组实现。
它是非线程安全的，不支持 null 元素。
在大多数场景下，它的性能优于 INLINECODEf205c2d7 和 INLINECODEe611d084，特别是在作为栈或队列使用时。
它利用循环数组的概念，实现了在两端进行 O(1) 时间复杂度的插入和删除操作。

掌握了 INLINECODE57c60125，你就拥有了处理双端数据序列的强大工具。下次当你需要实现一个栈或者双端队列时，别忘了首先考虑它。开始在你的项目中重构代码，尝试使用 INLINECODEe3e99cc6 来替代旧的数据结构吧！

投稿给我们	如何建站？
vps是什么？	如何安装宝塔？
如何通过博客赚钱？	便宜wordpress托管方案
免费wordpress主题	这些都是免费方案

豆丁博客

深入解析 Java 中的 ArrayDeque：高效双端队列的实战指南

为什么选择 ArrayDeque？

ArrayDeque 的类层次结构

如何声明与初始化

深入构造方法

核心操作详解与实战

内部实现原理：它是如何工作的？

常见应用场景与最佳实践

性能优化建议

总结

相关文章美国1G带宽/1T流量高速vps $17.99/年