详解循环队列_循环队列的性质

一.定义

循环队列是一种使用数组实现，能够高效地处理队列元素的入队和出队操作的数据结构。它通过将队列的头部和尾部相连，形成一个逻辑上的环状空间，从而避免了队列空间的浪费。循环队列通过维护头指针和尾指针来跟踪队列状态，入队和出队操作都在固定位置进行。循环队列提高了队列的利用率，且具有较好的时间复杂度。

二.特点

1.固定大小的数组：

循环队列使用固定大小的数组来存储元素。这个数组的大小在创建队列时就确定，通常不会动态扩展或缩小。

2.循环性质：

循环队列的一个关键特点是它的队列是循环的。当"rear"指针到达数组的末尾时，下一个元素将从数组的开头插入。这意味着队列可以循环利用数组的空间，避免了数组满了之后无法插入新元素的问题。

3.双指针：

循环队列使用两个指针，分别是"front"（前指针）和"rear"（后指针）。"front"指针指向队列的第一个元素，"rear"指针指向队列的最后一个元素。这些指针的位置关系可以用来判断队列的状态（空或满）以及执行入队和出队操作。

4.高效的入队和出队操作：

由于循环队列的特性，入队和出队操作通常非常高效。入队操作只需在"rear"指针指向的位置插入元素并移动"rear"指针，出队操作只需移除"front"指针指向的元素并移动"front"指针。这些操作的时间复杂度通常是O(1)。

5.判空和判满：

循环队列有两种状态，即空队列和满队列。你可以使用指针的位置关系来判断队列是否为空（"front" == "rear"）或满（("rear" + 1) % 数组大小 == "front"）

6.有限大小：

由于数组大小是固定的，循环队列的容量有限。这意味着在队列满时，无法再插入更多元素，除非出队一些元素来腾出空间。

7.适用于环形数据存储需求：

循环队列通常用于需要周期性地循环存储数据的应用场景，如缓冲区管理、任务调度等。

8.需要小心管理大小和元素数量：

由于固定的容量，循环队列需要小心管理队列的大小和元素数量，以避免数据溢出或元素丢失的问题。

三.基本运算

1.初始化：

创建一个循环队列时，需要初始化队列的数组大小，以及"front" 和 "rear" 指针的初始位置。通常，"front" 和 "rear" 初始化为相同的值，表示空队列。

2.入队操作：

入队操作用于将元素添加到队列中。这包括将元素插入到"rear"指针所指向的位置，然后将"rear"指针向后移动。如果队列已满（即"rear" + 1 等于 "front"，考虑循环性质），则入队操作失败。

3.出队操作：

出队操作用于移除队列中的元素。这包括从"front"指针所指向的位置移除元素，然后将"front"指针向后移动。如果队列为空（即"front" 和 "rear" 指向相同位置），则出队操作失败。

4.判空和判满：

通过检查"front" 和 "rear" 指针的位置关系，可以判断队列是否为空（"front" == "rear"）或满（("rear" + 1) % 数组大小 == "front"，考虑循环性质）。

5.获取队列大小：

可以通过计算"rear"和"front"指针的位置关系来获取队列中元素的数量。

四.代码实现

1.定义接口

#define MAXSIZE 100
 
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 *);
 
/*队空*/
int isempty(CirclesQueue *Q);
 
// 输出队列内容  
void printQueue(CirclesQueue *Q);
 
// 获取队列长度  
int getLength(CirclesQueue *Q);
 
// 获取队首元素
DataType getFront(CirclesQueue* Q);

2.初始化

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

3.入队 

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

4.队满

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

5.出队

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

6.队空

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

8.获取队列长度

// 输出队列内容  
void printQueue(CirclesQueue *Q) {
    int i;
    if (isempty(Q)) {  
        printf("Queue is empty.\n");  
        return;  
    }  
    i = (Q -> front) %MAXSIZE;
    do{
        printf(" %d",Q -> data[(i + 1 % MAXSIZE)]);
        i = (i+1) %MAXSIZE;
    }while(i != Q -> rear);
}

9.获取队首元素

  
DataType getFront(CirclesQueue* Q) {  
    int i;
    i = (Q -> front) %MAXSIZE;
    return Q -> data[(i + 1 % MAXSIZE)];
}// 获取队首元素

