跳到正文

3.2.2 队列的顺序实现

40 分钟

3.2.2 循环队列:用取模复用数组前部空间

普通顺序队列若只让 frontrear 向右移动,会出现前部空闲却无法入队的“假溢出”。循环队列把下一个位置定义为 (index+1)%CAP,使下标在末端回到 0。

常见约定是 front 指向队头元素,rear 指向下一个可写位置,并牺牲一个槽位区分空与满:空条件 front==rear,满条件 (rear+1)%CAP==front,元素数 (rear-front+CAP)%CAP

int enqueue(Queue*q,int x){if((q->rear+1)%CAP==q->front)return 0;
 q->data[q->rear]=x; q->rear=(q->rear+1)%CAP; return 1;}
int dequeue(Queue*q,int*x){if(q->front==q->rear)return 0;
 *x=q->data[q->front]; q->front=(q->front+1)%CAP; return 1;}

容量为 5 的数组按此约定最多存 4 个元素。若必须用满全部槽位,可额外维护 size 或最近一次操作标志,此时满条件相应改变,不能混用公式。

手工推演:CAP=5,front=3,rear=1,有效下标顺序为 3、4、0,元素数 (1-3+5)%5=3。再入队写下标 1,rear 变 2,此时 (2+1)%5==3,队满。

错解反馈:用 rear==CAP 判满会错过回绕;用 rear-front 直接算长度可能得到负数;既牺牲槽位又声称容量 5 可存 5 个,约定自相矛盾。

迁移题:CAP=8,front=6,rear=2 时元素数是多少?答案 4,对应下标 6、7、0、1。独立验收:能用同一约定写出空、满、长度、入队、出队五个公式,并推演两次回绕。

小纸条

计算:CAP=8,front=6,rear=2,牺牲一格约定下有几个元素?

登录 后可看答案

Practice

本课练习

0

先独立作答再提交;编程题会在隔离沙箱中真实编译、运行并对拍。

本课练习正在补齐,暂不应标记为完成。