企业官网建设流程全解析

1. 队列是什么：不只是“排队”那么简单

队列这种数据结构，几乎每个学计算机的人都会遇到。如果你刚接触编程，可以把队列想象成食堂打饭的队伍：先来的先打饭，后来的排后面，谁也不能插队。程序的术语叫先进先出（FIFO，First In First Out），这和栈的“后进先出”正好相反。

我第一次系统写队列是在某次课程的实验里，要求用数组和链表各实现一遍队列。当时觉得这玩意儿太简单了，无非就是入队、出队、判空嘛。真正动手才发现，里面有几个特别容易被忽略的细节，比如假溢出、环形队列的判满判空、链表尾指针的维护。这些坑如果不提前搞明白，后面做 BFS（广度优先搜索）、消息队列、任务调度的时候都会栽跟头。

这篇文章我不会只贴几段代码了事。我会把队列的实现拆开揉碎，从数组实现到链表实现，从前端代码到实际测试，把每个决策背后的原因都讲明白。适合正在上数据结构课的学生，也适合准备面试、想彻底吃透队列的开发者。我尽量说人话，让小白也能跟上。

2. 整体设计与存储结构选型：先想清楚再动手

2.1 顺序队列为什么会有“假溢出”

写代码之前，我先聊聊设计取舍。队列的底层存储无非两种：顺序存储（数组）和链式存储（链表）。顺序存储优点很明显：内存连续、缓存友好、随机访问快，而且不需要频繁地 new 节点。缺点是容量固定，扩容要搬数据，还容易出现“假溢出”。

什么是假溢出？看下面这个场景：

假设数组长度是 4，一开始队头 front = 0，队尾 rear = 0。

入队 a、b、c 之后，rear 变成 3，front 还是 0，此时队里有 a、b、c 三个元素。

然后把 a、b 出队，front 变成 2，rear 还是 3。这时候队列里只剩一个 c，但 rear 已经指向数组末尾了。如果再入队一个 d，rear 要加 1 变成 4，而数组下标超出长度，程序直接报错“队列已满”。

可实际数组下标 0 和 1 的位置明明空着呢，这就叫假溢出——数组还有空间，却因为 rear 走到头就误判成满了。我第一次写队列就是用这种“线性”思路，结果测试时一跑就撞上了，当时完全懵了。

解决假溢出的思路有两个：

1. 每次出队后把后面元素往前挪，类似动态数组的删除操作。但这样每次出队都是 O(n)，效率太低，不适合当通用方案。
2. 把数组首尾相接，逻辑上当成一个环，这就是环形队列（Circular Queue）。rear 和 front 走到底部时，用取模运算绕回到开头。

比较一下：

在多数场景下，环形队列明显更优。所以这一版我会直接采用环形队列的方案，这才是工程里最常见的写法。

2.2 环形队列的两种判空判满策略

环形队列最核心的问题是：怎么区分“空”和“满”？

我画一个简单的环：数组长度 n=4，front 指向队头元素位置，rear 指向队尾元素的下一个位置。初始状态下 front = rear = 0，此时队列为空。

不断入队，直到 rear 追到 front，有一种方案是让 rear 走一圈刚好等于 front，这时候如果还允许入队，队列会变成“满且空”的诡异状态，无法区分。所以标准的环形队列通常采用两种策略之一：

策略一：预留一个空闲位置。队列满的条件变成(rear + 1) % n == front。也就是说，最多存 n-1 个元素。这样 rear 永远不可能和 front 相等，除非队列是空的。

策略二：引入 size 变量记录元素个数。入队时 size 加一，出队时 size 减一。判空看 size == 0，判满看 size == n。这个方案可以存满 n 个元素，代价是额外维护一个变量。

两种方案在实际工程里都有人用。内部实现类、嵌入式代码常用策略一，因为它省一个变量，判断也直观。应用层封装常用策略二，因为容量利用率更高。我手把手写的这个例子，就用策略一，因为面试时考官经常追着这个考点问。

2.3 为什么还要考虑泛型和容量扩容

队列的存储类型不能写死。如果今天存 int，明天存 String，又得重写一份。所以用 Java 就写泛型，用 C++ 就写模板，用 C 就老老实实把类型定义出来用宏替换。泛型的好处不只是省代码，还在于编译期就能发现类型错误。