五.运行截图

六.完整代码

1.CirclesQueue.h

#define MAXSIZE 100
 
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 *);
 
/*队空*/
int isempty(CirclesQueue *Q);
 
// 输出队列内容  
void printQueue(CirclesQueue *Q);
 
// 获取队列长度  
int getLength(CirclesQueue *Q);
 
// 获取队首元素
DataType getFront(CirclesQueue* Q);

2.CirclesQueue.c

#include <stdio.h>
#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 printQueue(CirclesQueue *Q) {
    int i;
    if (isempty(Q)) {  
        printf("Queue is empty.\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) {  
    return (Q->rear - Q->front + MAXSIZE) % MAXSIZE; // 循环队列：若rear在前方，则长度为rear-front+MAXSIZE，否则为rear-front  
} 
 
// 获取队首元素  
DataType getFront(CirclesQueue* Q) {  
    int i;
    i = (Q -> front) %MAXSIZE;
    return Q -> data[(i + 1 % MAXSIZE)];
}

3.main.c

#include <stdio.h>
#include "CirclesQueue.h"
#include <string.h>
#include <stdlib.h>
 
int main(int argc, char* argv[])
{
	CirclesQueue Q;
	DataType x;
	int cmd;
	char yn;
int result;
    char welcome[] = "欢迎使用";
	int i = 0; 
	int m = 0; 
	int n = 0;
    for(i=0;i<strlen(welcome);i++)
	{
		printf("%c",welcome[i]);
		for(m=0;m<10000;m++)
			for(n=0;n<1000;n++)
			{
				;
			}
	}
	printf("\n\n\n");
 
	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）？");
			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:
			printf("队列的长度：%d\n",getLength(&Q));
			break;
		case 7:
		    printf("队列首元素: %d\n", getFront(&Q));  
            break;
		case 8:
			printf("输出队列：");
			printQueue(&Q);
			printf("\n");
			break;
		case 9:
		    printf("本程序由李英豪设计开发\n");
		    break;
		}
 
	}while(cmd!=0);
 
 
	return 0;
}

七.小结

循环队列（Circular Queue）是一种基于数组或链表的队列数据结构，具有以下要点和小结：

1. 定义和特点：

   • 循环队列是一种队列数据结构，其底层数据结构可以是数组或链表。
   • 与普通队列不同，循环队列允许队列的头尾相连，形成一个循环结构，从而充分利用存储空间。
   • 循环队列的特点包括快速入队和出队操作，适用于需要循环利用队列空间的场景。

2. 基本操作：

   • 循环队列的基本操作包括初始化、入队、出队、判空、判满等。
   • 入队操作将元素添加到队尾，出队操作从队头移除元素。
   • 需要维护队头和队尾指针，它们在队列为空时指向同一位置，而在队列不为空时分别指向队头和队尾的元素。

3. 循环利用空间：

   • 循环队列允许在队列尾部添加元素，当队尾达到队列的最大容量时，它可以循环回到队列的开头，从而充分利用存储空间。
   • 这意味着队列的操作不会因为队列尾部满而停止，而是可以继续在队列开头添加元素。

4. 高效性：

   • 循环队列的入队和出队操作通常具有常数时间复杂度，因为它们只涉及指针的移动和数组的访问。

5. 容量限制：

   • 循环队列的容量是固定的，由数组或链表的大小决定。一旦达到容量上限，队列被认为是满的，无法再容纳更多元素。

6. 应用：

   • 循环队列适用于需要循环利用队列空间的问题，如缓冲区管理、任务调度、广度优先搜索（BFS）等。

7. 复杂性：

   • 循环队列的实现相对较复杂，需要特别注意循环队列的维护，包括队头和队尾指针的更新。

8. 解决问题：

   • 循环队列通常用于解决需要在队列尾部添加元素并保持队列的循环性质的问题。

总之，循环队列是一种高效的、有界容量的队列数据结构，适用于需要循环利用队列空间的问题。它的循环性质和高效性使其在多种应用中具有优势，但需要谨慎维护队头和队尾指针以确保正确操作。