为充分利用向量空间,克服 " 假溢出" 现象的方法是:将向量空间想象为一个首尾相接的圆环,并称这种向量为循环向量。存储在其中的队列称为循环队列(Circular Queue)。循环队列是把顺序队列首尾相连,把存储队列元素的表从逻辑上看成一个环,成为循环队列。
循环队列三种情况
1、
![image-20211006115040686]()
-
front 指向头元素的前一个元素
-
rear 指向队尾元素
-
对空、入队和队满情况判断:
- 队空:front=rear
- 入队:rear=(rear+1)% maxsize,每次元素进入队列,队尾指针 rear 向后移动 一位。
- 队满:front==(rear+1)% maxsize
-
根据 rear 和 front 计算队列长度:
- 当 rear>front
![image-20211006142409854]()
- 很容易得到队列长度为:rear-front
- 当 rear<front
- 因为是循环队列,rear 的位置可以在 front 的前面,此时队列长度为:rear+1+maxsize-front-1=rear-front+maxsize
- rear+ 1 为其中一段的长度
- maxsize-front-1 为另一段的长度
2、
![image-20211006151401822]()
- front 指向头元素
- rear 指向队尾的后一个元素
- 队满:front=(rear+1)% maxsize
- 队列长度:(rear-front+max)% maxsize