数据结构-循环队列详解（c语言版）_c语言循环队列

目录

一、什么是循环队列？

二、特点

三、基本运算

四、代码实现

 1、初始化

2、入队

3、出队

4、队满？

5、队空？ 

6、输出队列

7、队列大小

8、获取队首元素

五、队列应用场景

六、完整代码

1、完整代码

2、运行结果

七、总结

---

前言

相比于链队列，循环队列有着内存固定，效率高等特点，因而广泛应用于计算机的各个层面。本文主要介绍循环队列的概念和特点，列举一些循环队列的应用场景，以及给出用数组用C语言实现循环队列的代码。

---

一、什么是循环队列？

循环队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，一般保持队尾指针（rear）大于队头指针（front）的规律，实现循环利用。

二、特点

循环队列的特点主要包括：

1. 高效利用存储空间：循环队列通过循环使用存储空间，避免了普通队列在元素出队时需要移动大量元素的缺点，提高了队列的效率。
2. 避免假溢出：普通队列在插入元素时，如果队列已满，则需要移动大量元素才能插入新元素，这种情况下会造成假溢出。而循环队列通过循环使用存储空间，避免了这种情况的发生。
3. 适合处理用户排队等待的情况：循环队列可以高效地处理用户排队等待的情况，因为它的插入和删除操作都是在队头进行的，可以快速响应请求。
4. 需要预先分配大量存储空间：循环队列需要预先分配足够的存储空间，这可能会造成一定的空间浪费。
5. 时间复杂度：读取元素时，循环队列的时间复杂度为O(1)；插入和删除元素时，循环队列的时间复杂度也为O(1)。

总的来说，循环队列是一种高效的数据结构，它可以有效地处理排队等待的情况，避免假溢出等问题，但也需要注意预先分配存储空间的问题。

三、基本运算

循环队列的基本运算主要包括以下几个操作：

1. 初始化：创建一个空的循环队列，并设置队列的容量和当前队列中的元素数量。
2. 入队：将一个元素添加到队列的尾部。如果队列已满，则无法添加元素。
3. 出队：从队列的头部删除一个元素。如果队列为空，则无法删除元素。
4. 判断队列是否为空：检查队列中是否有元素。
5. 判断队列是否已满：检查队列是否已达到最大容量。
6. 获取队列的元素个数：返回队列中当前的元素数量。
7. 获取队头元素：返回队列头部的元素，但不删除该元素。
8. 输出队列：将队列中所有元素打印出来。

这些基本运算可以实现对循环队列的基本操作和管理。在实现循环队列时，需要注意队列的存储空间分配、元素的插入和删除位置以及队列为空和已满时的特殊情况处理等问题。

四、代码实现

   1、初始化

    循环队列初始化操作步骤如下：

    1、定义一个数组空间，作为循环队列的存储空间。

     2、定义两个指针，分别指向队列的头部和尾部，即front和rear。

     3、初始化时，将front和rear都指向队列的头部。

  代码如下（示例）：

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

2、入队

循环队列入队操作步骤如下：

1、判断队列是否已满，如果队列已满，返回100001错误信息。

 2、如果队列未满，将新元素添加到rear所指向的位置。

 3、将rear向后移动一位。

 4、如果rear已经到达数组的末端，则将其循环移动到数组的开头。

返回成功信息。

  代码如下（示例）：

/*入队*/
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;
}

3、出队

循环队列出队操作步骤如下：

1、判断队列是否为空，如果队列为空，返回100002错误信息。

2、如果队列非空，将front所指向的元素删除并返回。

3、将front向后移动一位。

4、如果front已经到达数组的末端，则将其循环移动到数组的开头。

返回成功信息。

 代码如下（示例）：

/*出队*/
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、队满？

循环队列队满判断操作步骤如下：

 队列的rear指针加1之后对MAXSIZE取模结果等于front指针，表名队列已满，函数返回1；             反 之，队列未满，函数返回0；

 代码如下（示例）：

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

5、队空？ 

 循环队列队空判断操作步骤如下：

 如果队列的front指针等于rear指针，队列为空，函数返回1；反之，队列不为空，函数返回0；

 代码如下（示例）：

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

6、输出队列

循环队列中的数据元素可以通过以下步骤进行输出：

1、首先判断队列是否为空，如果为空返回100002错误信息。

2、从front开始，依次访问队列中的每个元素。

3、到达rear时，如果队列未满，则将rear向前移动一位。

4、如果rear已经到达数组的末端，则将其循环移动到数组的开头。

5、继续从front开始遍历，直到访问完所有元素。

 代码如下（示例）：

/*输出队列*/
 
void print(CirclesQueue *Q) 
{
	int i;
	if(isempty(Q))
	{
		printf("队列为空！100002\n");
		return 100002;
	}
	
	i=(Q->front)%MAXSIZE;
	do{
		printf("%d  ",Q->data[(i+1 %MAXSIZE)]);
		i=(i+1)%MAXSIZE;
	} while(i!=Q->rear);
} 

