队列
队列是与栈并列的另一种操作受限的线性表，遵循”先进先出”（FIFO）原则。从排队买奶茶到操作系统的任务调度、从图的广度优先搜索到二叉树的层序遍历，队列的身影无处不在。本章围绕队列的两种存储实现（顺序与链式）、循环队列的”假溢出”问题，以及双端队列、优先级队列等变体展开。
本章要解决的问题
如何保证”先来先服务”？普通顺序队列存在”假溢出”的空间浪费，循环队列通过取模实现首尾相连；链式队列则彻底摆脱了空间上限。此外，双端队列如何结合栈与队列的优点、优先级队列如何”插队”，都是本章要理清的问题。
学习目标
- 理解队列的定义、特点与基本操作
- 掌握循环队列的存储结构、判空判满条件及入队出队实现
- 理解普通顺序队列”假溢出”问题及循环队列的解决思路
- 掌握链式队列的实现与出队注意事项
- 了解双端队列、优先级队列的特点与适用场景
- 掌握队列在 BFS、层序遍历等场景中的应用
章节导航
| 子章节 | 核心内容 |
|---|---|
| 基本概念 | 队列定义、特点、基本操作 |
| 顺序队列 | 假溢出、循环队列、判空判满、入队出队 |
| 链式队列 | 存储结构、初始化、入队出队 |
| 双端队列与优先级队列 | Deque 分类、与栈队列关系、堆实现 |
| 经典应用 | BFS、缓冲区、任务调度、趣味事实 |
| 总结 | 术语对照、核心要点 |
建议阅读顺序
基础路线：基本概念 → 顺序队列 → 链式队列，先掌握两种存储实现。
进阶路线：双端队列与优先级队列 → 经典应用 → 总结，理解队列的变体与实际价值。
循环队列的判空判满条件是本章核心考点（
front == rear 判空、(rear+1)%MaxSize == front 判满），务必结合代码理清”牺牲一个存储单元”的约定。链式队列出队删除最后一个元素时需更新 rear 指针，也是常考易错点。