1. 为什么我建议你认真学一下ArrayDeque和PriorityQueue很多Java开发者在刚接触集合框架时精力基本都花在ArrayList、HashMap、LinkedList这几个“大明星”身上面试被问烂了日常也天天用。但等你真正做了一段项目之后会发现光会这几个远远不够。我见过不少同事处理“先进先出”的业务场景时第一反应还是用ArrayList从头删元素或者用LinkedList当队列结果性能一塌糊涂、代码也写得别扭。ArrayDeque和PriorityQueue这两个类就是那种“我明明在JDK里见过它但从来没正眼看过它”的类型。ArrayDeque底层是循环数组实现的双端队列头尾插入删除都是O(1)既能当栈用又能当队列用性能比Stack和LinkedList都稳。PriorityQueue则更特别它是一个基于二叉堆的优先队列每次取出来的都是当前优先级最高的元素但内部并不是完全有序的——这个特性很多人一开始会理解拧巴。这篇文章我就把这两个类的核心概念、底层实现逻辑、常用方法、实战场景以及我实际踩过的坑一次性讲清楚。适合刚学完Java基础集合、准备进阶的初学者也适合那些“用过但不求甚解”的开发者用来查漏补缺。不需要你有很深的数据结构基础我会尽量把堆和循环数组这些概念讲得具体一点。提前说一句本文所有代码基于JDK 8不同版本细节可能有微小差异但核心设计两三个大版本内基本没变过放心看。2. ArrayDeque被低估的双端队列底层藏着循环数组2.1 循环数组是怎么做到头尾O(1)插入的ArrayDeque不是用链表实现的这一点很多人搞错。它底层是一个Object数组然后用两个整型变量head和tail来标记队列的头和尾。数组的容量始终是2的幂次方默认初始容量16。为什么要设计成2的幂因为这样可以用位运算来替代取模运算。比如往队尾加元素时正常写法可能是tail (tail 1) % length但因为是2的幂JDK里直接用tail (tail 1) (elements.length - 1)位与运算比取模快得多。别小看这点性能差距在高频入队出队的场景下这积少成多还是很明显的。具体工作方式是往队尾添加元素时直接把元素放到tail指向的位置然后tail往后移一位从队头弹出元素时直接取出head指向的元素然后head往后移一位。当tail追上head时说明数组满了触发扩容容量翻一倍然后把元素重新拷贝到新数组。整个过程没有元素的搬移这就是为什么ArrayDeque比LinkedList的插入删除性能更好。LinkedList虽然是双向链表头尾操作确实是O(1)但每个节点都要维护前驱后继引用还要频繁创建Node对象对CPU缓存不友好实际吞吐量落后ArrayDeque一大截。这一点我在后面的性能对比部分会给出实测数据。2.2 扩容机制和内存拷贝细节ArrayDeque的扩容触发条件是head tail也就是数组被填满了。扩容时newCapacity (oldCapacity 1)直接左移一位也就是乘2保证容量依然是2的幂。扩容后的数据拷贝不是简单System.arraycopy从头拷到尾因为数据在数组里是环形的可能从中间断开。JDK里的处理分两步第一段是拷贝head到数组末尾的数据第二段是拷贝数组开头到tail的数据。两段拼接起来放到新数组的头部然后head重置为0tail重置为oldCapacity。我看过很多源码解析在这里含糊带过实际自己去DEBUG一下这个过程你会对环形结构有非常直观的理解。这里有个细节值得注意ArrayDeque的扩容是“翻倍扩容”和ArrayList类似均摊下来每次添加操作还是O(1)的。但如果你能预估元素规模建议在构造时就传入容量new ArrayDeque(预计元素数量)。因为ArrayDeque不像HashMap有负载因子的概念传进去的容量会被直接当成初始数组大小不够了再扩所以尽量估准一点。2.3 核心方法速查与使用姿势ArrayDeque的方法比较多但我建议你按三个用途来记当队列用、当栈用、当双端操作用。当队列用FIFOArrayDequeString queue new ArrayDeque(); queue.offer(任务A); // 入队等价于 addLast queue.offer(任务B); String task queue.poll(); // 出队等价于 pollFirst取A当栈用LIFOArrayDequeString stack new ArrayDeque(); stack.push(第一层); // 等价于 addFirst stack.push(第二层); String top stack.pop(); // 等价于 removeFirst取第二层注意ArrayDeque作为栈使用时性能是优于java.util.Stack的因为Stack继承了Vector所有方法都加了synchronized在单线程环境下这个锁完全是多余的开销。JDK官方文档实际上也是建议优先使用ArrayDeque而不是Stack。双端操作deque.addFirst(element); // 头部插入满了抛异常 deque.offerFirst(element); // 头部插入满了返回false deque.addLast(element); // 尾部插入满了抛异常 deque.offerLast(element); // 尾部插入满了返回false deque.removeFirst(); // 移除头元素空了抛异常 deque.pollFirst(); // 移除头元素空了返回null deque.getFirst(); // 查看头元素空了抛异常 deque.peekFirst(); // 查看头元素空了返回null这里有个我自己用下来的建议在不确定队列是否为空的情况下优先使用poll和peek系列方法而不是remove和get系列因为返回null比抛NoSuchElementException更容易处理代码也会更干净。但如果你明确“这里不可能为空空了就是BUG”那用抛异常的方法能更快发现问题这也算是一种快速失败的设计思路吧。2.4 为什么ArrayDeque不能存nullArrayDeque的所有方法在插入null时都会直接抛NullPointerException这一点和LinkedList不同。这个设计其实是有讲究的。因为poll和peek方法用null来表示“队列为空”如果允许插入null那当poll返回null时你就无法区分到底是队列空了还是队列里本来就存了一个null。这种“哨兵值”的设计在很多容器里都能看到比如ConcurrentLinkedQueue也是同样的策略。所以你在使用ArrayDeque时业务数据中如果可能含null值入队之前必须先做过滤否则会在某个毫秒级时刻突然抛NPE而且还不容易定位。我在某个订单处理模块里就吃过这个亏当时一批订单数据里有一两条缺少关键字段被存成了null结果队列处理到一半就炸了。3. PriorityQueue最小的不一定在最后但取出来的一定是最小3.1 二叉堆是如何让“取最值”变成O(1)的PriorityQueue的底层是一个二叉堆具体来说是最小堆。堆是一种完全二叉树在PriorityQueue里直接用数组存储父子节点的关系通过索引计算假设某个节点在数组中的下标是i那么它的左子节点下标是2i1右子节点是2i2父节点是(i-1)/2。堆的核心约束只有一个父节点的值必须小于等于子节点的值。注意只是父子之间有序兄弟节点之间没有任何顺序要求。所以二叉堆能保证的是堆顶元素数组第一个元素一定是全局最小的但你不能指望整个数组是从小到大排好序的。用生活化的类比来解释堆就像是一个公司里的领导层级每个人只管自己下面的几个下属保证“我比我的下属能力强”但隔壁部门的人什么水平你管不着。而全公司的“最强者”一定在CEO的位置上。你要找最强者闭着眼睛直接抓CEO就行这就是为什么取堆顶元素是O(1)的。插入元素时新元素先放到数组末尾然后执行上浮操作跟父节点比较如果比父节点小就交换位置一路浮上去直到找到合适的位置。这个过程最坏情况下是O(log n)因为树的高度就是log n。删除堆顶元素时先把堆顶元素拿走然后把数组末尾的元素挪到堆顶再执行下沉操作跟两个子节点中较小的那个比较如果比它大就交换一路沉下去。这个过程同样也是O(log n)。3.2 自定义排序用Comparator掌控优先级判断PriorityQueue默认使用元素的自然顺序也就是元素必须实现Comparable接口。但实际开发中单纯靠自然顺序往往不够用更多时候你需要通过Comparator自定义规则。我举个例子在任务调度场景里我们希望紧急程度高的任务先出队紧急程度相同的时候先来的先出队。class Task { int urgency; // 紧急程度数字越大越紧急 long createTime; // 创建时间 String name; Task(int urgency, long createTime, String name) { this.urgency urgency; this.createTime createTime; this.name name; } }PriorityQueueTask taskQueue new PriorityQueue((t1, t2) - { // 紧急程度高的优先 if (t1.urgency ! t2.urgency) { return t2.urgency - t1.urgency; } // 紧急程度相同先来的优先 return Long.compare(t1.createTime, t2.createTime); });写完这个Comparator之后往队列里丢任务poll的时候永远会拿到当前紧急程度最高的那个任务。这里有个很容易踩的坑Comparator的返回值决定了优先级但如果你写反了比较方向那“最高的优先级”可能就变成“最低的优先级”了。我建议在写完Comparator之后先放三五个元素进去逐个poll出来打日志看一眼顺序确认无误再上线别以为一眼就能看出来对不对。3.3 PriorityQueue的扩容与迭代器特性PriorityQueue的初始容量是11扩容策略跟ArrayDeque不一样如果旧容量小于64直接翻倍再加2如果大于等于64容量增加50%。这个策略的动机是容量小时快速扩张减少扩容次数容量大时平稳增长避免浪费内存。扩容时会把老数组的元素整体拷贝到新数组由于堆的顺序存储在扩容后依然有效不需要重新调整堆结构。还有一个特性很多人不知道PriorityQueue的iterator()返回的迭代器并不会按优先级顺序遍历元素。你拿迭代器去遍历看到的顺序是无序的甚至可能看起来“乱七八糟”。这个设计第一次遇到时会觉得很反直觉。我记着自己第一次踩这个坑是在调试一个告警系统想打印一下当前队列里有哪些待处理的告警结果输出顺序既不是按时间也不是按级别我心里还在想这是不是源码有BUG。后来才发现迭代器遍历的只是底层数组的物理存储顺序堆只有在pop的时候才保证顺序。如果你需要按优先级顺序遍历整个队列正确做法是循环poll或者先把队列元素拷出来再排序。比如ListTask sortedTasks new ArrayList(taskQueue); sortedTasks.sort(comparator);3.4 经典实战用PriorityQueue一行思路解决TopK问题PriorityQueue最经典的实战场景就是TopK问题——在海量数据中找出最大或最小的K个元素。求最大的K个元素就维护一个大小为K的最小堆堆顶是目前这K个元素中最小的那个。遍历数据时如果当前元素比堆顶大就把堆顶替换掉。这样遍历完一遍堆里留下的就是全局最大的K个。求最小的K个元素则反过来维护一个大小为K的最大堆需要传一个反转的Comparator。这个思路的时间复杂度是O(n log K)在n很大的时候性能优势非常明显。如果是全量排序哪怕用最快的快排也是O(n log n)当n上亿的时候全量排序要几十秒而TopK方案只需要一次遍历加一个小堆维护几毫秒就能跑完。下面是一个求TopK的完整示例假设我们要从100万个整数中找出最大的10个public static ListInteger findTopK(ListInteger data, int k) { // 最小堆堆顶是当前K个元素中最小的 PriorityQueueInteger minHeap new PriorityQueue(k); for (int num : data) { if (minHeap.size() k) { minHeap.offer(num); } else if (num minHeap.peek()) { minHeap.poll(); minHeap.offer(num); } } return new ArrayList(minHeap); }用K个元素的小堆去兜住数据流思考过程也很简单新来一个数字如果它比当前TopK里最小的还小那它肯定进不了TopK如果比最小的那个大那它应当替换掉最小的那个。这里有个边界条件值得提醒PriorityQueue的构造器传入k时如果你确定k大于等于1就没问题但如果k等于0会直接抛IllegalArgumentException。做算法题或者实际项目时记得先拦截k0的情况。4. 实操对比ArrayDeque vs LinkedListPriorityQueue vs 全量排序4.1 双端队列该选谁一次压测带来的认知刷新我之前在一个模拟项目中做过一个消息缓冲队列的组件核心逻辑就是把上游请求先放入队列然后由下游消费者批量拉取处理。最初用的是LinkedList理由是“它是队列的标准实现”。后来压测发现性能不理想TPS上不去排查了很久才怀疑到队列实现上。我做了个简单的JMH压测分别用ArrayDeque和LinkedList执行10万次offer和poll操作结果让我印象很深// 简单压测代码循环10万次先offer再poll public static long testDeque(DequeInteger deque, int count) { long start System.nanoTime(); for (int i 0; i count; i) { deque.offer(i); } for (int i 0; i count; i) { deque.poll(); } return System.nanoTime() - start; }在本地环境跑出来的结果ArrayDeque耗时大约是LinkedList的一半左右。原因也不难理解ArrayDeque的元素都存储在一块连续的内存上CPU高速缓存的命中率高而LinkedList每个节点都是独立的Node对象分散在堆内存各处遍历和修改时频繁发生缓存未命中还要额外维护两个引用字段。Node对象本身是额外的内存开销。LinkedList每个元素都要包装成Node这个Node对象占用的内存通常是原始数据的几倍。如果你的队列里存的是百万级别的消息对象内存差距非常可观。所以我的结论很明确单线程环境下只要是“先进先出”或者“后进先出”的线性场景ArrayDeque几乎总是优于LinkedList。LinkedList真正有优势的场景是需要频繁在中间位置插入删除元素、并且你已经持有对应的ListIterator的情况而这种场景在日常业务代码里其实很少出现。4.2 PriorityQueue和全量排序时效优先场景的降维打击再对比一下PriorityQueue和全量排序在实际业务中的差异。某个订单履约系统中有一个“超时订单优先处理”的需求规则是订单超时时间越长越需要被优先处理新产生的订单排后面。同时系统要求新订单插入后能在极短时间内拿到当前最紧急的那个订单。方案一用一个ArrayList存所有订单每次要取最紧急订单时做一次全量排序再取第一个。这个方案在数据量很小的时候没什么问题但订单量过了十万之后每次全量排序就是毫秒级的耗时而且随着系统越来越忙这个耗时还在增长。方案二用PriorityQueue插入订单时offer进去自动上浮调整要处理时直接poll自动下沉调整。每次操作都是O(log n)十万条数据也就是十几次比较完全不是一个量级。还有个更典型的场景是“延迟任务调度”。我做过一个轻量级的定时任务模块任务都有一个执行时间每次从队列头部取出执行时间最近的那个任务。用PriorityQueue存储一个线程循环poll判断时间是否到了没到就sleep一小段时间再继续poll。整个调度器的核心代码不超过50行但性能和稳定性都不错。技术上这就是一个简单的延迟队列实现PriorityQueue在其中充当了“时间轴”的角色。这种“每次只取最值”的场景用PriorityQueue是天然契合的。它不需要维护全量有序性只保证堆顶是最值背后省掉的开销就是全量排序里那些“多余人物的比较”。5. 常见问题与避坑心得5.1 compareTo和Comparator返回0会导致什么这是个很隐蔽的问题。当两个元素的优先级相同时compareTo或者Comparator返回0PriorityQueue不保证它们的相对顺序。更准确地说堆在调整过程中相同优先级的元素位置是“随缘”的先插入的不一定先被取出来。如果业务上需要“优先级相同就按插入顺序处理”那必须在Comparator里加入一个递增的序号字段做次级排序就像我在前面Task例子里用createTime做次级排序一样。5.2 线程安全两个类都不是线程安全的ArrayDeque和PriorityQueue都不是线程安全的。多线程环境下并发修改不会有数据错乱到崩溃的程度因为fail-fast迭代器会抛ConcurrentModificationException但同时也会发生元素丢失、重复读取等隐蔽问题。如果你需要线程安全的双端队列优先考虑java.util.concurrent包里的LinkedBlockingDeque或ConcurrentLinkedDeque。如果只是需要线程安全的优先级队列JDK自带的PriorityBlockingQueue是最省事的选择它相当于在PriorityQueue外面套了一层锁加上阻塞等待逻辑。我见过一个极端案例某同学用ArrayDeque做多生产者单消费者的消息队列不加锁想着反正“就一个消费者不会有并发问题”。结果生产者的数量一上来消费者经常抓不到消息甚至偶尔出现ArrayIndexOutOfBoundsException。就是因为多线程同时offer时tail被多个线程同时更新数据错乱。这种低级错误在生产环境出了故障之后排查起来非常痛苦所以提前选对并发容器很重要。5.3 迭代器遍历PriorityQueue的意外顺序我在前面提到过PriorityQueue的迭代器不保证顺序。但还有一个相关细节容易踩坑foreach遍历PriorityQueue时如果循环体内部调用queue.remove()会抛ConcurrentModificationException。因为foreach用的是迭代器迭代器创建时会记录modCountremove方法会修改modCount迭代器一检查发现版本对不上立刻抛异常。正确的边遍历边删除方式是使用迭代器的remove方法或者先收集要删除的元素遍历结束后再统一removeAll。比如PriorityQueueTask queue new PriorityQueue(); // ... 添加元素 queue.removeIf(task - task.urgency 3);removeIf是JDK 8引入的默认方法内部会正确处理迭代时的删除操作推荐优先使用。5.4 容量初始化不当导致的不必要扩容ArrayDeque构造器传入的初始容量JDK内部会向上取整为2的幂次方。比如你传21实际容量是32。所以如果你精确计算了元素数量是30个传30进去实际是32多申请了一点但避免了扩容性能上是划算的。如果你传了一个很大的容量长期只使用一小部分ArrayDeque不会自动缩容这点和ArrayList的trimToSize不一样要注意内存占用。PriorityQueue初始容量传参不会做2的幂次方转换传多少就是多少所以按实际需要预估即可略微多估一些减少扩容。5.5 一个综合示例借助两个类实现一个简易任务调度器最后分享一个把两个类用起来的综合小例子。这是一个非常简易的定时任务调度器核心思想是用PriorityQueue存储按执行时间排序的任务用ArrayDeque存储待执行的任务列表。public class SimpleScheduler { private final PriorityQueueScheduledTask taskQueue new PriorityQueue( Comparator.comparingLong(t - t.executeAt) ); private final ArrayDequeRunnable readyQueue new ArrayDeque(); static class ScheduledTask { long executeAt; Runnable action; ScheduledTask(long executeAt, Runnable action) { this.executeAt executeAt; this.action action; } } public void schedule(long delayMillis, Runnable action) { long executeAt System.currentTimeMillis() delayMillis; taskQueue.offer(new ScheduledTask(executeAt, action)); } public void update() { long now System.currentTimeMillis(); // 把到期的任务从优先队列挪到待执行队列 while (!taskQueue.isEmpty() taskQueue.peek().executeAt now) { ScheduledTask task taskQueue.poll(); readyQueue.offer(task.action); } // 执行所有到期任务 Runnable action; while ((action readyQueue.poll()) ! null) { action.run(); } } }这个代码很简单但包含了一个很重要的设计思想PriorityQueue负责“时间排序”ArrayDeque负责“执行缓冲”两个数据结构各司其职。真实项目里的调度框架核心逻辑比这复杂得多但这套“最小堆选最近任务队列缓冲执行”的思路是很多调度器的公共底座。理解了这两个类的设计再看那些开源框架的调度源码你会发现很多东西都是相通的。我自己在项目里用它解决过一个实际需求某业务系统需要定时批量刷新缓存各业务的刷新时间点不同每次只需要执行“最紧急的那一批”不需要全量扫描所有任务。用上面这个思路改造后核心代码量减少了一半不止而且逻辑非常容易理解。6. 什么时候用ArrayDeque什么时候用PriorityQueue很多初学者会把这两个类放在一起比较其实它们的定位完全不同。ArrayDeque解决的是“线性结构里高效头尾操作”的问题PriorityQueue解决的是“始终能快速取到最优元素”的问题。如果非要说共性那就是它们都通过精心设计的底层数据结构在某些场景下做到了比通用结构更好的性能。我的选型建议是这样普通FIFO队列用ArrayDeque需要栈结构用ArrayDeque需要“每次取最值”的用PriorityQueue加合适的Comparator如果队列元素数量巨大并且要频繁“批量倒出”处理ArrayDeque这种连续内存的结构对缓存更友好优先考虑如果数据不断变化优先级且需要动态取出最值PriorityQueue是不二之选。面试的时候如果被问到这两个类建议不要只回答“ArrayDeque是双端队列PriorityQueue是优先队列”而是能把“循环数组如何实现O(1)头尾操作”、“完全二叉树如何用数组存储”、“堆的上浮下沉具体怎么做”这些底层细节讲清楚。这些内容才是真正区分“背了八股文”和“真的理解集合框架”的分水岭。我个人在实际项目中最大的体会是集合类的选择很少是一锤定音的。刚开始写代码时可以先用最熟悉的ArrayList顶上等性能数据出来或者逻辑复杂到需要更合适的数据结构时再切换到ArrayDeque、PriorityQueue这类“专业选手”。关键是心里要有这张地图知道什么场景下有什么工具可以切换别等到线上出了性能问题才想起来还有别的选择。平时写工具类或者算法题我会有意识地用ArrayDeque替代LinkedList、用PriorityQueue处理TopK问题练得多了选型就变成了肌肉记忆。这些看似不起眼的API用好了其实能在很长的职业生涯里持续帮你省时间。