【数据结构】循环队列

古城微笑少年丶 2022-09-29 15:44 265阅读 0赞

循环队列的设计是为了避免“虚溢出”的现象。所谓“虚溢出”是指在利用数组构建队列时，当尾指针指向数组末尾时，即便数组前端仍有剩余空间，但是却无法向队列中添加新元素的“虚假溢出”的现象。图示如下：

![SouthEast][]

循环队列为解决“虚溢出”的问题，允许当尾指针到达数组末尾时，如果数组头部仍有空间，可以移动到数组头部并指向这些空间。所以形象地称为循环队列，并用下图表示。

![这里写图片描述][SouthEast 1]

需要注意的是循环队列在计算机中仍然是以数组的形式顺序存储的，所谓循环是通过计算指针移动的位置来实现的。公式如下：

将尾指针向后移动一位，新的位置为：
    rear = (rear + 1) % MaxSize
    头指针的移动同理：
    front = (front + 1) % MaxSize

由于循环结构的特点，我们无法使用判断条件：front = rear 来判断队列是否为空，因为当数组空间可以被全部使用时，当队列为空或队列已满的情况下，front与rear都指向同一位置。解决这个问题的方法有两种：

1.  **额外设置一个计数器，记录队列长度。由计数器的数值判断队列的情况。**
2.  **牺牲一个存储空间，不向头指针所指的位置添加元素（如上图所示）。这样我们就有了新的判断条件**：

front == rear //队列为空
        (rear + 1) % MaxSize == front //队列已满

显然这样的方式更为简单。

由此给出计算队列长度的公式：

length = (rear - front + MaxSize) % MaxSize

下面是相关的C语言实现

#include <stdio.h>
    
    #define MaxSize 10
    typedef struct{
        int Date[MaxSize];
        int front;
        int rear;
    } Queue;
    
    void AddQ(Queue *Q, int item)
    {
        if((Q->rear+1)%MaxSize == Q->front){
            printf("队列已满\n");
            return;
        }
        else{
            Q->rear = (Q->rear+1)%MaxSize;
            Q->Date[Q->rear] = item;
        }
    
    }
    
    int DeleteQ(Queue *Q)
    {
        if(Q->rear == Q->front){
            printf("队列为空\n");
            return NULL;
        }
        else{
            Q->front = (Q->front+1)%MaxSize;
            return Q->Date[Q->front];
        }
    }

[SouthEast]: /images/20220708/87a123e55fd0494b90e1fc0e0ff946bb.png
[SouthEast 1]: /images/20220708/83cf33b846534a39b4d104c650d96a7e.png