ArrayDeque 是 Java 标准库中的一个双端队列（Deque）实现，它基于动态数组结构，提供快速的插入和删除操作，无论是在队列的头部还是尾部。由于其高效的性能和灵活的使用方式，ArrayDeque 常被用作栈或队列，支持 FIFO（先进先出）和 LIFO（后进先出）的数据结构。它特别适合于需要频繁进行元素插入和删除的场景，如任务调度、事件处理等。此外，ArrayDeque 还提供了对所有 Deque 操作的快速响应，使其成为实现各种算法和数据结构的理想选择。

肖哥弹架构 跟大家“弹弹” 高并发锁， 关注公号回复 'mvcc' 获得手写数据库事务代码

欢迎 点赞，关注，评论。

关注公号 Solomon 肖哥弹架构获取更多精彩内容

历史热点文章

• 解锁大语言模型参数：零基础掌握大型语言模型参数奥秘与实践指南
  

• 高性能连接池之HikariCP框架分析：高性能逐条分解(架构师篇)
  

• 缓存雪崩/穿透/击穿/失效原理图/14种缓存数据特征+10种数据一致性方案
  

• Java 8函数式编程全攻略：43种函数式业务代码实战案例解析(收藏版)
  

• 一个项目代码讲清楚DO/PO/BO/AO/E/DTO/DAO/ POJO/VO
  

• 17个Mybatis Plugs注解：Mybatis Plugs插件架构设计与注解案例(必须收藏)
  

