数据结构之循环队列

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

循环队列三种情况

1、

• front 指向头元素的前一个元素

• rear 指向队尾元素

• 对空、入队和队满情况判断：

  • 队空：front=rear
  • 入队：rear=（rear+1）% maxsize，每次元素进入队列，队尾指针 rear 向后移动 一位。
    • queue【rear】=x
  • 队满：front==(rear+1)% maxsize

• 根据 rear 和 front 计算队列长度：

  • 当 rear>front
    • 
    • 很容易得到队列长度为：rear-front
  • 当 rear<front
    • 
      • 因为是循环队列，rear 的位置可以在 front 的前面，此时队列长度为：rear+1+maxsize-front-1=rear-front+maxsize
        • rear+ 1 为其中一段的长度
        • maxsize-front-1 为另一段的长度

  2、

  

  • front 指向头元素
  • rear 指向队尾的后一个元素
  • 队满：front=(rear+1)% maxsize
  • 队列长度：(rear-front+max)% maxsize