【数据结构】循环队列

0. 前言 

在之前的博客，博主跟小伙伴们分享了数据结构中的队列，并且我们可以实现顺序队列和链式队列，这期博客再给大家讲解一种实现队列的方式——循环队列。未来我们学校操作系统，会学习到生产者消费者模型时就会使用循环队列。我们一起来进入正题吧！

1. 循环队列的定义

顺序队列在使用过程中容易出现虚假的满状态， 为了解决这个问题，就产生了一个较巧妙的方法，将顺序队列臆造为一个环状的空间，称之为循环队列。循环队列中指针和队列元素之间的关系不变，我们只需要利用模运算就可以很容易实现指针的循环移动。但是循环队列中存在一个问题，在循环队列中只凭头指针front等于尾指针rear无法判别队列空间是“空”还是“满”，可有两种处理方法：其一是另设一个标志位以区别队列是“空”还是“满”；其二是少用一个元素空间，约定以“队列头指针在队列尾指针的下一位置(指环状的下一位置)上”作为队列呈“满”状态的标志。此处使用方法二来解决这个问题。

2. 循环队列的结构

结构图

3. 队列结构体类型定义

#define MAX_SIZE 10   
 
//循环队列的结构设计
typedef struct cir_queue{
    int data[MAX_SIZE];
    int rear;
    int front;
}cir_queue;
 

代码解释： 

#define MAX_SIZE 5

我们#define定义了一个常量MAX_SIZE，其值为 5。这个常量将在后续的代码中用于指定循环队列的最大容量。

//循环队列的结构设计
typedef struct cir_queue{
    int data[MAX_SIZE];
    int rear;
    int front;
}cir_queue;
 

这里定义了一个名为struct cir_queue的结构体类型，因为结构体类型使用不方便，

并且typedef对结构体类型重新起名叫cir_queue，这个结构体包含以下三个成员：

• int data[MAX_SIZE]：这是一个整型数组，用于存储循环队列中的元素。数组的大小由前面定义的MAX_SIZE决定。
• int front：这是一个整型变量，用于表示循环队列的队首位置。
• int rear：这是一个整型变量，用于表示循环队列的队尾位置。

4. 循环队列的常用操作

4.1 初始化

将循环队列的队首指针front和队尾指针rear初始化为 0。

在一个空的循环队列中，队首和队尾指针都指向数组的第一个位置，表示队列为空。

代码如下：

//初始化循环队列
cir_queue* init()
{
    cir_queue* q = (cir_queue*)malloc(sizeof(cir_queue));
    if (q == NULL)
    {
        exit(0);   //申请内存失败，退出程序
    }
    q->front = 0;
    q->rear = 0;
    return q;
}

4.2 循环队列入队操作

入队操作同顺序队列的方法，直接将rear向后移动即可，但是要注意判断，如果rear达到了队列的空间上线，将要从头继续开始移动，这里推荐使用余数法，即无论如何求余都是在这片空间内进行操作，防止一次错误执行就直接整体崩溃，而且也相对而言更为简洁，不推荐使用if语句，这样显得比较累赘。

 注意进行加一移动位置操作的时候，不能直接q->rear++这样的操作，这样计算机判断优先级会产生让自己意想不到的后果，此外这里还需要进行一次是否队列已满的判断，当我们rear指针的下一个位置就是front的位置的时候，即改循环队列已满。

 代码如下：

//入队操作enqueue
void enqueue(cir_queue* q, int data)
{
    if ((q->rear + 1) % MAX_SIZE == q->front)
    {
        printf("溢出，无法入队\n");
        return;
    }
    else 
    {
        q->rear = (q->rear + 1) % MAX_SIZE;
        q->data[q->rear] = data;
    }
}

4.3 循环队列出队操作

如果顺序队列的出队操作，直接将front进行后移一位即可，注意这时候有一个需要留意的地方，即队列是否为空，当队列为空的时候是无法进行出队操作的。

代码如下： 

//出队操作dequeue

void dequeue(cir_queue * q) 
{
	if (q->rear == q->front) 
	{
		printf("队列为空，无法出队\n");
		return;
	}
	else
	{
		q->data[q->front] = 0;
		q->front = (q->front + 1) % MAX_SIZE;
	}
}

4.4 循环队列遍历操作

遍历操作需要借助一个临时变量储存位置front的位置信息，利用i逐步向后移动，直到i到达了rear的位置即可宣告遍历的结束。

代码如下：

//遍历队列
void print(cir_queue* q) 
{
    int i = q->front;
    while (i != q->rear) 
    {
        i = (i + 1) % MAX_SIZE;
        printf("%d\t", q->data[i]);
    }
    printf("\n");       //记得换行
}

5. 完整代码：

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define maxsize 10      //表示循环队列的最大容量

//循环队列的结构设计
typedef struct cir_queue 
{
    int data[maxsize];
    int rear;
    int front;
}cir_queue;

//初始化循环队列
cir_queue* init()
{
    cir_queue* q = (cir_queue*)malloc(sizeof(cir_queue));
    if (q == NULL)
    {
        exit(0);   //申请内存失败，退出程序
    }
    q->front = 0;
    q->rear = 0;
    return q;
}

//入队操作enqueue
void enqueue(cir_queue* q, int data)
{
    if ((q->rear + 1) % maxsize == q->front)
    {
        printf("溢出，无法入队\n");
        return;
    }
    else 
    {
        q->rear = (q->rear + 1) % maxsize;
        q->data[q->rear] = data;
    }
}

//出队操作dequeue
void dequeue(cir_queue* q)
{
    if (q->rear == q->front) 
    {
        printf("队列为空，无法出队\n");
        return;
    }
    else {
        q->data[q->front] = 0;
        q->front = (q->front + 1) % maxsize;
    }
}

//遍历队列
void print(cir_queue* q) 
{
    int i = q->front;
    while (i != q->rear) {
        i = (i + 1) % maxsize;
        printf("%d\t", q->data[i]);
    }
    printf("\n");       //记得换行
}

int main() 
{
    cir_queue* q = init();
    入队操作///
    printf("入队操作\n");
    for (int i = 1; i <= 6; i++) 
    {
        enqueue(q, i);
    }
    print(q);
    出队操作///
    printf("出队操作\n");
    for (int i = 1; i <= 3; i++) 
    {
        dequeue(q);
        print(q);
    }
    return 0;
}

代码测试：

6. 结语

对循环队列的介绍就到这里啦，希望这篇文章能给予你一些帮助，如果有疑问的，欢迎在评论区与我讨论交流，你们的点赞、收藏，评论是我更新更多知识的动力~ 我们下期博客见！