欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

数据结构_循环队列(C语言)

程序员文章站 2022-05-04 17:25:20
...

(一)循环队列图文解析

队列,顾名思义就像我们平时排队打饭一样,队尾有人不断来排队打饭,队头不断有人打完饭离开队头

顺序队列用顺序存储结构,即数组存储,分别包含俩个变量front和rear分别代表队头和队尾,为了防止数组越界溢出,我们将顺序队列变成一个环状的空间,即循环队列,超出数组界队尾重新回到数组的开头,以此防止数组溢出报错。
数据结构_循环队列(C语言)
通过取模,我们可以让顺序队列的存储空间循环使用;假设数组最大空间为6,当Q.front=4,Q.rear=5,则队列长度为1,未达到最大队列长度,如果我们还需要入队,此刻队尾不能再继续在数组中添加数据元素了,那么我们可以使Q.rear=(Q.rear+1)%6,即Q.rear=0,重新回到数组的初始地址,继续入队,于是这就形成了循环队列。

(二) 循环队列代码解析

(1) 循环队列的基本操作

1.1 循环队列的存储结构

#define MAXQSIZE 100
typedef struct{
	int *base;//存储数据元素的数组
	int front;//头指针
	int rear;//尾指针
}SqQueue;

1.2 循环队列的初始化

void InitQueue(SqQueue &Q)
{
	Q.base=(int*)malloc(MAXQSIZE*sizeof(int));//为队列分配空间
	if(!Q.base)
		printf("内存分配失败!\n");
	else
		Q.front=Q.rear=0;//初始化头尾指针都为0,队列为空
}

1.2 循环队列的入队

void EnQueue(SqQueue &Q,int e)
{
	if((Q.rear+1)%MAXQSIZE==Q.front)
		printf("队满!\n");
	else
	{
		Q.base[Q.rear]=e; //队尾入队,给队尾数据赋值
		Q.rear=(Q.rear+1)%MAXQSIZE;	//队尾指针加1
	}
}

1.3 循环队列的出队

void DeQueue(SqQueue &Q,int &e)
{
	if(Q.front==Q.rear)
		printf("队空!");
	else
	{
		e=Q.base[Q.front];//队头出队,清除队头数据
		Q.front=(Q.front+1)%MAXQSIZE;//队头指针加1
	}
}

1.4 循环队列的长度

int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
	//对于循环队列,队尾队头的差值也有可能为负值,所以加上MAXQSIZE再与MAXQSIZE取模
}

1.5 循环队列的头元素

int GetHead(SqQueue Q)
{
	return Q.base[Q.front];
}

1.6 循环队列的尾元素

int GetTail(SqQueue Q)
{
	return Q.base[Q.rear-1];
}

(2) 循环队列源代码及测试

2.1 源代码:

#include<stdio.h>
#include<malloc.h>
#define MAXQSIZE 100
typedef struct{
	int *base;
	int front;
	int rear;
}SqQueue;


void InitQueue(SqQueue &Q)
{
	Q.base=(int*)malloc(MAXQSIZE*sizeof(int));
	if(!Q.base)
		printf("内存分配失败!\n");
	else
		Q.front=Q.rear=0;
}

void EnQueue(SqQueue &Q,int e)
{
	if((Q.rear+1)%MAXQSIZE==Q.front)
		printf("队满!\n");
	else
	{
		Q.base[Q.rear]=e;
		Q.rear=(Q.rear+1)%MAXQSIZE;
	}
}
void DeQueue(SqQueue &Q,int &e)
{
	if(Q.front==Q.rear)
		printf("队空!");
	else
	{
		e=Q.base[Q.front];
		Q.front=(Q.front+1)%MAXQSIZE;
	}
}
int QueueLength(SqQueue Q)
{
	return (Q.rear-Q.front+MAXQSIZE)%MAXQSIZE;
}

int GetHead(SqQueue Q)
{
	return Q.base[Q.front];
}
int GetTail(SqQueue Q)
{
	return Q.base[Q.rear-1];
}
int main()
{
	int e;
	SqQueue Q;
	InitQueue(Q);

	printf("依次入队1,2,3\n");
	EnQueue(Q,1);
	EnQueue(Q,2);
	EnQueue(Q,3);
	printf("队列长度:%d\n",QueueLength(Q));
	printf("队头元素:%d\n",GetHead(Q));
	printf("队尾元素:%d\n",GetTail(Q));

	printf("出队一次\n");
	DeQueue(Q,e);
	printf("队列长度:%d\n",QueueLength(Q));
	printf("队头元素:%d\n",GetHead(Q));
	printf("队尾元素:%d\n",GetTail(Q));
	return 0;
}

2.2 测试结果:

测试环境 : Windows 10
编译软件 : Visual C++ 6.0

数据结构_循环队列(C语言)