容量扩容这块也容易被忽略。顺序队列的容量如果固定，业务量一上涨就出问题。所以我会在代码里加 grow 方法，当队列接近满的时候，把数组搬到更大的新数组里。你可能会问：“都预留一个位置判满了，怎么扩容呢？”做法是：当(rear + 1) % oldCapacity == front时，先扩容，再把元素按顺序搬到新数组，重新排列 front 和 rear 的位置。

我实际测试的时候发现，扩容如果不重新理顺元素顺序，后面取模运算很容易出错。别怕麻烦，搬完一定顺手重排一下。

3. 顺序队列与环形队列的完整实现

3.1 关键字段和构造方法

我用 Java 写一版基础的环形队列。完整代码片段如下：

public class MyCircularQueue<E> { private Object[] data; private int front; private int rear; private int capacity; private static final int DEFAULT_CAPACITY = 8; public MyCircularQueue() { this(DEFAULT_CAPACITY); } public MyCircularQueue(int capacity) { this.capacity = capacity; this.data = new Object[capacity]; this.front = 0; this.rear = 0; } public boolean offer(E value) { if (isFull()) { return false; } data[rear] = value; rear = (rear + 1) % capacity; return true; } public E poll() { if (isEmpty()) { return null; } E value = (E) data[front]; data[front] = null; front = (front + 1) % capacity; return value; } public E peek() { if (isEmpty()) { return null; } return (E) data[front]; } public boolean isEmpty() { return rear == front; } public boolean isFull() { return (rear + 1) % capacity == front; } }

这段代码很短，但每个字段都是有用意的。front 始终指向队头元素，rear 始终指向下一个空位。offer方法完成入队，poll方法完成出队。取模运算保证了数组下标在 0 到 capacity-1 之间环绕。

提示：poll方法里把data[front] = null是为了释放对象引用，否则数组一直持有旧对象的引用，GC 无法回收，长时间运行会内存泄漏。这个细节很细小，但做中间件的人一定不会忽略。

3.2 扩容操作的细节处理

如果不想让队列在满的时候直接拒绝服务，那就实现扩容。什么时候扩容呢？常见选择是：当判满条件触发时，或者当前元素数量达到容量的 75% 时就提前扩容。前者实现简单，后者性能更稳。我这里展示其中一种做法：

public boolean offerWithResize(E value) { if (isFull()) { resize(); } data[rear] = value; rear = (rear + 1) % capacity; return true; } private void resize() { int newCapacity = capacity * 2; Object[] newData = new Object[newCapacity]; int size = size(); int current = front; for (int i = 0; i < size; i++) { newData[i] = data[current]; current = (current + 1) % capacity; } this.data = newData; this.front = 0; this.rear = size; this.capacity = newCapacity; } public int size() { return (rear - front + capacity) % capacity; }

扩容的核心公式是size() = (rear - front + capacity) % capacity。这段公式如果不加 capacity 再取模，遇到 rear 小于 front 时会得到负数。我在初学阶段就踩过这个坑，直接算出个 -2，排查了半天才发现是取模的问题。

扩容之后，因为元素是从 front 位置开始按顺序搬的，所以新数组里 front 归零，rear 指向 size 的位置，整个顺序就理顺了。如果不理顺，后续入队出队全靠取模计算结果，同样能运行，但代码逻辑很难看，测试也容易绕晕。

3.3 入队出队的时间复杂度与边界测试

入队和出队操作，如果不考虑扩容，时间复杂度都是 O(1)。这也是队列能广泛用于高频消息转发的底气所在。假如你做的是订单处理系统，每秒钟成千上万的请求都要过队列，任何 O(n) 的入队操作都是不可接受的。

测试的时候我建议至少覆盖这几组场景：

• 空队列出队，返回 null 或者抛异常（看你设计，我这里返回 null）。
• 入队到恰好满，再尝试入队一个，看是否拒绝。
• 出队到只剩一个元素，再继续出队，看是否为空。
• 反复入队、出队多轮，验证取模是否出错。
• 扩容后再做一轮完整入队出队，确定数据顺序没被打乱。