ArrayDeque(业务结构）

ArrayDeque 是 Java 中的一个双端队列（Deque）实现，它基于动态数组来实现。

1、设计思考：

1. 需求场景：

2. 在许多编程任务中，需要一个支持快速插入和删除操作的队列，特别是在队列两端进行操作时。例如，在实现栈、队列、双向队列等数据结构时，这些操作非常常见。

3. 现有技术局限性：

4. ArrayList 提供了快速的随机访问能力，但在进行插入和删除操作时，特别是在队列的两端，可能需要移动数组中的大量元素，导致效率低下。

5. LinkedList 虽然提供了高效的插入和删除操作，但其随机访问性能较差，且内存开销较大。

6. 技术融合：

7. ArrayDeque 结合了数组的快速随机访问特性和链表的高效插入删除特性，使用一个可变大小的数组来存储元素，并提供了在数组两端快速添加或移除元素的能力。

8. 设计理念：

9. ArrayDeque 旨在提供一个高效的双端队列实现，它允许元素从两端快速地被插入或删除，同时保持了较高的内存效率和访问性能。

10. 实现方式：

11. ArrayDeque 内部使用一个可变大小的数组来存储元素，数组中的元素以循环方式存储，这样可以在数组的两端以 O(1) 的时间复杂度进行插入和删除操作。

2、内部细节：

1. 数组扩容：

2. 当元素添加到 ArrayDeque 时，如果当前数组没有足够的空间来存储新元素，ArrayDeque 会创建一个新的、更大的数组，并将旧数组中的所有元素复制到新数组中。

3. 新数组的大小通常是原始数组大小的两倍，但也可能根据当前的元素数量和负载因子进行调整。

4. 头部和尾部操作：

5. ArrayDeque 维护两个索引，分别表示头部和尾部的位置。

6. 当元素被添加到尾部时，尾部索引会增加；当元素被从头部移除时，头部索引会增加。

7. 当头部或尾部索引达到数组末尾时，它们会回绕到数组的开始位置，因为 ArrayDeque 的数组是循环使用的。

8. 数组收缩：

9. 虽然 ArrayDeque 主要通过扩容来适应元素的增加，但它并不会自动收缩数组的大小。如果需要减少内存占用，可以手动创建一个新的、更小的数组，并将当前的元素复制到新数组中。

10. 随机访问：

11. 尽管 ArrayDeque 提供了在两端快速插入和删除的能力，但它也支持快速的随机访问，因为底层数据结构是数组。

12. 插入元素：

13. 在新数组中，头部索引前的位置现在有了空间，ArrayDeque 可以直接在头部索引前插入新元素。由于数组是循环使用的，如果头部索引是 0，新元素将被插入到数组的最后一个位置，并且头部索引将更新为指向新元素。

14. 更新头部索引：

15. 插入元素后，头部索引会相应地向前移动，指向新插入的元素。

3、 数据结构

图说明：

• ArrayDeque：

• 表示 ArrayDeque 类的实例，是一个基于数组实现的双端队列。

• 数组 (Elements) ：

• ArrayDeque 内部使用一个动态数组来存储队列中的元素。

• Head Index：

• 表示队列头部的索引，用于 poll 或 peek 操作。

• Tail Index：

• 表示队列尾部的索引，用于 offer 或 peekLast 操作。

• Array Elements：

• 数组中的元素，存储队列中的数据。

• Element 1, Element 2, Element n：

• 表示数组中的具体元素。

4、 执行流程

图说明：

• 开始：执行操作的起始点。

• 创建 ArrayDeque 实例：初始化 ArrayDeque 对象。

• 入队操作：执行将元素添加到队列尾部的操作。

• 计算尾索引：计算当前尾元素的索引位置。

• 添加元素到尾：在尾索引位置添加新元素。

• 更新尾索引：更新尾索引以指向下一个可用位置。

• 结束入队：完成入队操作。

• 出队操作：执行将元素从队列头部移除的操作。

• 计算头索引：计算当前头元素的索引位置。

• 移除元素从头：移除头索引位置的元素。

• 更新头索引：更新头索引以指向下一个可用位置。

• 结束出队：完成出队操作。

• 头部查看：查看队列头部的元素。

• 读取头元素：读取头索引位置的元素。

• 尾部查看：查看队列尾部的元素。

• 读取尾元素：读取尾索引前一个位置的元素。

• 结束查看：完成元素查看操作。

• 结束：所有操作完成。

5、优点

1. 高效的插入/删除操作：

2. 在队列的两端插入和删除元素的时间复杂度为 O(1)。

3. 内存效率：

4. 相比于 LinkedList，ArrayDeque 使用数组存储元素，减少了内存开销。

5. 随机访问性能：

6. 相比于 LinkedList，ArrayDeque 提供了更好的随机访问性能。

6、缺点

1. 数组扩容/缩容开销：

2. 当数组容量不足以容纳更多元素时，需要进行扩容操作，这涉及到创建新数组和复制旧数组中的元素，可能会带来一定的性能开销。

3. 数据实时性：

4. 在多线程环境下，虽然 ArrayDeque 不是线程安全的，但可以通过外部同步机制来保证线程安全，这可能会影响数据的实时性。

7、使用场景

• 适用于需要快速插入和删除元素的场景，如实现一个任务调度系统。

• 作为栈、队列或双端队列使用，特别是在需要从两端进行元素添加或移除的操作中。

8、类设计

9、应用案例

在 Java 中，ArrayDeque 是一个基于动态数组实现的双端队列（Deque），它提供了高效的队列和栈操作。以下展示了如何在一个简单的生产者-消费者场景中使用它来管理任务队列：

import java.util.ArrayDeque;import java.util.Deque;
class Producer implements Runnable {    private final Deque<Integer> queue;
    public Producer(Deque<Integer> queue) {        this.queue = queue;    }
    @Override    public void run() {        for (int i = 0; i < 10; i++) {            queue.offer(i); // 生产者将元素添加到队列            System.out.println("Produced: " + i);            try {                Thread.sleep(100); // 生产时间            } catch (InterruptedException e) {                e.printStackTrace();            }        }    }}
class Consumer implements Runnable {    private final Deque<Integer> queue;
    public Consumer(Deque<Integer> queue) {        this.queue = queue;    }
    @Override    public void run() {        for (int i = 0; i < 10; i++) {            Integer item = queue.poll(); // 消费者从队列中取出元素            if (item != null) {                System.out.println("Consumed: " + item);            }            try {                Thread.sleep(100); //消费时间            } catch (InterruptedException e) {                e.printStackTrace();            }        }    }}
public class ArrayDequeExample {    public static void main(String[] args) {        Deque<Integer> queue = new ArrayDeque<>();        Thread producerThread = new Thread(new Producer(queue));        Thread consumerThread = new Thread(new Consumer(queue));
        producerThread.start();        consumerThread.start();    }}