循环队列的存储空间为(0:59),初始状态为空,经过一系列正常的入队与退队操作后,front=25

2020-06-21 综合 381阅读
设有一个用数组Q[1..m]表示的环形队列,约定f为当前队头元素在数组中的位置,r为队尾元素的后一位置(按顺时针方向),若队列非空,则计算队列中元素个数的公式应为 (m+r-f)mod m
(60+24-25)mod 60 =59
分析:
 对于顺序队列,头指针和尾指针开始时刻都指向数组的0下标元素。当加入新元素以后,尾指针向后移动,指向最后一个元素的下一个位置。
但是尾指针不能超过数组的最大范围。当有元素删除时,头指针向后移动。但是头指针不能低于数组的0下标。这样就会引入一种“假溢出”现象,
数组中存在空余的空间,但是由于尾指针已经在最大位置,不能加入元素。
    循环队列就可以用来解决 假溢出 问题, 当队列后面的满了,就从头在开始,形成头尾相接的循环. 
    出现的问题:  front=rear即头指针和尾指针相等,但是对应两种情况:一种是队列是空,一种是队列是满。
    所以,我们定义循环队列中空出一个位置为满队列状态。front指向头元素,rear指向尾元素的下一个位置。
    那么循环队列的长度如何计算呢? 
     情况一:  当rear大于front时,循环队列的长度:rear-front
    情况二:  当rear小于front时,循环队列的长度:分为两部分计算 0+rear   和   Quesize-front  ,  将两部分的长度合并到一起即为: rear-front+Quesize
    所以将两种情况合为一种,即为:  总长度是(rear-front+Quesize)%Quesize
声明:你问我答网所有作品(图文、音视频)均由用户自行上传分享,仅供网友学习交流。若您的权利被侵害,请联系fangmu6661024@163.com