关于循环队列的一些讲解

转载：http://www.nowamagic.net/librarys/veda/detail/2351

前面讲到了队列的“假溢出”，解决假溢出的办法就是后面满了，就再从头开始，也就是头尾相接的循环。我们把队列的这种头尾相接的顺序存储结构称为循环队列。

比如昨天的例子，rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了。

但是如果继续进行入队操作的话，比如继续插入a6、a7，则rear指针就与front指针重合，同时指向下标为2的位置。

• 此时问题又出来了，我们刚才说，空队列时，等于rear，现在当队列满时，也是from等于rear，那么如何判断此时的队列究竟是空还是满呢？
• 办法一是设置一个标志变量flag，当front == rear,且flag = 0时为队列空，当front == rear,且flag= 1时为队列满。
• 办法二是当队列空时，条件就是from = rear,当队列满时，我们修改其条件，保留一个元素空间。也就是说，队列满时，数组中还有一个空闲单元。 如下图所示，我们就认为此队列已经满了，也就是说，我们不允许上图情况出现。

我们来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1) %QueueSize == front (取模“%的目的就是为了整合rear与front大小为一个问题)。

比如上面这个例子， QueueSize = 5，当 front=0，而 rear=4, (4+1) %5 = 0，所以此时队列满。再比如，front = 2而rear =1。(1 + 1) %5 = 2，所以此时 队列也是满的。而对于下图, front = 2而rear= 0, (0+1) %5 = 1，1!=2,所以此时队列并没有满。

另外，当rear > front时，此时队列的长度为rear—front。但当rear < front时，队列长度分为两段，一段是QueueSize-front，另一段是0 + rear，加在一起，队列长度为rear-front + QueueSize，因此通用的计算队列长度公式为：

(rear—front + QueueSize) % QueueSize

有了这些讲解，现在实现循环队列的代码就不难了。具体的例子程序可以参照前面说的顺序队列。

最后

以上就是义气音响为你收集整理的关于循环队列的一些讲解的全部内容，希望文章能够帮你解决关于循环队列的一些讲解所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。