数据结构之循环队列

全栈程序员-用户IM • 2022年6月2日上午10:36 • 未分类

大家好，又见面了，我是你们的朋友全栈君。

数据结构之循环队列

前言：
关于循环队列需明白以下几点：
1、循环队列是队列的顺序存储结构
2、循环队列用判断是否为空利用 Q.front=Q.rear
3、循环队列头指针始终指向队列头元素，而尾指针始终指向队列尾元素的下一个位置
4、按照队列的定义，队头删除，队尾插入，在这里插入图片描述会导致队头之前可能有空余的内存空间（如下图J1，J2出队后，空间被浪费），为了解决该问题，提出循环队列的解决方案

5、循环队列通过浪费一个空间，利用(Q.rear+1)%maxSize=Q.front判断队列是否为满，以此解决队列空间浪费问题（如下图所示）
在这里插入图片描述
一、循环队列的基本操作的实现代码

// 循环队列.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

#define  maxQueueSize 5 //事先确定的最大队列长度

typedef int QElemType;

typedef struct
{
	QElemType *base;//初始化动态分配的指定长度的空间
	int front;//头指针，若队列不空，指向队列头元素
	int rear;//尾指针，若多列不空，指向队列尾元素的下一个位置
}SqQueue;

/*循环队列初始化*/
bool InitQueue(SqQueue *Q)
{
	Q->base=(QElemType*)malloc(maxQueueSize*sizeof(QElemType));
	if (!Q->base)
	{
		return false;
	}
	Q->front=0;
	Q->rear=0;
	printf("循环队列初始化完成！\n");
	return true;
}

/*循环队列入队*/
bool EnQueue(SqQueue *Q,QElemType e)
{
	if ((Q->rear+1)%maxQueueSize==Q->front)//队列满
	{
		return false;
	}
	Q->base[Q->rear]=e;
	Q->rear=(Q->rear+1)%maxQueueSize;
	printf("%d 入队完成！\n",e);
	return true;
}

/*循环队列出队*/
bool DeQueue(SqQueue *Q,QElemType *e)
{
	if (Q->front==Q->rear)//队列空
	{
		return false;
	}
	*e=Q->base[Q->front];
	Q->front=(Q->front+1)%maxQueueSize;
	printf("%d 出队完成！\n",*e);
	return true;
}

/*打印循环队列*/
void printfQueue(SqQueue Q)
{
	printf("打印循环队列如下\n");
	while (Q.front!=Q.rear)
	{
		if (Q.front==maxQueueSize &&(Q.rear+1)%maxQueueSize!=Q.front)
		{
			Q.front=0;
		}
		printf("%d ",Q.base[Q.front]);
		Q.front++;
	}
	printf("\n");
}

int _tmain(int argc, _TCHAR* argv[])
{
	SqQueue *Q=(SqQueue*)malloc(sizeof(SqQueue));
	InitQueue(Q);

	EnQueue(Q,6);
	EnQueue(Q,8);
	EnQueue(Q,10);
	EnQueue(Q,12);
	printfQueue(*Q);
	QElemType *e=(QElemType*)malloc(sizeof(QElemType));
	DeQueue(Q,e);
	DeQueue(Q,e);
	EnQueue(Q,14);
	EnQueue(Q,16);
	printfQueue(*Q);

	system("pause");
	return 0;
}

循环队列运行过程图如下：

程序实际运行结果如下，对比上面出队入队图，也就对循环队列有了更深的理解：
在这里插入图片描述