数据结构之循环队列

为充分利用向量空间，克服"假溢出"现象的方法是：将向量空间想象为一个首尾相接的圆环，并称这种向量为循环向量。存储在其中的队列称为循环队列（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