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

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

    此时问题又出来了,我们刚才说,空队列时,front等于rear,现在当队列满时,也是front等于rear,那么如何判断此时的队列究竟是空还是满呢?

    • 办法一是设置一个标志变量flag,
      • 当front==rear,且flag=0时为队列空,
      • 当front==rear,且flag=1时为队列满。
    • 办法二是当队列空时,条件就是front=rear,

      1. 当队列满时,我们修改其条件,保留一个元素空间。<br />也就是说,队列满时,数组中还有一个空闲单元。<br />例如图4-12-8所示,我们就认为此队列已经满了,也就是说,我们不允许图4-12-7的右图情况出现。<br />![image.png](https://cdn.nlark.com/yuque/0/2021/png/23091758/1637484596633-4778ff81-2cb1-4870-9518-dc695b6935cf.png#clientId=ud2e69c6a-2304-4&from=paste&id=u344fee93&margin=%5Bobject%20Object%5D&name=image.png&originHeight=217&originWidth=1152&originalType=url&ratio=1&size=52224&status=done&style=none&taskId=uefceea96-bce3-431d-8013-fbf3e87c091)<br />图4-12-8

    我们重点来讨论第二种方法,
    由于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;
    3. /* 循环队列的顺序存储结构 */
    4. typedef struct
    5. {
    6. QElemType data[MAXSIZE];
    7. /* 头指针 */
    8. int front;
    9. /* 尾指针,若队列不空,指向队列尾元素的下一个位置 */
    10. int rear;
    11. } SqQueue;

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

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

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

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

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

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

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

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

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