队列

队列是与栈并列的另一种操作受限的线性表，遵循”先进先出”（FIFO）原则。从排队买奶茶到操作系统的任务调度、从图的广度优先搜索到二叉树的层序遍历，队列的身影无处不在。本章围绕队列的两种存储实现（顺序与链式）、循环队列的”假溢出”问题，以及双端队列、优先级队列等变体展开。读完本节，你将能够理解队列的定义、特点与基本操作、掌握循环队列的存储结构、判空判满条件及入队出队实现、理解普通顺序队列”假溢出”问题及循环队列的解决思路、掌握链式队列的实现与出队注意事项、了解双端队列、优先级队列的特点与适用场景、掌握队列在 BFS、层序遍历等场景中的应用。

本章要解决的问题

如何保证”先来先服务”？普通顺序队列存在”假溢出”的空间浪费，循环队列通过取模实现首尾相连；链式队列则彻底摆脱了空间上限。此外，双端队列如何结合栈与队列的优点、优先级队列如何”插队”，都是本章要理清的问题。

基础路线：基本概念 → 顺序队列 → 链式队列，先掌握两种存储实现。

进阶路线：双端队列与优先级队列 → 经典应用 → 总结，理解队列的变体与实际价值。