我实测时最容易漏的是“出队导致 front 追上 rear”的场景。比如容量 4，入队 a、b、c 再出队 a、b，此时 front=2、rear=3。如果再用原来的线性思维去看，会觉得 front 大于 rear 很奇怪，但只要别忘了取模，它依然能正常工作。

4. 链式队列的实现与对比：什么时候该用链表

4.1 带头节点与不带头节点的取舍

数组实现虽然高效，但容量扩展毕竟要搬数据，而且内存需要一片连续空间。如果队列长度波动特别大，或者元素本身是复杂结构，更适合用链式队列。

链式队列的经典结构是：一个头节点指向队头，一个尾指针指向队尾。入队在链表尾部插入节点，出队在链表头部删除节点。这样入队和出队都是 O(1)。

链表实现第一个要决策的问题：头节点到底要不要用“哑节点”？

用哑节点（dummy head）的好处是：空链表和插入第一个节点时，不需要额外改头指针的指向，逻辑更统一。不用哑节点的话，每次插入和删除都要判断“链表是不是空”，代码容易漏分支。

我在教学和项目里更偏好用头节点指向真实元素，再加一个尾指针。因为队列的出队操作本来就是删除头部，用头节点反而别扭。你可以理解为：普通单链表头插法用得少，尾插法需要尾指针；而队列恰好是尾插头删。下面给一个常见的实现。

4.2 链式队列完整实现

public class LinkedQueue<E> { private Node<E> head; private Node<E> tail; private int size; private static class Node<E> { E value; Node<E> next; Node(E value) { this.value = value; } } public boolean offer(E value) { Node<E> newNode = new Node<>(value); if (tail == null) { head = tail = newNode; } else { tail.next = newNode; tail = newNode; } size++; return true; } public E poll() { if (head == null) { return null; } E value = head.value; head = head.next; if (head == null) { tail = null; } size--; return value; } }

这段代码里有一个很关键的细节：出队后如果 head 变成 null，必须把 tail 也置为 null。如果不这么做，tail 会指向一个已经不在链表里的旧节点，下一次入队就会把新节点接在一个“孤立节点”后面，整个链表就断了。这个坑我印象很深，当时写一个简易塞车模拟器，每次车辆出队再入队，链表就越来越乱，后来就是 tail 没处理干净。

需要同步记录 size 的原因是：如果不记录 size，判断链表长度只能遍历，O(n)。上面代码直接维护了一个变量，取得长度就是 O(1)，实际开发里非常有用。

4.3 数组队列和链表队列的实战对比

很多初学者会纠结“到底用哪个”。我的建议是看场景：

比如我之前做过一个网络数据包缓冲模块，数据包大小不固定，有的几百字节，有的几百 KB。用数组会面临频繁扩容和内存浪费的问题，换成链式队列后，每个节点按需分配，内存利用率就高了。

反过来，如果你在做 CPU 任务调度，任务对象不大，而且频率极高，数组队列更好。数组天然连续，访问时 CPU 缓存命中率高，吞吐量有明显优势。

5. 利器还是双刃剑：双端队列与循环队列的扩展

5.1 用队列实现栈、用栈实现队列

面试里经常出现“如何用两个栈实现队列”“如何用两个队列实现栈”这种题。这其实不是单纯的炫技，而是考察你对数据结构内部顺序的理解。

用两个栈实现队列的思路是：一个栈（inStack）负责入队，另一个栈（outStack）负责出队。入队时直接压入 inStack；出队时，如果 outStack 为空，把 inStack 所有元素弹出并压入 outStack，再从 outStack 弹出。这样元素的顺序正好反转两次，变成了先进先出。

我第一次觉得这种设计很妙，是在模拟一个打印任务队列的时候。系统外设驱动里就是这么干的，输入缓冲区先积累一批指令，等到输出端准备好了再反转倒出去。

用两个队列实现栈则是另一个思路：入栈时不断入队到非空队列，出栈时将前 n-1 个元素搬到另一个队列，再将最后一个元素出队。核心思想也是“搬移”。这个操作出栈复杂度是 O(n)，并不高效，所以工程里很少真这么做，但用来练习理解队列特性很合适。

