数据结构 / 队列 / 循环队列 / 概念

1. 定义

为充分利用向量空间，克服假溢出现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（Circular Queue）。循环队列是把顺序队列首尾相连，把存储队列元素的表从逻辑上看成一个环，成为循环队列。

2.简介

循环队列就是将队列存储空间的最后一个位置绕到第一个位置，形成逻辑上的环状空间，供队列循环使用。在循环队列结构中，当存储空间的最后一个位置已被使用而再要进入队运算时，只需要存储空间的第一个位置空闲，便可将元素加入到第一个位置，即将存储空间的第一个位置作为队尾。 循环队列可以更简单防止伪溢出的发生，但队列大小是固定的。

在循环队列中，当队列为空时，有front=rear，而当所有队列空间全占满时，也有front=rear。为了区别这两种情况，规定循环队列最多只能有MaxSize-1个队列元素，当循环队列中只剩下一个空存储单元时，队列就已经满了。因此，队列判空的条件是front=rear，而队列判满的条件是front=（rear+1)%MaxSize。

图1

注意：

• 队列下标从0开始
• rear指向的是最后一个空位置

3.队列中元素的个数计算

• 队列中元素的个数：len = ( rear - front + MaxSize ) % MaxSize
• 解析：
  • 不考虑循环，队列的个数为rear-front + 1 - 1, +1是队列下标从0开始的，-1是rear指向最后空位置
  • 因为有循环，会有跨界的可能，先加上一个MaxSize, 相当于放在一个2xMaxSize中，避免了跨界，计算出长度后，多余部分用%MaxSize来纠正 (MaxSize % MaxSize 为0，2xMaxSize / MaxSize 也为0，不会对最后结果有影响)
    • 例1：
      • 如下图3，MaxSize=8，front=2, rear=0, rear正好跨过一轮
      • rear-front=-2, 这时加上MaxSize再%MaxSize，(0-2+8)%8=6         
    • 例2：
      • 如下图4，MaxSize=8，front=0, rear=6 
      • rear-front=6, (6-0+8)%8=6                        

图4

图3

                

参考： 循环队列_百度百科

---

目录：学习笔记快速链接                 

下一篇：循环队列 / 结构体定义和创建