本文是个人学习笔记,素材来自青岛大学王卓老师的教学视频。
一方面用于学习记录与分享,
另一方面是想让更多的人看到这么好的《数据结构与算法》的学习视频。
如有侵权,请留言作删文处理。
课程视频链接:
数据结构与算法基础–第05周13–3.5队列的表示和实现2–3.5.2队列的顺序表示和实现1
📚 【Week05】13_队列的顺序表示和实现1
队列
顺序队列空栈、入队和出队示意图
❓ 思考:存在什么问题??
设数组大小为 MAXQSIZE,rear = MAXQSIZE 时,发生溢出。
解决假上溢的方法
(1) 将队中元素依次向队头方向移动。
缺点:浪费时间。每移动一次,队中元素都要移动。
(2) 将队空间设想成一个循环的表,即分配给队列的 m 个存储单元可以循环使用。
当 rear 为 maxqsize 时,若向量的开始端空着,又可从头使用空着的空间。
当 front 为 maxqsize 时,也是一样。
就好像下标为 0 的位置是接在下标为 5 的位置后面。
😊 解决假上溢的方法——引入循环队列
base[0] 接在 base[MAXQSIZE - 1] 之后,若 rear + 1 == M,则令 rear = 0;
实现方法:
利用 模运算(mod,C语言中:%)。
插入元素:
Q.base[Q.rear] = x;
Q.rear = (Q.rear + 1) % MAXQSIZE;
删除元素:
x = Q.base[s.front];
Q.front = (Q.front + 1) % MAXQSIZE;
循环队列:循环使用为队列分配的存储空间。
循环队列入队和出队
❓ 思考:循环队列时会出现队空:front == rear,队满:front == rear,如何判断队空和队满?
解决方案:
(1) 另外设一个标志以区别队空和队满
(2) 另设一个变量,记录元素个数
(3) 少用一个元素空间