5.2 循环队列的空间利用与注意事项

前面提到预留一个空位的判满方案，会浪费一个数组位置。如果我们要求“必须存满 n 个元素”，怎么办？这时需要引入 size 变量。

引入 size 后，判空判满就非常简单了：

public boolean isFull() { return size == capacity; } public boolean isEmpty() { return size == 0; }

实现时，初始 size = 0，入队成功 size++，出队成功 size--。有人觉得多维护一个变量也没那么复杂，确实如此，而且更直观。个别极端并发场景下，size 变量可能会跟 front/rear 出现同步问题，需要配合锁机制或者 CAS 原子操作。但在单线程教学示例里完全够用。

5.3 一个更“能装”的队列扩展思路

如果你还想做工程化扩展，可以考虑给队列加一个阻塞特性：队列满时，入队线程等待；队列空时，出队线程等待。这就是生产者-消费者模型里的基础组件。Java 里的ArrayBlockingQueue、LinkedBlockingQueue就是典型例子。

阻塞队列的底层还是环形数组或者链表，只是多了条件变量和锁。理解普通队列的 front、rear 怎么变化，再去读阻塞队列源码，会轻松非常多。我建议你按这个顺序学习：

1. 手写环形数组队列。
2. 手写链式队列。
3. 给队列加锁，模拟多线程入队出队。
4. 阅读标准库里的阻塞队列源码。

6. 实战演练：任务调度里的队列长什么样

6.1 一个模拟场景：打印任务调度

为了让你体会队列的价值，我举个例子。某培训机构的管理系统里有一个打印任务调度模块，学生提交打印作业，打印机一台，最多排 10 个任务。这就是一个典型的队列场景：先提交的任务先打印。

我用环形队列实现一个简化版：

public class PrintTaskQueue { private String[] tasks = new String[11]; private int front = 0; private int rear = 0; public boolean submit(String task) { if ((rear + 1) % tasks.length == front) { System.out.println("队列已满，任务[" + task + "]提交失败"); return false; } tasks[rear] = task; rear = (rear + 1) % tasks.length; System.out.println("任务[" + task + "]已进入队列"); return true; } public String processNext() { if (front == rear) { System.out.println("队列为空，无需处理"); return null; } String task = tasks[front]; front = (front + 1) % tasks.length; System.out.println("任务[" + task + "]已完成"); return task; } }

这里把长度设为 11，而不是 10，原因就是预留了一个空位来判满。这是新手最容易忽略的点：明明想放 10 个任务，结果数组长度设成 10，永远只能存 9 个，因为有一个位置要留给 rear 作为“空位标记”。

我建议你在自己练习时也把容量和“实际可存元素数”区分开，写个注释说明，不然过半个月回看代码自己都忘了为什么长度多 1。

6.2 参数选择的两个原则

这里其实暴露了两个通用原则：

第一，容量上限一定要定得合理。队列满了之后有两种策略：丢弃新任务，还是阻塞等待。如果是界面点击任务，阻塞会让整个界面卡住，所以通常用丢弃策略并给出提示；如果是后台任务队列，可以用阻塞策略配合线程池。

第二，判空判满逻辑要统一。后台代码判空和判满的公式分别写在两个方法里，如果前后用了两套逻辑，很容易出错。我在重构某段旧代码时就看到过一个队列，判空用 front==rear，判满却用 rear+1==front，没取模，容量小的时候没问题，容量一大、front 超过 rear 时直接判断错误。统一用取模表达式，是上策。

6.3 真实业务里队列的几种变体

业务场景中队列还会变形为：

• 优先级队列：虽然叫队列，但顺序不按入队时间，而是按优先级。底层一般用堆，不是链表。
• 延迟队列：任务要延迟一段时间才能被取出，底层会用时间轮或优先队列。
• 有界队列：队满不允许继续入队，用于流量削峰，后端系统常用。
• 无界队列：内存足够就能一直入队，但要注意内存爆炸。

