讲环形队列前,先说一下顺序队列的问题
●顺序队列的问题
•用rear == MaxSize -1 作为队满的条件有缺陷
•可能队列为空 , 但仍然满足该条件,进队时出现 "上溢出" 是一种假溢出
顺序队列的问题,我们用环形队列来解决
●环形队列的对策
•充分地使用数组中的存储空间 , 把数组的前端和后端连接起来 , 形成一个环形的顺序表 , 即把存储队列元素的表从逻辑上看成一个环
•得到环形队列或循环队列
环形队列的四要素
(1)初始的时候 ,我们让队首指针 和 队尾指针都指向 位序为 0 处 ,(这里为了便于判断队满和队空,所以直接指向队列开头)
(2) 元素入队 , 我们让队尾指针向后依次移动 ,然后入队新元素
(3) 当队空的时候, 队首指针 front 和队尾指针 rear 重合 ,那当队满的时候 ,就不能重合了,如上图 3 所示 , 到队列位序为 MaxSize-1 处 ,就代表队满了
(4) 当要出队时 , front 向后移动 ,并删除指向的队元素 , front 其后面的元素就是队首元素(注:front指向的是要删除处理的元素 , 所以每次处理完都是指向队首元素的前一个位置 , 当要出队元素时 , front 才向后移动,并进行操作)
//因为我们定义的是循环队列 , 当我们循环执行 入队 和 出队 操作的时候 , front 和 rear 的位序会一直递增 ,但是我们的最大的位序标号是 MaxSize-1 , 所以 当 rear 到了 MaxSize-1 的时候 , 如果队不满(rear 不指向 0 ,已经腾出位置了) ,我们就需要将 rear 重置成 0 了,然后接着插入, 那怎么进行操作呢 ?
就像我们操场跑圈 ,跑完一圈 ,我们的公里数已经增加 ,但是我们操场一圈的公里数是固定的 ,我们需要从头跑 ,此时我们已经跑了操场长度的 整数倍 ,所以每次我们要重返起点的时候,我们只需要把我们跑的总公里数 对 操场长度取余就可以了, 我们就可以从新开始 , 保证位序不会错乱 , rear 也是同理的
//至于数组最大存储量 为MaxSize ,为什么队列只存储 MaXSize-1 个元素 , 是因为我们队空的标志是 front 和 rear 重合 . 并且 rear 始终指向 队列头元素 的前一个位置 ,意思就是 rear 指向的地方 逻辑上空的(意思就是可覆盖的,不属于队列了已经) , 当 队列里面存储了 MaxSize-1 个元素的时候 , 我们的 rear 指向队列最后一个元素 , rear 下一个位置 是 front 指向的 , 我们不能再添加元素了 ,因为 front 会删除其指向的元素 , 并且如果再添加元素 rear 会和 front 重合 ,这时我们就无法区分 此时是队空还是队满 ,如下图(这里和我们的定义有关, front 必须为 队列头元素的前一个位置 ,当删除元素的时候才往后移动到要删除的地方 ,所以 front 会占用 数组的一个空间 , 其会删除其指向的元素, 所以 队列数组最大存储为 MaxSize -1 , front 指向的元素是出队的元素 ,已经不属于队列 )
// 如果队列不满 ,我们 就把 rear 向后移动一位 ,然后插入新元素即可,取余和上面同理,为了让 rear 逻辑上的数字和 数组位序 保持一致
//如果队列不为空 , 就把front 移动到队列的第一个元素, 然后取出 front 处的元素,存入 e,取余和上面同理,
定义队列数据结构:
初始化队列 InitQueue(q)
●构造一个空队列 , 将 front 和 rear 指针均设置成初始状态即 0 值.
代码实现:
销毁队列 ClearQueue(&q)
●释放队列 q 占用的存储空间
代码实现:
判断队列是否为空QueueEmpty(q)
●若队列q 满足q->front == q->rear 条件,则返回 true ;否则返回false.
下面开始代码实现:
进队列enQueue(q,e)
●在队列不满的条件下,先将队尾指针rear 循环増一, 然后再将元素添加到该位置
代码实现:
出队列 deQueue(q,e)
●在队列q 不为空的条件下,将队首指针front 循环増 1 ,并将该位置的元素传入e
代码实现:
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
如需转载请保留出处：https://bianchenghao.cn/bian-cheng-ri-ji/51222.html