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，入队尾，出队头
进程调度、缓冲区管理
循环队列
首尾相连，空间复用
交通灯控制、替代普通队列
优先队列
按优先级出队
算法优化、中断处理
双端队列
头尾均可操作
历史记录、撤销操作、调度算法
掌握这些队列类型有助于你在实际开发中选择最适合的数据结构，从而写出更高效、更健壮的程序。