循环队列

原文地址： 数据结构——循环队列详解

最近数据结构上的越来越快了，这个东西也不打算自己写了，这篇文章写的 Very Good。

一、循环队列的定义

定义：队列主要有顺序队列，循环队列，双端队列，优先队列。而当中循环队列是一种线性数据结构。它也被称为 “环形缓冲器”。它只允许在一端进行插入操作，即队尾（rear），而在另一端进行删除操作，即队头 (front)，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。向队列中插入新的数据元素称为入队，新入队的元素就成为了队列的队尾元素。

特点：

1. 循环队列允许元素在队尾插入，在队头删除，同时遵循先进先出原则。
2. 由于循环队列是基于数组实现的，所以它的访问速度很快，特别是在移动元素时。
3. 如果需要大量添加和删除元素，循环队列比链表更有效率，因为它不需要频繁地移动指针来访问元素。
4. 不支持随机访问元素，因此不能像数组那样直接访问特定位置的元素。

二、 循环队列的基本操作

1. 初始化：这是创建一个空的顺序队列，需要设定队首指针 front 和队尾指针 rear 都指向同一个位置，一般初始都设置为 0，即队列为空。

2. 元素入队：也被称为插入操作，是将一个新元素添加到队列尾部的操作。

3. 元素出队：也被称为删除操作，是将队列头部的元素移除的操作。

4. 求队列长度：可以通过计算队尾指针和队首指针之差的值再加 1 来获取当前队列的长度。

5. 判断是否为空：通过检查队首指针 front 和队尾指针 rear 是否相等来判断队列是否为空。

6. 判断是否为满：当队尾指针指向数组的最后一个位置时，下一个要插入的位置就是队头指针。

7. 取队头：头元素就是队列中的第一个元素，可以通过返回队首指针 front 的值来获取。

8. 输出队列：将队列中元素通过 while 语句循环语句打印出来

三、循环队列的实现

1、循环队列的定义

用一个数组来存储队列中的元素，用 front 作为队头指针，指向队列的第一个元素，用 rear 作为队尾指针，即指向队列最后一个元素的下一个位置.

#define MAXSIZE 4

typedef int DataType;

typedef struct
{
    DataType data[MAXSIZE];
    int front;
    int rear;
}CirclesQueue;

2、循环队列的初始化

循环队列的初始化只需要将队头指针（front）和队尾指针（rear）都初始化为 0.

/*循环队列初始化*/
int init(CirclesQueue *Q)
{
    Q->front = Q->rear = 0;
    return 0;
}

3、循环队列出队

出队前判断队列是否为空，如果为空，返回 100002 错误信息，如果队列不为空，将队列的队头指针向前移动一位，即将队头指针加 1 并对 MAXSIZE 取模，确保指针在数组范围内循环移动，当到达数组末尾时，会回到数组的开头。

/*出队*/
int dequeue(CirclesQueue *Q, DataType *x)
{
    if(isempty(Q))
    {
        printf("队列为空！100002\n");
        return 100002;
    }
    Q->front = (Q->front+1) % MAXSIZE;
    *x = Q->data[Q->front];
    return 0;
}

4、循环队列入队

入队前需要判断队列是否已经满了，如果队列为满，则不能入队。反之，则将队列的队头向前移动一位，确保指针在数组范围内能够循环移动。具体来说，就是将当前队头指针的值加 1，然后对队列的最大容量（MAXSIZE）取模来实现。

/*入队*/
int enqueue(CirclesQueue *Q, DataType x)
{
    if(isfull(Q))
    {
        printf("队列已满！100001\n");
        return 100001;
    }

    Q->rear = (Q->rear+1) % MAXSIZE;
    Q->data[Q->rear] = x;
    return 0;
}

5、队列判空

判断循环队列是否为空通过比较队头指针和队尾指针是否相等来判断，如果它们相等，说明队列中没有元素，反之则存在元素。 

/*队空*/
int isempty(CirclesQueue *Q)
{
    return (Q->front == Q->rear) ? 1 : 0;
}

6、 队列判满

