3.2.2.1 循环队列

教材导航 · 第3章

原书定位

印刷页P77起,对应PDF第89页。下文为目视整理的知识提要;完整内容见原书对照。

设数组长度 MM,front 指队头,rear 指队尾后一位置,牺牲一个单元区分空满:

空:front=rear,满:(rear+1) mod M=front\text{空}:front=rear,\qquad\text{满}:(rear+1)\bmod M=front 长度=(rear−front+M) mod M\text{长度}=(rear-front+M)\bmod M

入队后 rear=(rear+1)%M,出队后 front=(front+1)%M;最大可存 M−1M-1 项,操作均为 O(1)O(1)。

也可另设 size 或 tag 区分空满,使用全部 MM 个单元。计数法空时 size=0、满时 size=M;标志法在头尾相等时结合最近一次成功操作判断。指针定义改变时,应重新推导条件。

图3.7 循环队列出入队

图3.7 循环队列出入队,原书P77。

对应练习

3.2 节习题与逐题解析

关联知识

原书对照

展开原书对照截图

原书对照,原书P77,PDF第89页

原书对照,原书P78,PDF第90页