面试时你提到队列，跟着展开一两个变体的实现思路，会让面试官觉得你真的懂，而不只是背了定义。我在带新人时经常发现，会背 FIFO 的人很多，但能把优先级队列和普通队列区别讲清楚的人不多。关键区别在于：“普通队列严格按入队时间排序，优先级队列按权重排序，底层是堆。” 一句话点到本质。

7. 常见问题与排查技巧实录

7.1 队列“假满”导致元素无法入队

现象：数组明明还有空位，但队列就是提示已满。

排查思路：打印 front 和 rear 的值，观察它们的位置。如果 front 在靠近末尾，rear 已经循环到前面，说明 rear 快追上 front。此时如果已经满足(rear + 1) % len == front，就是真满了，不是假满；如果不是，说明代码里判满逻辑有误，比如忘了取模。

我自己的习惯是写一个debug()方法，把 front、rear、size、容量打印出来：

public void debug() { System.out.println("front=" + front + ", rear=" + rear + ", size=" + size() + ", capacity=" + capacity); }

测试时每操作一步调用一次，很快就能定位问题到底出在入队还是出队。

7.2 链表队列出队后 tail 未置空导致数据错乱

现象：连续出队直到链表为空，再入队新元素，程序报错或者数据顺序不对。

排查思路：断开链表后要检查 head 和 tail。出队到最后一个节点，head 变为 null，这时 tail 也要置为 null。最好在 poll 方法里加一句“如果 head == null，则 tail = null”。这就是最简单的修复。

7.3 泛型数组不能直接创建

现象：在泛型类里写data = new E[capacity]，IDE 直接报错。

原因：Java 的泛型在运行时类型会被擦除，数组却需要运行时确定类型，两者冲突。解决方法是声明Object[]，赋值时转型。这也是上面代码里使用Object[]的原因。初学泛型的人几乎都会遇到这个问题，属于高频小坑。

7.4 取模运算溢出问题

如果你用 C/C++ 写，(rear + 1) % capacity在极少量高并发下不会有大问题，但如果在小容量且多次循环的场景，所有整型溢出都有隐患。建议把循环下标统一用unsigned int或long类型。Java 里则可以把%和&配合位运算优化，当容量设计为 2 的幂时，(rear + 1) & (capacity - 1)等价于取模，且性能更好。

很多高性能框架的环形队列，比如某些 RPC 框架的缓冲区，容量固定设计成 2 的幂，就是因为可以用位运算替代取模，把关键路径的 CPU 周期压到极低。

7.5 多线程环境下队列不安全

现象：单线程跑得好好的，两个线程一入队一出队，偶尔丢数据、死循环。

原因：front、rear 变量的读写不是原子的，也没有锁保护。

解决方案有三种：

• 简单粗暴：方法加锁，性能一般。
• 原子变量 + CAS：适合环形数组队列，无锁。
• 使用现成并发队列：比如ConcurrentLinkedQueue，免去重复造轮子。

我的建议是，教学阶段先把单线程版本的逻辑写稳，再研究并发。很多同学一上来就追无锁并发，结果基础判空逻辑都没搞对，调试起来特别痛苦。

8. 队列在真实开发中的角色与下一步扩展建议

队列应用的范围比我刚学的时候以为的宽太多。消息队列（比如各类 MQ 系统）本质上是分布式队列。操作系统里的进程调度队列、打印队列、网络设备里的数据包队列，全是队列思想。甚至网页前端的任务队列、React 的调度器，底层都在反复使用队列和堆。

如果你已经能把环形数组队列和链式队列手写出来，下一步建议按下面顺序深入：

• 读标准库源码，看ArrayDeque和LinkedList的差异；
• 实现一个简单的阻塞队列，模拟生产者消费者；
• 用队列实现一个 BFS 迷宫寻路算法，你能直观感受到先进先出带来的“层级顺序”；
• 试着写一个固定容量的滑动窗口统计逻辑，会发现很多后端限流组件就是这么干的。

我在实际工作中发现，多数性能问题并不来自某个数据结构选错，而是基础队列的入队出队路径上出现了隐藏拷贝或锁竞争。能把底层每一行代码都弄明白的人，排查这类问题会快很多。

这门课上的“队列”，其实是你理解系统异步化、流控和缓冲机制的钥匙。把它吃透，后面学并发、学消息中间件都会顺手很多。