之前讲栈是 “先进后出的叠盘子”，而队列是 “先进先出的排队”—— 比如外卖订单 “先下单先处理”、消息推送 “先发送先接收”，核心是 “只能从队尾加、队头删”。这篇和栈的实现逻辑对齐，分别用循环数组（解决普通数组假满问题） 和链表（无容量限制） 造一个 “订单队列”，每步讲清 “结构定义、内存变化、操作执行”，看完你就能自己写队列。
一、用循环数组实现队列：3 步造一个 “高效缓冲队列”
普通数组实现队列有个致命问题：“队尾满了但队头有空位”（比如数组存了 3 个订单，队头删 1 个后，队尾还是满的，没法再存），而循环数组通过 “指针循环” 解决这个问题，是项目里 “固定容量缓冲” 的首选（比如消息中间件的本地缓冲）。
1. 第一步：定义循环数组队列的 “骨架”（数据结构）
要实现一个存订单 ID 的队列，需要 4 个关键部分：
数组 data：存订单 ID（int 类型，每个占 4 字节）；
队头指针 front：记录 “取数据的位置”（索引）；
队尾指针 rear：记录 “存数据的位置”（索引）；
容量 capacity：数组大小（必须比实际最大存储数大 1，预留 1 个空位区分 “满” 和 “空”）。
用代码表示（Java 伪代码，简化好懂）：
// 循环数组队列的结构定义
class CircleArrayQueue {
int\[] data; // 存订单ID的数组
int front; // 队头指针（取数据的索引）
int rear; // 队尾指针（存数据的索引）
int capacity; // 数组容量（实际能存capacity-1个数据）
// 构造方法：初始化队列
public CircleArrayQueue(int capacity) {
this.capacity = capacity;
this.data = new int\[capacity]; // 申请capacity大小的数组
this.front = 0; // 队头初始为0（未取数据）
this.rear = 0; // 队尾初始为0（未存数据）
}
}
初始化后的内存状态：
假设初始化容量为 4 的队列（
new CircleArrayQueue(4)），实际存 3 个订单，数组内存地址从0x500开始；内存项格式：【数组内存地址】 | 【数组索引】 | 【存储的订单 ID（初始值）】 | 【队头 front】 | 【队尾 rear】 | 【状态说明】
具体内存项：
0x500 | 0 | 0 | 0 | 0 | 空队（front==rear）
0x504 | 1 | 0 | 0 | 0 | 空
0x508 | 2 | 0 | 0 | 0 | 空
0x50C | 3 | 0 | 0 | 0 | 预留空位（区分满 / 空）
2. 第二步：实现核心操作 1—— 入队（offer）：往队尾存订单
入队是 “把订单 ID 存到 rear 位置”，核心是 “先判满，再存数据，最后循环移动 rear”—— 因为要避免 “假满”，rear 移动时用(rear+1)%capacity实现 “到数组末尾后循环到开头”。
入队后的内存变化（存第一个订单 ID 1001，文本行对齐描述）：
内存项格式：【数组内存地址】 | 【数组索引】 | 【存储的订单 ID】 | 【队头 front】 | 【队尾 rear】 | 【状态说明】
具体内存项：
0x500 | 0 | 1001 | 0 | 1 | 存 1 个订单，队尾指向 1
0x504 | 1 | 0 | 0 | 1 | 空
0x508 | 2 | 0 | 0 | 1 | 空
0x50C | 3 | 0 | 0 | 1 | 预留空位
再入队 2 个订单（1002、1003）后的内存变化：
内存项格式：【数组内存地址】 | 【数组索引】 | 【存储的订单 ID】 | 【队头 front】 | 【队尾 rear】 | 【状态说明】
具体内存项：
0x500 | 0 | 1001 | 0 | 3 | 满队（(3+1)%4=0==front=0）
0x504 | 1 | 1002 | 0 | 3 | 已存数据
0x508 | 2 | 1003 | 0 | 3 | 已存数据
0x50C | 3 | 0 | 0 | 3 | 预留空位（满队判断位）
入队的代码实现：
// 入队：往队尾存订单ID，成功返回true，满队返回false
public boolean offer(int orderId) {
// 判满：(rear+1)%capacity == front 表示满队
if ((rear + 1) % capacity == front) {
System.out.println("队列满了，不能再存订单了");
return false;
}
data\[rear] = orderId; // 存数据到队尾
rear = (rear + 1) % capacity; // 循环移动队尾指针
return true;
}
3. 第三步：实现核心操作 2—— 出队（poll）：从队头取订单
出队是 “从 front 位置取订单 ID”，核心是 “先判空，再取数据，最后循环移动 front”—— 取完后不用清空原数据（下次入队会覆盖），只需移动指针表示 “该位置已失效”。
出队后的内存变化（取走订单 1001，文本行对齐描述）：
内存项格式：【数组内存地址】 | 【数组索引】 | 【存储的订单 ID（未覆盖）】 | 【队头 front】 | 【队尾 rear】 | 【状态说明】
具体内存项：
0x500 | 0 | 1001 | 1 | 3 | 数据还在，但队列不认可（下次入队会覆盖）
0x504 | 1 | 1002 | 1 | 3 | 队头指向 1（下次取这个）
0x508 | 2 | 1003 | 1 | 3 | 已存数据
0x50C | 3 | 0 | 1 | 3 | 预留空位
再入队 1 个订单（1004）后的内存变化：
内存项格式：【数组内存地址】 | 【数组索引】 | 【存储的订单 ID】 | 【队头 front】 | 【队尾 rear】 | 【状态说明】
具体内存项：
0x500 | 0 | 1001 | 1 | 0 | 空（下次入队覆盖这里）
0x504 | 1 | 1002 | 1 | 0 | 队头（下次取这个）
0x508 | 2 | 1003 | 1 | 0 | 已存数据
0x50C | 3 | 1004 | 1 | 0 | 已存数据
出队的代码实现：
// 出队：从队头取订单ID，空队返回null
public Integer poll() {
// 判空：front == rear 表示空队
if (front == rear) {
System.out.println("队列为空，没订单可取");
return null;
}
int orderId = data\[front]; // 取队头数据
front = (front + 1) % capacity; // 循环移动队头指针
return orderId;
}
4. 循环数组队列的其他关键操作（判空、判满、取队头）
判空（isEmpty）：front == rear → 空队；
判满（isFull）：(rear+1)% capacity == front → 满队；
取队头（peek）：和出队类似，只取数据不移动 front（比如 “看最早的订单是谁，但暂不取”）。
代码实现：
// 判空：队列是否为空
public boolean isEmpty() {
return front == rear;
}
// 判满：队列是否已满
public boolean isFull() {
return (rear + 1) % capacity == front;
}
// 取队头：看最早的订单ID，不取出
public Integer peek() {
if (isEmpty()) {
System.out.println("队列为空，没订单可看");
return null;
}
return data\[front]; // 直接返回队头数据，不动指针
}
二、用链表实现队列：3 步造一个 “无容量限制的订单队列”
链表实现队列的核心是 “用单链表存数据，队头指向链表头（出队快），队尾指向链表尾（入队快）”—— 不用像单链表那样 “入队要遍历找尾”，也没有容量限制，适合 “订单量不确定” 的场景（比如外卖高峰期的订单队列）。
1. 第一步：定义链表队列的 “骨架”（节点 + 队列结构）
需要两个部分：
链表节点（Node）：存单个订单 ID 和下一个节点的指针；
链表队列（LinkedQueue）：用 front（队头）和 rear（队尾）指针分别指向链表头和尾，避免入队遍历。
用代码表示（Java 伪代码）：
// 1. 链表节点的结构：存订单ID+指向下一个节点的指针
class Node {
int orderId; // 订单ID（数据域）
Node next; // 指向下一个节点的指针（地址）
public Node(int orderId) {
this.orderId = orderId;
this.next = null; // 新节点默认无后续节点
}
}
// 2. 链表队列的结构：队头（取）+ 队尾（存）
class LinkedQueue {
Node front; // 队头指针（指向链表头，取数据）
Node rear; // 队尾指针（指向链表尾，存数据）
int size; // 队列大小（可选，方便统计订单数）
// 初始化队列：空队时front和rear都为null
public LinkedQueue() {
this.front = null;
this.rear = null;
this.size = 0;
}
}
初始化后的内存状态：
内存项格式：【队列对象】 | 【队头 front】 | 【队尾 rear】 | 【队列大小 size】 | 【状态说明】
具体内存项：
- LinkedQueue | null | null | 0 | 空队，无节点
2. 第二步：实现核心操作 1—— 入队（offer）：往队尾加订单节点
链表队列的入队是 “在链表尾加新节点”，核心是 “分空队和非空队处理”：
空队：新节点既是头也是尾（front 和 rear 都指向它）；
非空队：尾节点的 next 指向新节点，再更新 rear 为新节点（不用遍历找尾）。
入队后的内存变化（存第一个订单 ID 1001，文本行对齐描述）：
内存项格式：【队列对象】 | 【队头 front】 | 【队尾 rear】 | 【节点内存地址】 | 【节点 orderId】 | 【节点 next】 | 【size】 | 【状态说明】
具体内存项：
- LinkedQueue | 0x300 | 0x300 | 0x300 | 1001 | null | 1 | 1 个节点，头尾指向同一节点
再入队 2 个订单（1002、1003）后的内存变化：
内存项格式：【队列对象】 | 【队头 front】 | 【队尾 rear】 | 【节点内存地址】 | 【节点 orderId】 | 【节点 next】 | 【size】 | 【状态说明】
具体内存项：
LinkedQueue | 0x300 | 0x318 | 0x300 | 1001 | 0x30C | 3 | 队头（最早订单）
LinkedQueue | 0x300 | 0x318 | 0x30C | 1002 | 0x318 | 3 | 中间节点
LinkedQueue | 0x300 | 0x318 | 0x318 | 1003 | null | 3 | 队尾（最新订单）
入队的代码实现：
// 入队：往队尾加订单节点，无容量限制
public void offer(int orderId) {
// 1. 新建订单节点
Node newNode = new Node(orderId);
// 2. 空队：头尾都指向新节点
if (front == null) {
front = newNode;
rear = newNode;
} else {
// 非空队：尾节点的next指向新节点，更新队尾
rear.next = newNode;
rear = newNode;
}
size++; // 订单数+1
}
3. 第三步：实现核心操作 2—— 出队（poll）：从队头删订单节点
链表队列的出队是 “删除链表头节点”，核心是 “分单节点和多节点处理”：
单节点（size=1）：删完后队列空，front 和 rear 都设为 null；
多节点：更新 front 为原头节点的 next，原头节点失效（被垃圾回收）。
出队后的内存变化（取走订单 1001，文本行对齐描述）：
内存项格式：【队列对象】 | 【队头 front】 | 【队尾 rear】 | 【节点内存地址】 | 【节点 orderId】 | 【节点 next】 | 【size】 | 【状态说明】
具体内存项：
LinkedQueue | 0x30C | 0x318 | 0x300 | 1001 | 0x30C | 2 | 垃圾内存（无指针指向）
LinkedQueue | 0x30C | 0x318 | 0x30C | 1002 | 0x318 | 2 | 新队头（下次取这个）
LinkedQueue | 0x30C | 0x318 | 0x318 | 1003 | null | 2 | 队尾
出队的代码实现：
// 出队：从队头取订单，空队返回null
public Integer poll() {
// 判空：front==null表示空队
if (front == null) {
System.out.println("队列为空，没订单可取");
return null;
}
// 取队头数据
int orderId = front.orderId;
// 单节点处理：删完后空队
if (front == rear) {
front = null;
rear = null;
} else {
// 多节点：更新队头为下一个节点
front = front.next;
}
size--; // 订单数-1
return orderId;
}
4. 链表队列的其他关键操作（判空、取队头、查大小）
判空（isEmpty）：front == null → 空队；
取队头（peek）：只取头节点数据，不删节点；
查大小（getSize）：返回 size，方便统计当前排队订单数。
代码实现：
// 判空：队列是否为空
public boolean isEmpty() {
return front == null;
}
// 取队头：看最早的订单，不取出
public Integer peek() {
if (isEmpty()) {
System.out.println("队列为空，没订单可看");
return null;
}
return front.orderId; // 直接返回头节点数据
}
// 查队列大小：当前有多少个排队订单
public int getSize() {
return size;
}
三、循环数组队列 vs 链表队列：核心区别和选型建议
两种实现各有优劣，选对了能让项目性能提升 50%，关键看 “是否知道最大容量” 和 “是否需要灵活扩展”：
| 对比维度 | 循环数组队列 | 链表队列 |
|---|---|---|
| 容量限制 | 有（需提前确定 capacity，实际存 capacity-1 个数据） | 无（内存够就可一直存，适合订单量波动大的场景） |
| 内存开销 | 低（只有数组，无额外指针开销） | 高（每个节点多 8 字节 next 指针，且有 front/rear 指针） |
| 操作速度 | 快（只动指针，数组连续内存，缓存友好） | 稍慢（需新建节点，指针跳转，离散内存） |
| 实现复杂度 | 稍复杂（需处理指针循环和满 / 空判断） | 简单（只需处理头尾指针，无循环逻辑） |
| 适用场景 | 固定容量缓冲（如消息中间件本地缓存、设备数据采集缓冲） | 灵活扩展场景（如外卖订单队列、APP 消息推送队列） |
选型建议：
如果你知道 “最多存多少数据”（比如 “本地缓冲最多存 1000 条消息”）→ 用循环数组队列，速度快、省内存；
如果你不知道 “数据量上限”（比如 “外卖高峰期可能有 10 万单排队”）→ 用链表队列，无容量限制，不会溢出；
如果你需要 “快速统计数据量”→ 链表队列（size 变量直接获取），循环数组队列需计算
(rear-front+capacity)%capacity。
四、主流高级语言的队列对象说明（项目实战用）
不同语言封装了现成的队列类，不用自己实现，以下是 Java、C#、QT 中 “项目必用” 的队列类型，含底层实现和核心用法：
1. Java 语言
| 队列类名 | 底层实现 | 核心特点 | 常用方法 | 适用场景 |
|---|---|---|---|---|
java.util.LinkedList |
双向链表 | 实现 Queue 接口，无容量限制，线程不安全 | offer ()（入队）、poll ()（出队）、peek ()（取队头） | 普通业务队列（如订单排队、消息推送，非高并发） |
java.util.ArrayDeque |
循环数组 | 实现 Deque 接口，无容量限制（自动扩容），线程不安全，速度比 LinkedList 快 | offer()、poll()、peek() | 高性能非并发队列（如本地缓存队列、数据处理缓冲） |
java.util.concurrent.LinkedBlockingQueue |
双向链表（阻塞队列） | 有界 / 无界可选，线程安全（支持多线程入队出队），满队时入队阻塞、空队时出队阻塞 | put ()（阻塞入队）、take ()（阻塞出队）、offer () | 高并发场景（如多线程任务调度、分布式消息消费） |
实战示例（Java 普通订单队列）：
// 用LinkedList实现普通订单队列
Queue\<Integer> orderQueue = new LinkedList<>();
orderQueue.offer(1001); // 入队订单1001
orderQueue.offer(1002); // 入队订单1002
System.out.println(orderQueue.poll()); // 出队1001（最早订单）
System.out.println(orderQueue.peek()); // 取队头1002（不出队）
2. C# 语言
| 队列类名 | 底层实现 | 核心特点 | 常用方法 | 适用场景 |
|---|---|---|---|---|
System.Collections.Queue |
数组（自动扩容） | 非泛型，存 object 类型，线程不安全，无容量限制 | Enqueue ()（入队）、Dequeue ()（出队）、Peek ()（取队头） | 旧项目非泛型队列（如存混合类型数据） |
System.Collections.Generic.Queue<T> |
数组（自动扩容） | 泛型（如 Queue），线程不安全，无容量限制，性能高 | Enqueue()、Dequeue()、Peek() | 新项目泛型队列（如订单 ID 队列、用户 ID 队列） |
System.Collections.Concurrent.ConcurrentQueue<T> |
链表（并发安全） | 泛型，线程安全（无锁设计），无容量限制，支持高并发 | Enqueue ()、TryDequeue ()（尝试出队，避免阻塞） | 高并发场景（如多线程日志收集、并发任务处理） |
实战示例（C# 泛型订单队列）：
// 用Queue\<int>实现泛型订单队列
Queue\<int> orderQueue = new Queue\<int>();
orderQueue.Enqueue(1001); // 入队订单1001
orderQueue.Enqueue(1002); // 入队订单1002
Console.WriteLine(orderQueue.Dequeue()); // 出队1001
Console.WriteLine(orderQueue.Peek()); // 取队头1002
3. QT 框架（C++）
| 队列类名 | 底层实现 | 核心特点 | 常用方法 | 适用场景 |
|---|---|---|---|---|
QQueue<T> |
动态数组 | 泛型（如 QQueue），线程不安全，无容量限制（自动扩容） | enqueue ()（入队）、dequeue ()（出队）、head ()（取队头） | QT 桌面应用普通队列（如界面事件缓冲、数据接收队列） |
QConcurrentQueue<T> |
链表（并发安全） | 泛型，线程安全（支持多线程），无容量限制，属于 QT Concurrent 模块 | enqueue ()、tryDequeue ()（尝试出队） | QT 高并发场景（如多线程数据采集、网络消息处理） |
QList<T>（模拟队列） |
动态数组 | 虽为列表，但可通过 append ()（入队）、takeFirst ()（出队）模拟队列，线程不安全 | append ()、takeFirst ()、first ()（取队头） | 简单场景临时模拟队列（如少量数据处理） |
实战示例（QT 桌面应用订单队列）：
// 用QQueue\<int>实现QT订单队列
QQueue\<int> orderQueue;
orderQueue.enqueue(1001); // 入队订单1001
orderQueue.enqueue(1002); // 入队订单1002
qDebug() << orderQueue.dequeue(); // 出队1001
qDebug() << orderQueue.head(); // 取队头1002
最后：一句话搞懂队列的实现本质
循环数组队列：用 “连续内存 + 指针循环” 实现先进先出，解决普通数组假满问题，适合固定容量场景；
链表队列：用 “离散节点 + 头尾指针” 实现先进先出，无容量限制，适合灵活扩展场景；
高级语言队列类：本质是封装了上述两种实现，项目中优先用现成类，避免重复造轮子，重点关注 “是否线程安全” 和 “容量限制”。
搞懂这些，你在做 “订单排队”“消息推送”“数据缓冲” 时，就能精准选对队列类型，写出高效且符合项目需求的代码。