判断循环队列是否为满可以让队列的 rear 指针加 1 之后对 MAXSIZE 取模结果等于 front 指针，这时表明队列已满，反之则未满。

/*队满？*/
int isfull(CirclesQueue *Q)
{
    return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
}

7、取队头元素

想要获取队头元素，首先需要判断队列是否为空，如果为空，返回错误信息。不为空时，可以通过计算 front 加 1 后对 MAXSIZE 取模获取队首元素的位置。

/*取队头元素*/
int QueueFront(CirclesQueue *Q,DataType *x)
{
    if(isempty(Q))
    {
        printf("队列为空！100002\n");
        return 100002;
    }
    *x = Q->data[(Q->front + 1) % MAXSIZE];
    return 0;

8、输出队列

输出队列前需要先判断队列是否为空，如果为空则输出队列为空，不为空时，将队头指针的值赋给i，并对最大容量MAXSIZE取模，再通过 do-while 循环来遍历队列中的元素，循环的内部通过计算(i + 1 % MAXSIZE)来获取下一个元素的索引，并输出打印当前元素，同时更新i的值，使其加 1 并对MAXSIZE取模，以便继续遍历队列。

/*输出队列*/
void PrintQueue(CirclesQueue *Q){
    int i;
    if (isempty(Q))
    {
        printf("队列为空！\n");
        return;
    }
    i=(Q->front)%MAXSIZE;    //确保i的值在0到MAXSIZE-1之间，以便在后续操作中作为数组索引使用
    do
    {
        printf("%d、",Q->data[(i + 1 % MAXSIZE)]);
        i=(i+1)%MAXSIZE;
    }while(i!=Q->rear);
}

9、求队列长度

求循环队列的长度可以通过计算队列的尾指针（rear）和头指针（front）之间的差值，加上最大容量 (MAXSIZE)，然后对最大容量取模，得到队列的实际长度。最后，将计算结果存储在指针 x 所指向的位置，并返回 0 表示成功。

*获取队列长度*/ 
int getLength(CirclesQueue *Q,DataType *x) {  
  *x= (Q->rear - Q->front + MAXSIZE) % MAXSIZE; 
  return 0;
}

四、完整代码

1、main.c

#include <stdio.h>
#include "CirclesQueue.h"


int main(int argc, char* argv[])
{
    CirclesQueue Q;
    DataType x;
    int cmd;
    char yn;


    do
    {   
        printf("-----------循环队列演示-----------\n");
        printf(" 1. 初始化\n");
        printf(" 2. 入队\n");
        printf(" 3. 出队\n");
        printf(" 4. 队空？\n");
        printf(" 5. 队满\n");
        printf(" 6.取队头\n");
        printf(" 7.输出队列\n");
        printf(" 8.取长度\n");
        printf(" 9.帮助\n");
        printf(" 0. 退出\n");
        printf(" 请选择（0~6）：");
        scanf("%d",&cmd);
        switch(cmd)
        {
        case 1:
            init(&Q);
            printf("队列已初始化！\n");
            break;
        case 2:
            printf("请输入要入队的元素x=");
            scanf("%d", &x);
            if(!enqueue(&Q,x))
            {
                printf("元素x=%d已入队\n", x);
            }
            break;
        case 3:
            printf("确定要出队（出队会将删除对首元素, y or n, n）？");
            flushall();
            scanf("%c", &yn);

            if(yn == 'y' || yn == 'Y')
            {
                if(!dequeue(&Q,&x))
                {
                    printf("队首元素【%d】已出队！\n", x);
                }
            }
            break;
        case 4:
            if(isempty(&Q))
            {
                printf("队列为空！\n");
            }
            else{
                printf("队列不为空!\n");
            }
            break;
        case 5:
            if(isfull(&Q))
            {
                printf("队列为满！\n");
            }
            else{
                printf("队列未满!\n");
            }

            break;
        case 6:
            if(!QueueFront(&Q,&x))
            {
                printf("队首元素为【%d】！\n", x);
            }
            break;
        case 7:
            PrintQueue(&Q);
            printf("\n");
            break;
        case 8:
            if(!getLength(&Q,&x))
            {
                printf("队列长度为【%d】！\n", x);
            }
            break;
        case 9:
            printf("本程序由zzb设计开发,实现了循环队列的入队、出队、取队头等操作\n");

        }

    }while(cmd!=0);


    return 0;
}

2、 CirclesQueue.c

/*
    CirclesQueue.c
*/
#include "CirclesQueue.h"

/*循环队列初始化*/
int init(CirclesQueue *Q)
{
    Q->front = Q->rear = 0;
    return 0;
}


/*入队*/
int enqueue(CirclesQueue *Q, DataType x)
{
    if(isfull(Q))
    {
        printf("队列已满！100001\n");
        return 100001;
    }

    Q->rear = (Q->rear+1) % MAXSIZE;
    Q->data[Q->rear] = x;
    return 0;
}

/*队满？*/
int isfull(CirclesQueue *Q)
{
    return (Q->rear+1)%MAXSIZE == Q->front ? 1 : 0;
}


/*出队*/
int dequeue(CirclesQueue *Q, DataType *x)
{
    if(isempty(Q))
    {
        printf("队列为空！100002\n");
        return 100002;
    }
    Q->front = (Q->front+1) % MAXSIZE;
    *x = Q->data[Q->front];
    return 0;
}

/*队空*/
int isempty(CirclesQueue *Q)
{
    return (Q->front == Q->rear) ? 1 : 0;
}
/*取队头元素*/
int QueueFront(CirclesQueue *Q,DataType *x)
{
    if(isempty(Q))
    {
        printf("队列为空！100002\n");
        return 100002;
    }
    *x = Q->data[(Q->front + 1) % MAXSIZE];
    return 0;


}
/*输出队列*/
void PrintQueue(CirclesQueue *Q){
    int i;
    if (isempty(Q))
    {
        printf("队列为空！\n");
        return;
    }
    i=(Q->front)%MAXSIZE;
    do
    {
        printf("%d、",Q->data[(i + 1 % MAXSIZE)]);
        i=(i+1)%MAXSIZE;
    }while(i!=Q->rear);
}
/*获取队列长度*/ 
int getLength(CirclesQueue *Q,DataType *x) {  
  *x= (Q->rear - Q->front + MAXSIZE) % MAXSIZE; 
  return 0;
}

3、 CirclesQueue.h

/*
    CirclesQueue.h
    循环队列
*/

#define MAXSIZE 4

typedef int DataType;

typedef struct
{
    DataType data[MAXSIZE];
    int front;
    int rear;
}CirclesQueue;

/*循环队列初始化*/
int init(CirclesQueue *Q);

/*入队*/
int enqueue(CirclesQueue *Q, DataType x);

/*队满？*/
int isfull(CirclesQueue *Q);

/*出队*/
int dequeue(CirclesQueue *Q, DataType *x);

/*队空*/
int isempty(CirclesQueue *Q);
/*取队头元素*/
int QueueFront(CirclesQueue *Q,DataType *x);
/*输出队列*/
void PrintQueue(CirclesQueue *Q);
/*队列长度*/
int getLength(CirclesQueue *Q,DataType *x);

五、小结

1、循环队列是一种线性数据结构。它也被称为 “环形缓冲器”。它只允许在一端进行插入操作，即队尾（rear），而在另一端进行删除操作，即队头 (front)，其操作表现基于 FIFO（先进先出）原则并且队尾被连接在队首之后以形成一个循环。

2、循环队列的应用范围非常广泛，比如线程池任务调度、消息队列系统、缓冲区管理、广度优先搜索算法等应用场景。

3、队列满时，无法再进行插入操作；当队列空时，无法再进行删除操作。队列的大小是固定的，一旦创建后不能改变。

六、参考文献

《数据结构》(C 语言版）李刚，刘万辉. 北京：高等教育出版社 ，2017.   

《C 语言程序设计》(第四版）谭浩强. 北京：清华大学出版社，2014.

CSDN 数据结构 ----- 循环队列