《数据结构》C语言版——顺序队列

和顺序栈类似，在队列的顺序存储结构中，除了用一组地址连续的存储单元依次存放从队列头到队列尾的元素外，尚需附设两个指针front和rear分别指示队列头元素及队列尾元素的位置。

为了在C语言中描述方便起见，初始化建空队列的时候，令front=rear=0，每次插入新的队列尾元素时，“队尾针增1”；每当删除队列头元素时，“头指针增1”；

因此，在非空队列中，头指针始终指向队列头元素，而队尾指针始终指向队列尾元素的下一个位置，即队尾指针指向的空间是下一个能正常入队的空间，如图：

#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)
{
//入队时,新入队元素是在队尾指针指向当前下标地址进行入队,入队完成后,队尾指针指向下一个下标地址	
	if(Q->rear >= MAXSIZE)//当队尾指针指向的下标与队空间大小相同时,队已满
	return;
	Q->base[Q->rear]=x;
	Q->rear++;
}

/*展示顺序队列元素*/
void ShowQueue(Queue *Q)
{
	printf("顺序队列中存放的元素:");
	for(int i=Q->front;i<Q->rear;++i)
	{
		printf("%d ",Q->base[i]);
	}
	printf("\n");
}

/*出队*/
void DeQueue(Queue *Q)
{
//进队一个元素,队尾指针指向下一个有效的空间(新空间)
//出队一个元素,队头指针指向下一个有效的数据元素
//当某一时刻,出队了一个元素后,队头指针指向下一个(新空间)时,此时说明队头指针和队尾指针都指向队列的同一个下标地址
	if(Q->front==Q->rear)//队列为空
		return;
	Q->front++;
}

/*取队头元素*/
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开始存放数据,进队后,队尾指针指向下一个有效的新空间
	//队列中元素的个数正好是队尾队头所指的下标之差
	//例如队头指针指向0下标,队尾指针指向3下标,此时队中有3(3-0)个元素,即已存放数据在0,1,2下标中
}

/*清除顺序队列*/
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("入队\n");
	for(int i=1;i<=5;++i)
	{
		EnQueue(&Q,i);
	}
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ShowQueue(&Q);
	printf("出队列	");
	DeQueue(&Q);
	GetHead(&Q,&e);
	printf("队头元素为:%d\n",e);
	printf("顺序队的长度为:%d\n",Length(&Q));
	printf("\n");
	ClearQueue(&Q);
	DestroyQueue(&Q);
}

运行结果：