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

    刚才的例子继续，图4-12-5的rear可以改为指向下标为0的位置，这样就不会造成指针指向不明的问题了，如图4-12-6所示。
    image.png
    接着入队a 6 ，将它放置于下标为0处，rear指针指向下标为1处，如图4-12-7的左图所示。若再入队a 7 ，则rear指针就与front指针重合，同时指向下标为2的位置，如图4-12-7的右图所示。
    image.png

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

    image.png
    我们重点来讨论第二种方法，由于rear可能比front大，也可能比front小，所以尽管它们只相差一个位置时就是满的情况，但也可能是相差整整一圈。所以若队列的最大尺寸为QueueSize，那么队列满的条件是(rear+1)%QueueSize==front（取模“%”的目的就是为了整合rear与front大小为一个问题）。比如上面这个例子，QueueSize=5，图4-12-8的左图中front=0，而rear=4，(4+1)%5=0，所以此时队列满。再比如图4-12-8中的右图，front=2而rear=1。(1+1)%5=2，所以此时队列也是满的。而对于图4-12-6，front=2而rear=0，(0+1)%5=1，1≠2，所以此时队列并没有满。

    另外，当rear>front时，即图4-12-4的右图和4-12-5的左图，此时队列的长度为rear-front。但当rear<front时，如图4-12-6和图4-12-7的左图，队列长度分为两段，一段是QueueSize-front，另一段是0+rear，加在一起，队列长度为rear-front+QueueSize。因此通用的计算队列长度公式为：

    (rear-front+QueueSize)%QueueSize

    有了这些讲解，现在实现循环队列的代码就不难了。

    循环队列的顺序存储结构代码如下：

    1. /* QElemType类型根据实际情况而定，这里假设为int */
    2. typedef int QElemType;
    4. /* 循环队列的顺序存储结构 */
    5. typedef struct{
    7.     QElemType data[MAXSIZE];
    9.     /* 头指针 */
    10.     int front;
    12.     /* 尾指针，若队列不空，指向队列尾元素的下一个位置 */
    13.     int rear;
    15. } SqQueue;

    循环队列的初始化代码如下：

    1. /* 初始化一个空队列Q */
    2. Status InitQueue(SqQueue *Q){
    4.     Q->front = 0;
    5.     Q->rear = 0;
    7.     return OK;
    9. }

    循环队列求队列长度代码如下：

    1. /* 返回Q的元素个数，也就是队列的当前长度 */
    2. int QueueLength(SqQueue Q){
    4. return (Q.rear - Q.front + MAXSIZE) % MAXSIZE;
    6. }

    循环队列的入队列操作代码如下：

    1. /* 若队列未满，则插入元素e为Q新的队尾元素 */
    2. Status EnQueue(SqQueue *Q, QElemType e){
    4.     /* 队列满的判断 */
    5.     if ((Q->rear + 1) % MAXSIZE == Q->front)
    6.         return ERROR;
    8.     /* 将元素e赋值给队尾 */
    9.     Q->data[Q->rear] = e;
    11.     /* rear指针向后移一位置， */
    12.     Q->rear = (Q->rear + 1) % MAXSIZE;
    14.     /* 若到最后则转到数组头部 */
    15.     return OK;
    17. }

    循环队列的出队列操作代码如下：

    1. /* 若队列不空，则删除Q中队头元素，用e返回其值 */
    2. Status DeQueue(SqQueue *Q, QElemType *e){
    4.     /* 队列空的判断 */
    5.     if (Q->front == Q->rear)
    6.         return ERROR;
    8.     /* 将队头元素赋值给e */
    9.     *e = Q->data[Q->front];
    11.     /* front指针向后移一位置， */
    12.     Q->front = (Q->front + 1) % MAXSIZE;
    14.     /* 若到最后则转到数组头部 */
    15.     return OK;
    17. }

    从这一段讲解，大家应该发现，单是顺序存储，若不是循环队列，算法的时间性能是不高的，但循环队列又面临着数组可能会溢出的问题，所以我们还需要研究一下不需要担心队列长度的链式存储结构。