1. 简介
在数据结构中，队列（Queue） 是一种非常基础且广泛使用的结构。根据使用场景和操作方式的不同，队列可以分为多种类型。本文将介绍四种常见的队列类型，并结合实际应用场景进行说明，帮助你更深入地理解它们的特点和用途。
2. 普通队列（Simple Queue）
普通队列是最基础的队列形式，遵循“先进先出（FIFO）”原则。
- 入队（Enqueue）：发生在队列尾部（rear）
- 出队（Dequeue）：发生在队列头部（front）
结构示意如下：
应用场景
普通队列适用于以下场景：
- 进程调度
- 磁盘调度
- 内存管理
- IO 缓冲区
- 管道（Pipes）
- 客服电话系统
- 中断处理
踩坑提醒 ⚠️
普通队列的一个明显缺点是：当队列头部有元素被出队后，前面的空间无法被再次利用，容易造成空间浪费。
3. 循环队列（Circular Queue）
循环队列是对普通队列的一种优化，解决了空间浪费的问题。它将队列首尾相连，形成一个环形结构：
- 当尾部指针到达数组末尾时，可以“绕回”数组开头继续插入
- 只要队列中存在空位，就可以继续插入元素
结构示意如下：
应用场景
- 交通信号灯的切换控制
- 替代普通队列用于上述所有场景，提升内存利用率
优势 ✅
- 更好的内存利用率
- 避免普通队列中出现的“假满”现象（即队列未满但无法插入）
4. 优先队列（Priority Queue）
优先队列是一种带有优先级的队列结构。每个元素都有一个优先级，出队时总是优先级最高的元素先出队。
- 入队按到达顺序插入
- 出队根据优先级决定（高优先级先出）
- 若优先级相同，则按 FIFO 原则处理
结构示意如下：
应用场景
- 中断处理
- Prim 最小生成树算法
- Dijkstra 最短路径算法
- A* 寻路算法
- 堆排序（Heap Sort）
- 霍夫曼编码（Huffman Coding）
实现方式
通常使用 堆（Heap） 来实现优先队列，以保证插入和删除操作的效率。
5. 双端队列（Deque - Double-Ended Queue）
双端队列允许在队列的两端进行插入和删除操作：
- 可以从头部或尾部入队
- 也可以从头部或尾部出队
结构示意如下：
应用场景
- 浏览历史记录
- 撤销操作（Undo）
- A-Steal 工作窃取调度算法
- 实现栈或普通队列
特殊变种
5.1 输入受限双端队列（Input-Restricted Deque）
- 只能在尾部入队
- 可以在头部和尾部出队
结构示意如下：
5.2 输出受限双端队列（Output-Restricted Deque）
- 可以在头部和尾部入队
- 只能在头部出队
结构示意如下：
6. 总结
我们介绍了四种常见的队列类型及其应用场景：
| 队列类型 | 特点 | 常见用途 |
|---|---|---|
| 普通队列 | FIFO，入队尾，出队头 | 进程调度、缓冲区管理 |
| 循环队列 | 首尾相连，空间复用 | 交通灯控制、替代普通队列 |
| 优先队列 | 按优先级出队 | 算法优化、中断处理 |
| 双端队列 | 头尾均可操作 | 历史记录、撤销操作、调度算法 |
掌握这些队列类型有助于你在实际开发中选择最适合的数据结构，从而写出更高效、更健壮的程序。