最近有个实习生问我一个问题JDK 里现成的LinkedList、ArrayDeque甚至LinkedBlockingQueue都能当队列用为什么还要研究“队列的实现”我当时没有直接回答而是反问他“你清楚数组队列的假溢出是什么吗你知道循环队列为什么要浪费一个空间吗你能把阻塞队列和线程池的workQueue参数讲明白吗”他愣了一下。这就是这篇博文的出发点。队列是 Java 基础里最容易被“用过但没实现过”的数据结构也是面试里出现频率极高的考点。这篇内容不只是贴一段能跑的代码我会把数组实现、链表实现、循环队列的边界处理、JDK 的 Queue 接口体系、阻塞队列选型以及队列在线程池和消息场景里的真实角色串起来讲。适合正在系统复习 Java 基础的人、准备面试的开发者以及想补数据结构底层认知的进阶读者。1. 既然要手写队列先想清楚这三个问题很多人一上来就敲代码这其实顺序反了。队列看起来简单但真正动手实现的时候有几个前置问题没想明白代码写出来大概率是“能跑但经不起问”。1.1 队列到底在解决什么问题队列是一种“先进先出”的线性表只允许在一端插入、在另一端删除。这个约束看起来简单但它是构建异步、削峰、缓冲、任务调度的基石。举一个生活化的类比奶茶店排队。先到的人先拿到奶茶后来的排在队尾这就是 FIFO。如果后到的人先拿奶茶那这个数据结构就不叫队列叫栈。在计算机世界里队列的应用无处不在操作系统的 IO 请求队列、CPU 任务调度队列、网络数据包的接收缓冲区、数据库连接池的等待队列、线程池的任务队列、消息中间件里的消息堆积队列。你会发现所有涉及“来不及处理先缓存起来按顺序慢慢处理”的场景背后都是队列。所以实现队列的第一课不是写代码而是理解这个数据结构存在的意义它提供了一种有序的、可控的缓冲机制。1.2 数组和链表两种底子的本质差异队列的底层存储有两种主流方案连续内存数组和分散内存链表。这两个方案没有绝对优劣关键是理解它们的差异。数组的底层是一块连续的内存空间元素在内存里挨在一起。这个特性带来两个结果随机访问效率极高通过下标可以直接算出内存地址时间复杂度 O(1)。现代 CPU 有缓存行机制遍历数组时相邻元素大概率在同一个缓存行里加载一次内存就能处理多个元素实际运行速度比链表快很多。链表的底层是节点对象每个节点通过引用指向下一个节点。节点的内存地址不连续每个节点还额外存储了一个引用指针。带来的优势是添加和删除节点只需要调整指针不需要搬移整个数组。理论上没有容量上限只要内存够就可以一直追加。缺点是每个节点有额外内存开销且遍历时 CPU 缓存命中率低性能反而可能不如紧凑的数组。用一句话总结数组是“紧凑但死板”链表是“灵活但松散”。手写队列时如果你能预知容量上限、追求吞吐量优先选数组如果你需要无界动态扩容、频繁增删节点链表更自然。1.3 手写之前要定义的边界条件我在评审代码时发现大多数新手写的队列能处理“正常路径”但在边界条件上翻车。动手前至少要明确这四件事队列空的条件是什么队列满的条件是什么入队时容量不够怎么办扩容、拒绝还是阻塞出队时队列为空怎么办返回 null、抛异常还是阻塞等待这四个问题直接决定了队列的语义。普通队列和阻塞队列的区别本质就是“满的时候怎么办”和“空的时候怎么办”这两个问题的不同回答。所以写代码之前先想清楚这些问题比背代码重要得多。2. 第一版实现数组队列以及它的致命伤先来一个标准的数组实现感受一下核心逻辑。2.1 一个能跑的数组队列public class ArrayQueueE { private Object[] elements; private int head; private int tail; private int size; private static final int DEFAULT_CAPACITY 10; public ArrayQueue() { this(DEFAULT_CAPACITY); } public ArrayQueue(int capacity) { elements new Object[capacity]; head 0; tail 0; size 0; } public boolean enqueue(E item) { if (item null) { throw new NullPointerException(队列不支持 null 元素); } if (size elements.length) { throw new IllegalStateException(队列已满); } elements[tail] item; tail; size; return true; } SuppressWarnings(unchecked) public E dequeue() { if (size 0) { return null; } E result (E) elements[head]; elements[head] null; // 释放引用帮助 GC head; size--; return result; } SuppressWarnings(unchecked) public E peek() { return size 0 ? null : (E) elements[head]; } public boolean isEmpty() { return size 0; } public int size() { return size; } }这段代码的逻辑很简单tail指向下一个入队位置head指向队首元素。入队时把元素放到tail位置然后tail出队时取出head位置的元素然后head。这里有一个细节值得说明出队时我用elements[head] null手动释放了引用。如果不做这一步数组中已经出队的元素会一直被引用着对于长期运行的队列来说这会导致内存无法回收形成一种隐蔽的内存泄漏。这个细节在面试里是很加分的点。2.2 假溢出是怎么产生的上面这个实现有一个严重问题。假设数组容量是 10你连续入队 10 个元素此时tail 10队列满。然后你出队 5 个元素head 5tail 10size 5。此时队列明明只有 5 个元素却在enqueue时报“队列已满”。为什么因为tail已经指到数组末尾了虽然数组前 5 个位置是空的。这就叫假溢出——数组有空间但线性指针已经到底了。如果不处理这个问题数组队列的空间利用率会越来越低最终完全无法入队。2.3 循环队列把数组掰弯解决假溢出的标准做法是把数组想象成一个环当tail到达数组末尾时不是报错而是绕回数组开头继续使用空位。关键代码是取模运算public class CircularArrayQueueE { private Object[] elements; private int head; private int tail; private int size; private static final int DEFAULT_CAPACITY 10; public CircularArrayQueue() { this(DEFAULT_CAPACITY); } public CircularArrayQueue(int capacity) { elements new Object[capacity]; head 0; tail 0; size 0; } public boolean enqueue(E item) { if (item null) { throw new NullPointerException(队列不支持 null 元素); } if (size elements.length) { throw new IllegalStateException(队列已满); } elements[tail] item; tail (tail 1) % elements.length; size; return true; } SuppressWarnings(unchecked) public E dequeue() { if (size 0) { return null; } E result (E) elements[head]; elements[head] null; head (head 1) % elements.length; size--; return result; } SuppressWarnings(unchecked) public E peek() { return size 0 ? null : (E) elements[head]; } public boolean isEmpty() { return size 0; } public int size() { return size; } }核心变化只有两行tail (tail 1) % elements.length和head (head 1) % elements.length。%运算让指针在到达数组末尾后自动回到开头。举个例子数组长度 5tail 4时入队一个元素(4 1) % 5 0tail绕回 0下一次入队就会写到数组开头的位置。这样整个数组的空间被循环利用假溢出问题彻底解决。这里有一个容易被忽略的面试考点循环队列也可以用“浪费一个空间”的方式判断队空和队满而不是维护 size 字段。具体做法是队空条件head tail队满条件(tail 1) % capacity head这种方式牺牲一个存储单元换来的是不需要维护 size 字段在极低层级的嵌入式环境里有一定的意义。但我在实现中选择了维护 size 的方式逻辑更直观也不容易出错。两种方案都能讲清楚面试时应该说得出取舍。3. 第二版实现链表队列以及它的隐藏代价数组队列解决假溢出之后已经可以用了但它还有一个限制初始容量固定。容量设小了队列满了只能拒绝容量设大了内存又浪费。要解决这个问题要么实现动态扩容要么直接换链表。3.1 链表队列的核心代码链表队列的思路比数组队列更自然入队就是在链表尾部追加节点出队就是移除链表头部节点不需要搬移任何元素。public class LinkedQueueE { private NodeE head; private NodeE tail; private int size; private static class NodeE { E data; NodeE next; Node(E data) { this.data data; } } public void enqueue(E item) { if (item null) { throw new NullPointerException(队列不支持 null 元素); } NodeE newNode new Node(item); if (tail null) { head newNode; tail newNode; } else { tail.next newNode; tail newNode; } size; } public E dequeue() { if (head null) { return null; } E data head.data; head head.next; if (head null) { tail null; } size--; return data; } public E peek() { return head null ? null : head.data; } public boolean isEmpty() { return head null; } public int size() { return size; } }几个关键点需要说明维护tail引用让入队操作变成 O(1)否则每次入队都要从头遍历到尾部时间复杂度会退化到 O(n)。dequeue时如果head变成 null说明队列空了此时tail也必须置为 null。这是一个非常容易漏掉的边界条件漏掉后会导致“队列已空但 tail 还指向旧节点”的脏状态。链表队列不需要担心假溢出只要内存足够节点可以无限追加。3.2 为什么链表队列没有假溢出数组队列的假溢出源于“连续内存 线性指针”的组合——指针到达物理末尾时前面空出来的位置用不上。链表队列的节点是离散的每个新元素都对应一个新建的节点通过指针连接不存在“物理末尾”的概念。tail永远指向最后一个有效节点的实际位置任何位置都可以通过新节点延展。这也是为什么很多无界队列选择链表做底层它的容量上限只取决于内存大小而不是初始化时定死的容量。3.3 链表队列的性能补偿点链表队列虽然解决了动态扩容问题但引入了隐藏代价每次入队都要新建一个节点对象涉及内存分配和对象头开销。节点之间有引用指针遍历时无法利用 CPU 缓存局部性。大量节点在内存中分散对 GC 压力更大。一个常见的折中方案是预分配节点池。在系统启动时提前创建一批节点存入空闲链表入队时从池中取出节点复用出队时把节点归还给池子。这样做避免了频繁的对象创建和销毁在消息中间件、网络框架等追求低延迟的场景里很常见。JDK 的ConcurrentLinkedQueue默认就使用了类似思路只不过它的节点回收依赖于 GC并没有显式对象池。4. 别重复造轮子JDK 的 Queue 生态到底怎么用手写实现的意义在于理解底层原理但生产环境里除非你有非常特殊的性能诉求否则不要重复造轮子。JDK 已经提供了一套层次分明的队列生态关键在于选对实现。4.1 Queue 接口的方法设计哲学先看接口层。java.util.Queue继承了Collection定义了两组语义不同的方法操作失败时抛异常失败时返回特殊值入队add(e)offer(e)出队remove()poll()查看队首element()peek()为什么 JDK 要设计两套方法因为队列有两种典型的使用场景容量有界的队列入队失败是预期内的情况用offer返回false更合理调用方可以做降级处理。业务语义上“入队必须成功”的场景用add抛异常更直接让异常处理逻辑显式化。出队同理。remove()在队列为空时抛NoSuchElementExceptionpoll()返回null。这里有个常见的坑如果队列本身允许存 null 元素那么poll()返回 null 就无法区分是“队列为空”还是“取到了 null”。所以 JDK 的ArrayBlockingQueue直接在文档里禁止 null 元素入队这是一处非常严谨的设计。4.2 LinkedList 和 ArrayDeque选谁日常业务代码里LinkedList经常被当成队列用因为它的addLast和removeFirst正好对应入队和出队。但从性能角度说我更推荐ArrayDeque。维度LinkedListArrayDeque底层结构双向链表循环数组随机访问O(n)O(1)入队/出队O(1)O(1)内存开销每个元素有节点对象和两个指针数组连续内存少量空位容量上限无界受内存限制自动扩容是否支持 null支持不支持ArrayDeque在入队和出队时虽然也要处理扩容但它扩容是“整块复制”且底层是连续数组CPU 缓存命中率远高于链表。在绝大多数业务场景下ArrayDeque的性能都优于LinkedList。有意思的是LinkedList实现了Deque接口ArrayDeque也实现了Deque接口但两者的历史定位完全不同。LinkedList更通用它同时是List和DequeArrayDeque则专门面向栈和队列场景做了优化。如果明确要用队列或栈优先ArrayDeque。4.3 阻塞队列从数据结构到并发原语普通队列只解决数据组织问题不涉及线程协作。但生产环境里的队列往往跨线程使用于是 JDK 提供了一套BlockingQueue接口在入队和出队操作上加上了阻塞语义。BlockingQueue在Queue的基础上增加了几种行为入队时队列满线程阻塞等待直到队列有空间。出队时队列空线程阻塞等待直到队列有元素。支持带超时时间的阻塞操作offer(e, timeout, unit)和poll(timeout, unit)。常用的实现有以下几种ArrayBlockingQueue有界、基于数组、公平性可通过构造参数指定。适合对容量有硬上限的场景。LinkedBlockingQueue基于链表、默认无界容量Integer.MAX_VALUE也可构造时有界。吞吐量通常高于ArrayBlockingQueue。SynchronousQueue不存储任何元素的队列每个入队操作必须等待另一个出队操作。适合直接交接模式。PriorityBlockingQueue无界、支持优先级比较出队顺序由优先级决定而非插入顺序。DelayQueue元素只有到达延迟时间后才能被取出典型的延迟任务调度场景。这一块也是 Java 并发编程里最容易考到的内容和线程池的workQueue参数直接相关。5. 队列实现的面试考点拆解队列本身是基础数据结构但它在 Java 面试里能延伸出大量问题。我把高频考点做了个梳理。5.1 面试官在这一题上想听到什么如果你被问到“实现一个队列”面试官考察的核心点其实是三件事第一边界意识。你的队列满时怎么办空时怎么办head和tail的指针移动逻辑是否自洽这能区分“背过代码”和“真正理解”。第二复杂性权衡。数组实现和链表实现的差异、循环队列的取模逻辑、扩容策略都是在考察你对底层原理的掌握程度。第三工程意识。你知不知道 JDK 提供了哪些现成队列知不知道阻塞队列和线程池的关系能不能解释offer和add的区别这决定了面试官是否愿意让你通过基础轮。建议准备一个“手写面试版”的循环队列要求自己能在白板上流畅写出核心逻辑并能清晰解释每一个边界条件的理由。5.2 两道高频衍生题第一道是“用两个栈实现队列”。思路是用两个栈一个入栈一个出栈。入队时直接压入stackIn出队时如果stackOut为空把stackIn的元素全部倒入stackOut再弹出stackOut栈顶。这样保证出队顺序是 FIFO。这道题的坑在于不要在每次出队时都倒数据否则复杂度会退化。正确做法是“按需倾倒”stackOut非空时直接弹出为空时才批量倒入。摊还分析下每个元素最多进栈两次、出栈两次时间复杂度 O(1)。第二道是“循环队列如何判断空和满”。有两种方案维护 size 字段空条件size 0满条件size capacity或者牺牲一个存储位空条件head tail满条件(tail 1) % capacity head。我在前文实现中用的是第一种方案因为更直观第二种方案省了一个字段但在判断时会有一个存储位置永远无法使用需要向面试官解释清楚这个空间代价。6. 从手写实现到业务落地队列在真实项目中的角色手写队列是理解原理的训练场但真实项目的队列要比教科书复杂得多。这一章聊聊我在实际项目中频繁接触的两类队列场景。6.1 线程池与阻塞队列的选择逻辑线程池是阻塞队列最经典的应用场景。ThreadPoolExecutor的构造参数里workQueue决定了任务排队策略。我用一个实际配置来说明ThreadPoolExecutor executor new ThreadPoolExecutor( 2, // corePoolSize 8, // maximumPoolSize 60, TimeUnit.SECONDS, // 空闲线程回收时间 new ArrayBlockingQueue(1000), // 有界任务队列 new ThreadFactoryBuilder().setNameFormat(order-process-%d).build(), new ThreadPoolExecutor.AbortPolicy() // 拒绝策略 );这个配置的语义是核心线程 2 个任务超过 2 个时先入队队列满后创建新线程到 8 个再满就触发拒绝策略。排队等待的任务最多 1000 个超过的订单直接抛出异常避免无界堆积导致内存溢出。这里有个实践教训不要默认使用无界队列。LinkedBlockingQueue默认无界一旦任务生产速度超过消费速度队列会无限增长最终撑爆内存。在流量洪峰面前显式指定有界队列加拒绝策略比默默堆积然后系统宕机要可控得多。6.2 消息队列和本地队列的分工业务系统里的“消息队列”如 Kafka、RocketMQ本质也是队列但它解决的是分布式系统之间的异步通信问题比本地 JDK 队列多了一层网络传输和持久化。举一个我在支付系统中处理的订单超时场景本地队列DelayQueue保存延迟任务每个任务到点后从队列取出触发超时处理逻辑。消息队列订单状态变更事件发给 Kafka下游积分、通知、对账系统各自消费互不影响。这两类队列的分工差异很明显本地队列是 JVM 内部的内存结构速度快但无法跨进程消息队列是独立的中间件负责跨系统传递数据和状态。还有一个常见的生产问题是“消息队列重复消费”。根因往往在消费端——消息已经处理成功但消费确认还没来得及发送就宕机了重启后重新消费。解决思路是让消费逻辑具有幂等性比如用唯一业务键做去重表或者用数据库的唯一索引兜底。这些都是队列应用中的实战细节面试时如果能主动讲出这类处理经验是很加分的。回到开头那个实习生的问题。现在我有了更完整的答案研究队列的实现不是为了在生产环境手写一个替代品而是为了建立对数据结构边界的敏感度。当你见过假溢出、理解过循环队列的取模、亲手处理过链表空尾指针再去看ArrayDeque的扩容、ArrayBlockingQueue的take和put阻塞逻辑会发现自己不再是一个“调 API 的人”而是真正懂原理的人。这个转变就是学习数据结构的最大回报。