队列、循环队列与层次处理

考点定位

本课深化 队列、循环队列与层次处理。408作答必须同时给出数据结构表示、算法过程、不变量、复杂度和边界条件。

结构与取舍

队列按先进先出处理层次事件。循环队列必须通过牺牲一个槽、额外size或tag区分队空与队满。

算法推演

牺牲一槽时：队空 front==rear；队满 (rear+1)%m==front；元素个数 (rear-front+m)%m。

把算法写成“初始化—循环条件—状态更新—终止输出”。若使用递归、队列、堆或并查集，要指出其中保存的状态及何时失效。

正确性不变量

任何入队和出队后，front、rear都保持在[0,m-1]，逻辑顺序不受物理回绕影响。

初始化时不变量成立；一次迭代保持它；循环结束时它与终止条件共同推出答案。这是算法题证明的最短主线。

复杂度与边界

时间复杂度必须按输入规模和存储结构计算，不能只报结论。严格边界：必须明确题目采用哪一种判空判满约定，再计算容量。

随课应用

长度m=8且采用“牺牲一个存储单元”方案的循环队列，最多保存多少个元素？

先独立计算或编码，再完成单选与多选。代码题从标准输入读取并写到标准输出，不得硬编码样例；数值题需写出中间状态。