大家好,又见面了,我是你们的朋友全栈君。
数据结构之循环队列
前言:
关于循环队列需明白以下几点:
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;
}
循环队列运行过程图如下:
程序实际运行结果如下,对比上面出队入队图,也就对循环队列有了更深的理解:
发布者:全栈程序员-用户IM,转载请注明出处:https://javaforall.cn/137272.html原文链接:https://javaforall.cn
【正版授权,激活自己账号】: Jetbrains全家桶Ide使用,1年售后保障,每天仅需1毛
【官方授权 正版激活】: 官方授权 正版激活 支持Jetbrains家族下所有IDE 使用个人JB账号...