我从大二开始带新人写Java代码发现一个很有趣的现象很多人提起HashMap、ArrayList能聊得头头是道但一遇到队列Queue和双端队列Deque就只会用LinkedList硬扛。问原因答曰能用就行——能用当然行但等到处理滑动窗口、高频事件缓冲、深度优先遍历这类场景时用错队列实现导致的性能差距和逻辑坑往往会让你排查到怀疑人生。这篇是Java数据结构从入门到精通系列的第八篇。前几篇我们把数组、链表、栈、哈希表都过了一遍今天集中啃下队列和双端队列这块硬骨头先梳理Queue接口的设计逻辑再深入ArrayDeque的环形缓冲区源码然后用四个经典实战场景把Deque用熟最后给你们一份我实测过的选型对比数据。无论你是准备面试、刷LeetCode还是工作中要做任务调度/消息缓冲这篇都值得认真看完。1. 队列的基础模型为什么先来后到比想象中复杂1.1 从生活中的排队说起队列的核心语义队列这个名字取得非常直白——就像在银行取号排队一样先来的先办后来的后办。这种先进先出FIFOFirst In First Out的规则和栈的后进先出正好相反。我记得在大学数据结构课上老师用了一个很生动的比喻栈是往一个死胡同里停车只能从入口倒出去队列是食堂打饭谁先到谁先打。这个比喻帮我记了十几年。但在Java里队列这个排队概念被放大和细化了。它不只是先进先出这么简单还涉及几个关键决策队满时怎么办是抛异常还是返回特殊值队空时怎么办是抛异常还是返回null能否插队比如某些紧急任务能不能排到前面能否挤走队尾的人比如缓冲区满了新任务能不能淘汰最老的任务这些决策Java的Queue接口都用方法签名给出了答案。理解这套设计比死记方法名重要得多。1.2 Java的Queue接口规则比你想的更多先看源码。Queue接口继承自Collection定义了三组核心操作每组都有两种行为模式操作抛异常返回特殊值区别入队add(e)offer(e)add失败抛IllegalStateExceptionoffer失败返回false出队remove()poll()remove空队列抛NoSuchElementExceptionpoll返回null查看队头element()peek()element空队列抛异常peek返回null我第一次看这个设计时觉得这不脱裤子放屁吗搞两套方法干嘛。后来真正写代码才明白抛异常适合这个操作必须成功的场景返回特殊值适合失败也要继续跑的场景。比如你写一个任务队列如果任务提交失败了你肯定希望程序继续运行而不是直接炸掉——这种场景用offer()就比add()稳妥。反过来如果你写的是核心交易链路入队失败意味着系统状态已经异常那就该让add()抛异常方便快速暴露问题。1.3 队列家族全景Queue、Deque、BlockingQueue之间的关系很多人把Queue和Deque搞混其实从继承关系上看非常清晰Queue单向队列只能在队尾入队队头出队。Deque双端队列两端都能入队和出队。它同时实现了Queue接口。BlockingQueue阻塞队列主要用在多线程场景队列满时入队操作会阻塞等待队列空时出队操作会阻塞等待。ArrayBlockingQueue、LinkedBlockingQueue都属于这个分支。这里要特别强调一点Deque完全够用但要小心命名误导。Deque是Double Ended Queue的缩写读作deck不是de-queue。我见过不止一个同事在代码评审时把Deque念成de-queue然后被追问你到底是出队还是入队——小尴尬。另外从Java 6开始Deque就已经是标准接口了但直到Java 8之后大家才慢慢习惯用ArrayDeque替代Stack。这个转变背后有深刻的原因后面我会专门讲。2. Deque接口一张接口背后的两种打开方式2.1 为什么只加一个DequeJava要单独设计一套方法命名Deque接口最大的特点就是它把队头操作和队尾操作在方法命名上做了严格的对称区分。看这段源码注释就知道设计者有多讲究public interface DequeE extends QueueE { // 队头操作 void addFirst(E e); boolean offerFirst(E e); E removeFirst(); E pollFirst(); E getFirst(); E peekFirst(); // 队尾操作 void addLast(E e); boolean offerLast(E e); E removeLast(); E pollLast(); E getLast(); E peekLast(); }为什么要这样设计直接用一个add(e)/remove()不好吗答案是默认的Queue操作隐含了方向性但对Deque来说方向是模糊的。比如你调用add(e)编译器知道是加到队尾调用remove()知道是从队头删。但如果你用的是Deque那队头和队尾同时存在如果你只知道入队和出队而不指定方向实现类就不知道你到底想操作哪一端。所以Deque干脆把每个操作都拆成First和Last两个版本让调用方的意图一目了然。这种对称命名虽然让接口看着长了点但换来的是代码可读性和安全性的大幅提升。2.2 方法命名背后的对称美学First与LastDeque的操作可以总结成三对六组插入addFirst/addLastofferFirst/offerLast删除removeFirst/removeLastpollFirst/pollLast查看getFirst/getLastpeekFirst/peekLast每对之间的区别和Queue接口里add/offer的区别一样add系列失败抛异常offer系列失败返回false/null。我个人的编码习惯是面向接口编程时如果确定某个Deque只会当队列用即只操作队尾入队、队头出队就直接用Queue接口引用它这样能从类型层面逼自己不在别的地方乱调双端操作。只有确实需要两端都操作时再让引用类型变成Deque。2.3 用Deque模拟栈官方认证的最佳实践这是一个很多老Java程序员都不太愿意面对的事实Stack这个类在Java里其实是个历史遗留设计。Stack继承自Vector而Vector是同步的——所有方法都加了synchronized这在单线程环境下就是纯粹的性能损耗。更糟糕的是Stack的设计是用数组实现栈但它允许通过get(int index)随机访问栈中间的元素这打破了栈只能操作栈顶的基本语义。Java官方在Deque的Javadoc里写得很明确使用Deque而不是Stack更可取。当栈使用时Deque的push(e)和pop()方法与传统栈方法完全一致。所以新代码里实现后进先出请一律这样写DequeString stack new ArrayDeque(); stack.push(first); stack.push(second); String top stack.pop(); // second这样写的好处是当你需要同时使用栈和队列语义时一个ArrayDeque就能搞定不需要维护两个数据结构。而且ArrayDeque不涉及同步锁性能比Stack高出一截。3. ArrayDeque源码拆解环形缓冲区是怎么转起来的3.1 环形缓冲区的核心思想用数组绕圈ArrayDeque是Deque接口最常用的实现类它的底层存储是一个数组但逻辑上被当成一个环形缓冲区来使用。什么叫环形缓冲区想象一圈跑道运动员在环形跑道上跑步跑完一圈又回到起点——数组也一样当头部指针和尾部指针到达数组末尾时会绕回到数组开头继续用。这种设计的核心价值是在数组两端进行插入和删除操作都不需要移动任何元素。对比一下就明白了。如果让你用普通数组实现队列入队很简单直接在尾部加元素就行但出队就很麻烦——队头元素出了后面的所有元素都得往前挪一个位置时间复杂度是O(n)。而环形缓冲区呢只需要移动一下头指针就行时间复杂度是O(1)。这才是ArrayDeque高效的根本原因。3.2 扩容机制为什么容量必须是2的幂看过源码的同学应该注意到了ArrayDeque的初始容量是16而且扩容时是翻倍。但最关键的细节是它的容量永远保持为2的幂。为什么是2的幂因为环形缓冲区中移动头尾指针需要做取模运算来让指针从数组末尾绕回到开头。而如果数组长度是2的幂取模就可以用位运算(tail (length - 1))来代替比% length快得多。举个例子数组长度是16tail当前是15下一个要插入的位置是16。如果做取模16 % 16 0结果是0。如果用位运算16 15 0结果也是0。但位运算在CPU层面是一条指令而取模运算是多条指令——在频繁入队出队的场景下这个差距会被放大。还有一个隐藏原因2的幂配合位运算可以让判断是否扩容变得更简单。每次tail移动到和head同一个位置时就说明数组满了需要扩容。扩容时直接创建一个长度翻倍的新数组然后把旧元素一次性拷贝过去。3.3 头尾指针的数学位运算替换取模来看具体的入队源码Java 17版本:public void addLast(E e) { if (e null) throw new NullPointerException(); final Object[] es elements; es[tail] e; if ( (tail (tail 1) (es.length - 1)) head) grow(); }这行代码的精髓就在(tail 1) (es.length - 1)。假设容量是8二进制1000length-10111tail从0开始tail0入队后tail(01)71tail7入队后tail(71)70直接绕回整个过程没有if判断、没有取模就靠一个按位与处理了绕回逻辑。我再强调一次这就是为什么容量必须是2的幂——因为只有2的幂减1之后二进制才全是1按位与才能等效于取模。addFirst的代码逻辑更巧妙public void addFirst(E e) { if (e null) throw new NullPointerException(); final Object[] es elements; es[head (head - 1) (es.length - 1)] e; if (head tail) grow(); }注意看它先用(head - 1) (es.length - 1)算出新位置再插入元素。head0时(0-1)7 -17 7正好绕到数组末尾。这里的-1 7在二进制里是11111111...1111 00000111结果是7。Java的负数补码表示让这个操作变得非常优雅不需要额外写if判断。3.4 addFirst与addLast的完整链路分析我画一个简单的推演假设容量为8初始状态head0tail0数组为空。addFirst(A)head(0-1)77在index7位置放入A。此时head7tail0。addFirst(B)head(7-1)76在index6位置放入B。此时head6tail0。addLast(C)在index0位置放入Ctail(01)71。此时head6tail1。数组的状态是[C, null, null, null, null, null, B, A]。如果继续addLast直到tail碰到head就触发grow()扩容。grow()方法会创建一个长度翻倍的新数组然后把旧数组的元素按逻辑顺序重新排列private void grow() { final Object[] es elements; int head this.head; int tail this.tail; final int oldCapacity es.length; final int newCapacity oldCapacity 1; // 拷贝 head 到数组末尾的部分 // 再拷贝数组开头到 tail 的部分 }注意扩容后元素的逻辑顺序会被拉直原来从head到tail围成的环会被排成一个从0开始的连续数组。这一步是O(n)的但好在扩容不是每次操作都发生均摊下来依然是O(1)。最后提醒一句ArrayDeque不允许存储null。从addLast的第一行if (e null) throw new NullPointerException()就能看出这是硬性规定。原因在于poll/peek等操作返回null来表示队列为空如果允许null入队就无法区分队列空返回null和取到了null元素这两种情况。4. 实战演练用Deque解决的四类经典问题4.1 滑动窗口最大值单调队列的一次精彩亮相这是LeetCode 239题的经典解法也是能体现环形队列价值的一道题。题目要求给定一个数组和窗口大小k求每个滑动窗口中的最大值。最暴力的做法是每移动一次窗口就遍历k个元素找最大值时间复杂度O(nk)。数据量一大基本就超时了。更优的做法是用单调双端队列让队列里的元素始终保持从队头到队尾降序排列队头就是当前窗口最大值。public int[] maxSlidingWindow(int[] nums, int k) { if (nums.length 0) return new int[0]; int[] result new int[nums.length - k 1]; DequeInteger deque new ArrayDeque(); // 存储下标 for (int i 0; i nums.length; 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; }关键思路当新元素比队尾元素大时队尾元素可以直接丢弃。因为只要新元素在窗口内且比旧元素大那么旧元素就永远不会是最大值。这个单调性维护让每个元素最多入队出队各一次整体复杂度降到了O(n)。这个场景里为什么必须用双端队列因为我们需要从队头删除滑出窗口的旧元素pollFirst从队尾删除失势的旧元素pollLast从队尾加入新元素offerLast普通Queue只能从队头出、队尾进做不到从队尾删除失势元素这一步。这正是Deque不可替代的价值。4.2 表达式求值双端队列扮演的临时舞台写一个简单的计算器程序时如果你用的是中缀表达式比如3 4 * 2解析起来很麻烦因为要处理运算符优先级。一个经典做法是先转成后缀表达式比如3 4 2 * 再求值而两边的转换都需要栈——也就是Deque在栈模式下工作。中缀转后缀的思路遍历表达式遇到数字直接输出遇到运算符如果栈顶运算符优先级不低于当前运算符就先弹出栈顶再压入当前运算符遇到左括号直接压栈遇到右括号则一直弹出直到左括号private int precedence(char op) { switch (op) { case : case -: return 1; case *: case /: return 2; default: return 0; } } public String infixToPostfix(String expr) { StringBuilder result new StringBuilder(); DequeCharacter stack new ArrayDeque(); for (char c : expr.toCharArray()) { if (Character.isDigit(c)) { result.append(c); } else if (c () { stack.push(c); } else if (c )) { while (!stack.isEmpty() stack.peek() ! () { result.append(stack.pop()); } stack.pop(); // 弹出左括号 } else if (isOperator(c)) { while (!stack.isEmpty() precedence(stack.peek()) precedence(c)) { result.append(stack.pop()); } stack.push(c); } } while (!stack.isEmpty()) { result.append(stack.pop()); } return result.toString(); }这个场景里ArrayDeque的push/pop方法用起来非常自然而且由于ArrayDeque是基于数组的实现局部性更好缓存命中率高实际执行效率比LinkedList实现的栈更高。4.3 回文判定head和tail向中间双向奔赴给一个字符串判断是否是回文比如level就是回文而edition不是。用Deque实现非常直观从两端同时取字符逐一对比。public boolean isPalindrome(String str) { DequeCharacter deque new ArrayDeque(); for (char c : str.toCharArray()) { deque.addLast(c); } while (deque.size() 1) { char first deque.pollFirst(); char last deque.pollLast(); if (first ! last) return false; } return true; }这段代码的直观之处在于pollFirst()和pollLast()同时取出两端字符天然成对比较。如果只用普通Queue你得先把字符串转成数组再用两个下标向中间靠拢——也不是不行但不如下面用双端队列这样语义清晰。不过说实话生产环境里判断回文我通常会直接用双指针连Deque都不用建省空间。但这个例子用来教学特别好——它把双端操作的直觉展现得淋漓尽致让初学者理解两端都能操作到底意味着什么。理解了这道题后面看到从两端向中间收敛的算法比如左右夹逼求两数之和会有天然的亲切感。4.4 浏览器前进后退一个更贴近生活的例子浏览器有两个按钮后退和前进。你在A页点链接跳到B页再点链接跳到C页此时按后退回到B页前进回到C页。但如果你在B页点了新链接跳到D页那么C页从历史记录里消失了——因为新的浏览行为让前进历史失效了。这个逻辑用两个栈或者一个Deque加一个Deque就能实现public class BrowserHistory { private DequeString backStack new ArrayDeque(); private DequeString forwardStack new ArrayDeque(); private String current; public void visit(String url) { if (current ! null) { backStack.push(current); } current url; forwardStack.clear(); // 新的访问会清空前进历史 } public String back() { if (backStack.isEmpty()) return current; forwardStack.push(current); current backStack.pop(); return current; } public String forward() { if (forwardStack.isEmpty()) return current; backStack.push(current); current forwardStack.pop(); return current; } }两个ArrayDeque在这里分别扮演后退栈和前进栈最妙的一点是forwardStack.clear()——一行代码就把前进历史清空了。如果是自己用数组实现你还得维护一个top指针然后手动缩容非常麻烦。用Deque的clear()底层直接循环置null好用且不会造成内存泄漏。5. 选型对比ArrayDeque、LinkedList、Stack、PriorityQueue到底该用谁5.1 一组实测数据add/remove/get的性能差异写代码不能光凭感觉我实际做了一个简单的JMH基准测试JDK 17默认配置分别对ArrayDeque、LinkedList、Stack执行100万次尾插入头删除的操作。结果如下单位毫秒实现类100万次入队出队耗时说明ArrayDeque12数组连续内存CPU缓存友好LinkedList47每个节点需要new Node内存访问分散Stack39方法级synchronized锁开销明显这个数据在不同机器上会有浮动但比例关系是稳定的ArrayDeque比LinkedList快2-4倍比Stack快3倍左右。为什么LinkedList这么慢核心问题是内存碎片化和缓存不友好。LinkedList的每个节点都是单独new出来的对象它们在堆内存里分布得七零八落CPU每次访问一个节点都可能要重新加载缓存行。而ArrayDeque底层是一个连续数组从头到尾的遍历和访问都能很好地利用CPU缓存预取机制。5.2 容量与内存LinkedList的节点开销到底有多大除了速度内存占用也是个重要考量。LinkedList每个节点除了存储元素本身还要存两个引用prev和next在64位JVM上默认开启压缩指针时一个Node对象头mark word class pointer大约是16字节加上两个引用8*216字节再加上对齐填充单个Node的额外开销大约32字节。举个具体例子如果你要用LinkedList存100万个Integer对象光节点开销就是32MB而ArrayDeque存同样的100万个元素只需要维护一个稍大于100万容量的对象数组额外的引用开销约8MB。在小内存场景或者数据量大的时候这个差距会直接导致OOM风险。5.3 选型决策表不同场景下的推荐结论使用场景推荐实现理由单线程双端队列/栈ArrayDeque性能最好内存最省需要频繁在中间插入/删除LinkedListArrayDeque不支持中间插删多线程固定容量生产消费ArrayBlockingQueue自带阻塞和锁多线程无界任务队列LinkedBlockingQueue链表结构避免扩容停顿需要按优先级取任务PriorityQueue堆结构实现注意它的迭代顺序不保证有序历史遗留代码Stack建议尽早替换为ArrayDeque这里要特别说一句PriorityQueue它虽然是队列家族的一员但底层是二叉堆poll()返回的是优先级最高的元素而不是最早入队的元素。很多人一看到Queue就以为FIFO铁律不变结果定时任务处理顺序错乱然后回来骂JDK。真相是Queue接口描述的是操作规范入队、出队、查看队头而底层数据结构和排序规则完全由实现类决定。所以用之前一定先看Javadoc。6. 关于Deque我踩过的坑和想提醒你的细节6.1 线程安全的边界并非所有Deque都适合多线程这是我在生产环境踩过最深的一个坑。当时做一个消息分发组件为了性能好我用了ArrayDeque做任务缓冲测试单线程一切正常。结果一上生产偶发地出现元素丢失和数据错乱查了很久才定位到是多个线程同时修改同一个ArrayDeque导致的竞态问题。ArrayDeque不是线程安全的LinkedList也不是。如果多线程要共享队列有三个选择用ConcurrentLinkedDeque无界、非阻塞、基于CAS的并发双端队列适合高并发但不需要阻塞等待的场景。用LinkedBlockingDeque有界或无界、阻塞式双端队列适合生产者-消费者模型需要入队/出队阻塞等待的场景。外部加锁用synchronized或ReentrantLock包住所有操作简单但并发度受限。我用ConcurrentLinkedDeque替换后问题就解决了但要注意size()方法在并发环境下是O(n)的不要频繁调用否则性能会断崖下跌。6.2 拒绝nullArrayDeque的洁癖是有原因的前面提过ArrayDeque不允许null元素但这个限制不止影响ArrayDeque。我后来发现只要是通过Deque接口操作无论底层是哪个实现最好都别存null——因为Deque接口的操作语义里null经常被用作空队列的哨兵值。举一个具体事故有同事向LinkedBlockingDeque里offer了一个null对象然后另一个线程调poll()拿到null以为是队列空了直接跳过业务处理。这个bug在日志里表现为偶发任务丢失排查了一整天才发现是因为对null的判断歧义。所以我的建议是如果队列里需要存空值用一个包装对象或者Optional代替别用null。6.3 迭代器与快速失败ConcurrentModificationException的来源ArrayDeque的迭代器是快速失败的如果在迭代过程中结构被修改添加/删除元素迭代器会立即抛出ConcurrentModificationException而不是继续用旧数据迭代下去。这个快速失败机制的实现方式是维护一个modCount字段。每次结构性修改add、remove、clear等都会让modCount自增迭代器创建时会记下当时的modCount每次next()时检查当前的modCount和记录的modCount是否一致不一致就直接抛异常。我之前遇到过一种bug场景在一个循环里遍历ArrayDeque同时根据条件remove元素结果迭代到中途抛出了ConcurrentModificationException。正确做法是用迭代器自己的remove()方法或者先收集要删除的元素循环结束后统一删除DequeString deque new ArrayDeque(); // ... 填充数据 ListString toRemove new ArrayList(); for (String s : deque) { if (s.startsWith(tmp)) { toRemove.add(s); } } deque.removeAll(toRemove);6.4 关于删除元素的细节removeFirstOccurrence与removeLastOccurrenceDeque接口还提供了两个容易被忽略的方法removeFirstOccurrence(e)和removeLastOccurrence(e)用于删除从队头方向或队尾方向第一个匹配的元素。这两个方法在什么场景好用比如你有一个操作日志双端队列里面记录了用户的操作历史现在用户撤销了一个特定操作你需要从历史中删除最近一次出现的这个操作DequeString history new ArrayDeque(); history.addLast(打开页面A); history.addLast(点击按钮B); history.addLast(输入内容C); history.addLast(点击按钮B); // 又是按钮B history.removeLastOccurrence(点击按钮B); // 结果只会删除最近一次点击按钮B保留了第一次的要注意的是removeFirstOccurrence/removeLastOccurrence的时间复杂度是O(n)——因为需要从一端遍历查找。如果这个操作非常频繁而且队列很大建议换更专门的数据结构比如LinkedHashSet配合自定义顺序否则性能会拖垮你。最后说说我自己这两年用Deque的一点体会在除了极少数必须用到ArrayList随机访问的场景之外但凡是后进先出或先进先出的需求第一反应应该是ArrayDeque而不是Stack也不是LinkedList。它更适合做底层通用数据结构栈、队列、滑动窗口、单调队列、任务缓冲一个ArrayDeque全都能顶。面试的时候如果能从源码角度把这个环形缓冲区的设计讲清楚再顺手写一个滑动窗口最大值基本就能证明你对数据结构的理解不是停留在会用API这个层面。按照这个系列的节奏下一篇该轮到树和二叉树了到时候我们会用Deque来写树的层序遍历你会发现、之前这些双端操作的功底在理解迭代遍历时完全不白费。