《数据结构》C语言版——循环队列

如果说可以用循环队列解决队列的虚假满的状态，那么什么是虚假满状态？

假设当前顺序队列分配的最大空间是6，当队尾指针从5下标指向6下标时(6下标实际不存在)，说明此时队列已满，然而依然可以进行出队的操作，顺序队不能像顺序栈那样进行存储再分配扩大数组空间，所以队列的实际可用空间并未占满。

循环队列就是将顺序队列构造成为一个环状的队列空间，如图：

注意：

此时当指针front=指针rear时，无法判断队列空间是满还是空，有两种解决思路：
1.另设一个标志位区分队列空间是满还是空；
2.少用一个空间，约定以“队列头指针在队列尾指针的下一位置”作为队列满的状态标志。

来吧！举个栗子吧，如图：
【情况1】

初始化，队头指针front，队尾指针rear都指向0下标；
当存入数据元素1后，队尾指针rear从0下标指向1下标；
当存入数据元素2后，队尾指针rear从1下标指向2下标；
当存入数据元素3后，队尾指针rear从2下标指向3下标；
当存入数据元素4后，队尾指针rear从3下标指向4下标；
…
当存入数据元素8后，队尾指针rear从7下标指向0下标；(队列已满)
如何判断队头指针front与队尾指针rear重合时，队列是空还是满呢？我们假如用flag来标记队头指针front与队尾指针rear的重合状态，于是规定当flag=0时：队列为空；当flag=1时，队列为满。

【情况2】

我们把7下标的空间空出不存放数据，当数据元素7进为6下标的空间后，队尾指针rear就指向了为7下标的空间(此时7下标空间是空的)，理论上8个空间只用了7个空间，但在逻辑上我们规定此时队列已满。当rear+1后，队头指针front与队尾指针rear重合，说明此时队列空间逻辑已满，我们先将队头指针所指空间的元素出队，队头指针前移指向1下标，此时再将元素进下标为7的空间，队尾指针rear前移(指向0下标)，当rear+1后，队头指针front与队尾指针rear又重合，说明此时队列空间逻辑又已满，依次循环往复，出队—>队头指针front前移——>后面入队——>队尾指针rear前移(判断条件是rear+1后，队头指针front与队尾指针rear是否重合，不重合则可继续入队)。

但是，计算机是没有环状的存储空间的，依然是以线性存储的方式，那计算机如何判断什么时候队尾指针再次与队头指针重合呢？

—————OK！那就是：进行模运算—————

具体模运算是怎么实现的，文字显得苍白无力，还是那句话，把代码跑起来，慢慢体会！

#include <stdio.h>
#include <malloc.h>
#include <assert.h>

#define MAXSIZE 8//定义队列初始化存放8个数据元素
typedef int ElmeType;

/*给出顺序队列的结构*/
typedef struct Queue
{
	ElmeType *base;//指针base指向有效的队列空间
	int      front;//队头指针
	int      rear;//队尾指针指向下一个有效的空间
}Queue;

/*初始化顺序队列*/
void InitQueue(Queue *Q)
{
	Q->base=(ElmeType *)malloc(sizeof(ElmeType)*MAXSIZE);//开辟队列空间
	assert(Q->base!=NULL);//断言——是否开辟空间成功
	Q->front=Q->rear=0;//队头指针和队尾指针都指向队列的0下标,此时队列为空
}

/*入队*/
void EnQueue(Queue *Q,ElmeType x)
{
//数据入队后,队尾指针从当前空间指向下一个有效的空间,此时称队尾指针是伪指针;
//当伪指针所指下标+1后正好等于队列空间容量时,此时我们希望伪指针可以重新指向队头,而不是出界,于是进行模运算;

//(Q->rear+1)%MAXSIZE——若模为0,则伪指针恰好指向队列的最后一个有效空间,我们需要让此时的伪指针重新指向0下标而不是最后一个有效空间;
//(始终都要将队列最后一个有效空间空出)循环开始:
	if((Q->rear+1)%MAXSIZE==Q->front)//若伪指针所指下标+1与队头指针指向相同的下标,此时判断为队列逻辑已满
	return;//返回,理论上队列保留了队列最后一个有效空间
	Q->base[Q->rear]=x;//否则队列逻辑不满,继续在队尾指针所指下标进行入队,入队完成后,队尾指针又从当前空间指向下一个有效的空间
	Q->rear=(Q->rear+1)%MAXSIZE;//当逻辑空间满后,模运算实现队尾指针重新指向0下标而不是最后一个有效空间;
}

/*展示顺序队列元素*/
void ShowQueue(Queue *Q)
{
	printf("顺序队列中存放的元素:");
	for(int i=Q->front;i!=Q->rear;)
	{
		printf("%d ",Q->base[i]);//依次打印队头指针所指下标中的数据到队尾指针所指下标中的数据
		i=(i+1)%MAXSIZE;//循环打印,7下标不能打印,重新回到0下标(循环时,队尾下标-队头下标=-1)
	}
	printf("\n");
}

/*出队*/
void DeQueue(Queue *Q)
{
//出队一个元素,队头指针指向下一个有效的数据元素
	if(Q->front==Q->rear)//队头队尾指向相同,队列为空
		return;
	Q->front=(Q->front+1)%MAXSIZE;//队头指针循环,模运算实现队头指针重新指向0下标而不是最后一个有效空间;
}

/*取队头元素*/
void GetHead(Queue *Q,ElmeType *v)//指针v带回队头元素
{
//要获取队头,前提是队列不空
	if(Q->front==Q->rear)//队列为空
	return;
	*v=Q->base[Q->front];//必须在base所指的空间里取元素
}

/*顺序队列的长度*/
int Length(Queue *Q)
{
	return (Q->rear - Q->front);
	//下标0开始存放数据,进队后,队尾指针指向下一个有效的新空间
	//队列中元素的个数正好是队尾队头所指的下标之差
	//但是当队列逻辑空间满后,再存储数据需要先出队,再进行入队,此时队尾队头所指的下标之差为-1
}

/*清除顺序队列*/
void ClearQueue(Queue *Q)
{
	Q->front=Q->rear=0;//队列置为空
}

/*销毁顺序队列*/
void DestroyQueue(Queue *Q)
{
	free(Q->base);//释放base所指的队列空间
	Q->base=NULL;//预防野指针
}
/**/

void main()
{
	Queue Q;
	ElmeType e;//定义队头元素
	InitQueue(&Q);//&Q是传入队列的地址
	printf("将1,2,3,4,5,6,7,8依次入队\n");
	for(int i=1;i<=8;++i)
	{
		EnQueue(&Q,i);
	}
	ShowQueue(&Q);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	printf("进行出队\n");
	DeQueue(&Q);
	ShowQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("\n");
	printf("将元素10入队\n");
	EnQueue(&Q,10);
	ShowQueue(&Q);
	printf("\n");
	printf("进行出队\n");
	DeQueue(&Q);
	ShowQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("\n");
	printf("将元素20入队\n");
	EnQueue(&Q,20);
	ShowQueue(&Q);
	printf("\n");
	ClearQueue(&Q);
	DestroyQueue(&Q);
}

运行结果：