思路分析:

一、front就指向队列的第一个元素,也就是说,arr[front]就是队列的第一个元素

 

二、rear就是指向队列的最后一个元素的后一个位置,我们需要空出这个rear指向的空间(牺牲这个空间)

 

三、现在环形队列中,当队列满时,条件为:( rear + 1 ) % maxSize = front 

  原本队列满的条件是 rear = maxSize – 1 

  我的解释是:

 

所以实际上这个环形队列实际的存储数据的长度(从0开始到x)为 maxSize – 2 ,也就是 这个空间的大小-1 ,剩下的这个空间被牺牲掉了,用来做判断这个环形队列是不是满的!

当然,上面的图从1开始是不严谨的,应该从0开始,从1开始只是我画的时候方便=-=

 

四、当队列为空的时候,条件仍然是 rear = front 

 

五、队列中有效的数据的个数为( rear + maxSize – fron ) % maxSize 

 

 

 这个公式的解释可以这样理解,首先rear加上maxSize也就是从数组的0位置开始到rear位置加上了容量大小,此时减去一个front就相当于数组中将这个占有数据的值往下推,推到从0位置到rear-front,

此时对maxSize取余就是相当于一个大于maxSize的数减去了一个maxSize所得到的余数,就是数组中有效存储的个数。

把这个公式这样写更好理解:

          (  rear – front + maxSize ) % maxSize 

          1、先不考虑这个环存取数据绕过一圈以上了,那么肯定有rear>front,那么rear-front就是存的有效个数

          2、如果这个环存取数据也就rear和front通过一系列位移不知道是rear大还是front大

          3、此时加上maxSize,就一定可以保证rear-front是一个正数,此时对maxSize取余可以得到有效个数了

          

 

 

 

 

 

 

 

  

 

原文地址:http://www.cnblogs.com/leehl8016/p/16817362.html

1. 本站所有资源来源于用户上传和网络,如有侵权请邮件联系站长! 2. 分享目的仅供大家学习和交流,请务用于商业用途! 3. 如果你也有好源码或者教程,可以到用户中心发布,分享有积分奖励和额外收入! 4. 本站提供的源码、模板、插件等等其他资源,都不包含技术服务请大家谅解! 5. 如有链接无法下载、失效或广告,请联系管理员处理! 6. 本站资源售价只是赞助,收取费用仅维持本站的日常运营所需! 7. 如遇到加密压缩包,默认解压密码为"gltf",如遇到无法解压的请联系管理员! 8. 因为资源和程序源码均为可复制品,所以不支持任何理由的退款兑现,请斟酌后支付下载 声明:如果标题没有注明"已测试"或者"测试可用"等字样的资源源码均未经过站长测试.特别注意没有标注的源码不保证任何可用性