7、队列大小

循环队列获取队首元素的方法如下：

循环队列的大小可以通过rear指针和front指针之间的距离来得到。为了确保在计算队列长度时不会超出数组的边界,可以用rear指针减front头指针加上MAXSIZE再对MAXSIZE取模就可已得到队列大小。

代码如下（示例）：

/*获取队列中元素个数*/
 
int getSize(CirclesQueue *Q)
{
	return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
 } 

8、获取队首元素

循环队列获取队首元素的方法如下：

1、首先判断队列是否为空，如果则返回100002错误信息。

2、可以通过front加1后对MAXSIZE取模获取队首元素的位置。

代码如下（示例）：

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

五、队列应用场景

队列的应用场景主要包括：

异步处理：

在这种场景中，可以使用消息队列实现异步处理任务。例如，在用户注册后，可以通过消息队列发送注册邮件和短信，而不需要等待这两个任务完成后再返回给用户。这种方式可以提高处理效率。

应用解耦：

业务系统中，一些非核心的或非关键的部分可以使用消息队列来实现与应用解耦，从而降低系统的复杂性。例如，电商网站在促销期间抢购订单时，可以将抢到的商品订单信息放入消息队列，然后由出库、发货等后续系统从队列里读取任务信息并执行。

流量削锋和消息通讯：

在流量洪流突然来袭时，可以通过队列服务堆积缓存订单等信息，在下游系统有能力处理消息的时候再处理，避免下游订阅系统因突发流量崩溃。此外，消息队列还提供亿级消息堆积能力，3天的保留时长，消息消费系统可以错峰进行消息处理。

最终一致性：

在交易或支付系统中，不同的子系统/模块的状态需要最终保持一致，或都成功或都失败。子系统/模块之间传递的数据不能丢失，需要有可靠消息传递，能保证业务的连续性。分布式消息服务可以用于子系统/模块间的高可靠数据传递，实现两者之间的事务最终一致，降低实现难度和成本。

总之，消息队列在异步处理、应用解耦、流量削锋和消息通讯、最终一致性等场景中具有广泛的应用价值。

六、完整代码

1、完整代码

1、CirclesQueue.h

/*
	CirclesQueue.h
	循环队列
*/
 
#define MAXSIZE 5
 
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 *);
 
/*输出队列*/
void print(CirclesQueue *Q) ;
 
/*队空*/
int isempty(CirclesQueue *Q);
 
/*获取队列大小*/
int getSize(CirclesQueue *Q);
 
 
/*获取队首元素*/ 
int getFront(CirclesQueue *Q,DataType *x);
 
 

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;
}
 
/*输出队列*/
 
void print(CirclesQueue *Q) 
{
	int i;
	if(isempty(Q))
	{
		printf("队列为空！100002\n");
		return 100002;
	}
	
	i=(Q->front)%MAXSIZE;
	do{
		printf("%d  ",Q->data[(i+1 %MAXSIZE)]);
		i=(i+1)%MAXSIZE;
	} while(i!=Q->rear);
} 
 
/*获取队列中元素个数*/
 
int getSize(CirclesQueue *Q)
{
	return (Q->rear-Q->front+MAXSIZE)%MAXSIZE;
 } 
 
/*获取队首元素*/ 
int getFront(CirclesQueue *Q,DataType *x)
{
	if(isempty(Q))
	{
		printf("队列为空！100002\n");
		return 100002;
	}
	int i;
	i = (Q->front+1) % MAXSIZE;
	*x = Q->data[i];
	return  0;
}
 

3、main.c

#include <stdio.h>
#include "CirclesQueue.h"
 
 
int main(int argc, char* argv[])
{
	CirclesQueue Q;
	DataType x;
	int cmd;
	char yn;
    int num;
 
 
	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~9）：");
		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）？");
			getchar();
			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:	
	     	  print(&Q);
	     	  printf("\n"); 
			break; 
		case 7:	
 	          num=getSize(&Q);
 	          printf("队列大小为%d\n",num); 
           	break; 
    	case 8:	
            if(!getFront(&Q,&x)){
                printf("队首元素是【%d】\n",x); 
			} 
         	break;   
		case 9:	
            printf(" 本程序为循环队列的演示程序，\n有赵梦琪设计开发，程序完成了循环队列基本运算功能！。。。\n"); 
        	break;     	
			
		}
	
	}while(cmd!=0);
 
 
	return 0;
}

2、运行结果

七、总结

循环队列是一种先进先出（FIFO）的数据结构，它可以在固定大小的数组中实现队列的操作。相比于普通队列，循环队列的优点在于其队尾指针可以循环回到数组的开头，使得队列的操作更加高效。

循环队列的应用场景非常广泛，例如在操作系统中实现任务调度、在通信协议中实现数据包的存储和处理、在线程池中管理线程的执行等。循环队列的优点包括高效的插入和删除操作、空间利用率高、可以动态地调整队列大小等。