数据结构——循环队列详解

目录

一、循环队列的定义

二、 循环队列的基本操作

三、循环队列的实现 

1、循环队列的定义

2、循环队列的初始化 

3、循环队列出队 

4、循环队列入队 

5、队列判空

6、 队列判满

7、取队头元素

8、输出队列 

9、求队列长度 

四、完整代码 

五、小结 

六、参考文献

---

一、循环队列的定义

定义：队列主要有顺序队列，循环队列，双端队列，优先队列。而当中循环队列是一种线性数据结构。它也被称为“环形缓冲器”。它只允许在一端进行插入操作，即队尾（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 
#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);

4、运行截图 

五、小结 

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

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

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

 六、参考文献

 

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

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

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