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

(一)循环队列图文解析

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

顺序队列用顺序存储结构，即数组存储，分别包含俩个变量front和rear分别代表队头和队尾，为了防止数组越界溢出，我们将顺序队列变成一个环状的空间，即循环队列，超出数组界队尾重新回到数组的开头，以此防止数组溢出报错。

通过取模，我们可以让顺序队列的存储空间循环使用；假设数组最大空间为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