队列的顺序存储结构(循环队列)

// c3-3.h 队列的顺序存储结构(循环队列)(见图3.31)
#define MAX_QSIZE 5 // 最大队列长度+1
struct SqQueue
{
	QElemType *base; // 初始化的动态分配存储空间
	int front; // 头指针，若队列不空，指向队列头元素
	int rear; // 尾指针，若队列不空，指向队列尾元素的下一个位置
};

// bo3-3.cpp 循环队列(存储结构由c3-3.h定义)的基本操作(9个)
void InitQueue(SqQueue &Q)
{ // 构造一个空队列Q(见图3.32)
	Q.base=(QElemType *)malloc(MAX_QSIZE*sizeof(QElemType));
	if(!Q.base) // 存储分配失败
		exit(OVERFLOW);
	Q.front=Q.rear=0;
}
void DestroyQueue(SqQueue &Q)
{ // 销毁队列Q，Q不再存在(见图3.33)
	if(Q.base)
		free(Q.base);
	Q.base=NULL;
	Q.front=Q.rear=0;
}
void ClearQueue(SqQueue &Q)
{ // 将Q清为空队列(见图3.32)
	Q.front=Q.rear=0;
}
Status QueueEmpty(SqQueue Q)
{ // 若队列Q为空队列，则返回TRUE；否则返回FALSE
	if(Q.front==Q.rear) // 队列空的标志
		return TRUE;
	else
		return FALSE;
}
int QueueLength(SqQueue Q)
{ // 返回Q的元素个数，即队列的长度
	return(Q.rear-Q.front+MAX_QSIZE)%MAX_QSIZE;
}
Status GetHead(SqQueue Q,QElemType &e)
{ // 若队列不空，则用e返回Q的队头元素，并返回OK；否则返回ERROR
	if(Q.front==Q.rear) // 队列空
		return ERROR;
	e=Q.base[Q.front];
	return OK;
}
Status EnQueue(SqQueue &Q,QElemType e)
{ // 插入元素e为Q的新的队尾元素(见图3.34)
	if((Q.rear+1)%MAX_QSIZE==Q.front) // 队列满
		return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%MAX_QSIZE;
	return OK;
}
Status DeQueue(SqQueue &Q,QElemType &e)
{ // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR(见图3.35)
	if(Q.front==Q.rear) // 队列空
		return ERROR;
	e=Q.base[Q.front];
	Q.front=(Q.front+1)%MAX_QSIZE;
	return OK;
}
void QueueTraverse(SqQueue Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()
	int i;
	i=Q.front;
	while(i!=Q.rear)
	{
		vi(Q.base[i]);
		i=(i+1)%MAX_QSIZE;
	}
	printf("
");
}

// main3-3.cpp 循环队列检验bo3-3.cpp的主程序
#include"c1.h"
typedef int QElemType;
#include"c3-3.h"
#include"bo3-3.cpp"
void print(QElemType i)
{
	printf("%d ",i);
}
void main()
{
	Status j;
	int i=0,l;
	QElemType d;
	SqQueue Q;
	InitQueue(Q);
	printf("初始化队列后，队列空否？%u(1:空0:否)
",QueueEmpty(Q));
	printf("请输入整型队列元素(不超过%d个),-1为提前结束符: ",MAX_QSIZE-1);
	do
	{
		scanf("%d",&d);
		if(d==-1)
			break;
		i++;
		EnQueue(Q,d);
	}while(i<MAX_QSIZE-1);
	printf("队列长度为%d
",QueueLength(Q));
	printf("现在队列空否？%u(1:空0:否)
",QueueEmpty(Q));
	printf("连续%d次由队头删除元素,队尾插入元素:
",MAX_QSIZE);
	for(l=1;l<=MAX_QSIZE;l++)
	{
		DeQueue(Q,d);
		printf("删除的元素是%d,请输入待插入的元素: ",d);
		scanf("%d",&d);
		EnQueue(Q,d);
	}
	l=QueueLength(Q);
	printf("现在队列中的元素为
");
	QueueTraverse(Q,print);
	printf("共向队尾插入了%d个元素
",i+MAX_QSIZE);
	if(l-2>0)
		printf("现在由队头删除%d个元素: 
",l-2);
	while(QueueLength(Q)>2)
	{
		DeQueue(Q,d);
		printf("删除的元素值为%d
",d);
	}
	j=GetHead(Q,d);
	if(j)
		printf("现在队头元素为%d
",d);
	ClearQueue(Q);
	printf("清空队列后, 队列空否？%u(1:空0:否)
",QueueEmpty(Q));
	DestroyQueue(Q);
}

代码的运行结果：

/*
现在队列空否？0(1:空0:否)
连续5次由队头删除元素,队尾插入元素:
删除的元素是1,请输入待插入的元素: 4
删除的元素是2,请输入待插入的元素: 5
删除的元素是4,请输入待插入的元素: 6
删除的元素是4,请输入待插入的元素: 7
删除的元素是5,请输入待插入的元素: 8
现在队列中的元素为
6 7 8
共向队尾插入了8个元素
现在由队头删除1个元素:
删除的元素值为6
现在队头元素为7
清空队列后, 队列空否？1(1:空0:否)
Press any key to continue

*/

c3-3.h 所采用的循环顺序队列存储结构，当队列长度大于MAX_QSIZE-1 时，无法动
态地增加存储空间，原因是MAX_QSIZE 是固定于c3-3.h 中的常量。为了使循环队列也
能动态地增加存储空间，不固定队列长度，把队列长度也作为结构体的一个成员。前述
c3-4.h 就可以作为这种循环顺序队列的存储结构，bo3-8.cpp 是基于c3-4.h 结构的循环顺
序队列的基本操作。

// bo3-8.cpp 循环队列(存储结构由c3-4.h定义)的基本操作(4个)
int QueueLength(SqQueue2 Q) // 返回Q的元素个数，即队列的长度
{ 
	return(Q.rear-Q.front+Q.queuesize)%Q.queuesize;
}
void EnQueue(SqQueue2 &Q,QElemType e)// 插入元素e为Q的新的队尾元素(见图3.36)
{ 
	int i;
	if((Q.rear+1)%Q.queuesize==Q.front) // 队列满，增加存储单元
	{ 
		Q.base=(QElemType *)realloc(Q.base,(Q.queuesize+QUEUE_INCREMENT)*sizeof(QElemType));
		if(!Q.base) // 增加单元失败
			exit(ERROR);
		if(Q.front>Q.rear) // 形成循环
		{
			for(i=Q.queuesize-1;i>=Q.front;i--)
				Q.base[i+QUEUE_INCREMENT]=Q.base[i]; // 移动高端元素到新的高端
			Q.front+=QUEUE_INCREMENT; // 移动队头指针
		}
		Q.queuesize+=QUEUE_INCREMENT; // 增加队列长度
	}
	Q.base[Q.rear]=e; // 将e插入队尾
	Q.rear=++Q.rear%Q.queuesize; // 移动队尾指针
}
Status DeQueue(SqQueue2 &Q,QElemType &e)
{ // 若队列不空，则删除Q的队头元素，用e返回其值，并返回OK；否则返回ERROR(见图3.37)
	if(Q.front==Q.rear) // 队列空
		return ERROR;
	e=Q.base[Q.front]; // 用e返回队头元素
	Q.front=++Q.front%Q.queuesize; // 移动队头指针
	return OK;
}
void QueueTraverse(SqQueue2 Q,void(*vi)(QElemType))
{ // 从队头到队尾依次对队列Q中每个元素调用函数vi()
	int i=Q.front; // i指向队头
	while(i!=Q.rear) // 没到队尾
	{
		vi(Q.base[i]); // 调用函数vi()
		i=++i%Q.queuesize; // 向后移动i指针
	}
	printf("
");
}

// main3-8.cpp 循环且可增加存储空间的顺序队列，检验bo3-8.cpp的主程序
#include"c1.h"
typedef int QElemType;
#include"c3-4.h"
#include"bo3-4.cpp" // 基本操作(1)，与非循环同
#include"bo3-8.cpp" // 基本操作(2)，与非循环不同
void print(QElemType i)
{
	printf("%d ",i);
}
void main()
{
	Status j;
	int i,n=11;
	QElemType d;
	SqQueue2 Q;
	InitQueue(Q);
	printf("初始化队列后，队列空否？%u(1:空0:否)
",QueueEmpty(Q));
	printf("队列长度为%d
",QueueLength(Q));
	printf("请输入%d个整型队列元素:
",n);
	for(i=0;i<n;i++)
	{
		scanf("%d",&d);
		EnQueue(Q,d);
	}
	printf("队列长度为%d
",QueueLength(Q));
	printf("现在队列空否？%u(1:空0:否)
",QueueEmpty(Q));
	printf("现在队列中的元素为
");
	QueueTraverse(Q,print);
	for(i=1;i<=3;i++)
		DeQueue(Q,d);
	printf("由队头删除3个元素，最后删除的元素为%d
",d);
	printf("现在队列中的元素为
");
	QueueTraverse(Q,print);
	j=GetHead(Q,d);
	if(j)
		printf("队头元素为%d
",d);
	else
		printf("无队头元素(空队列)
");
	for(i=1;i<=5;i++)
		EnQueue(Q,i);
	printf("依次向队尾插入1～5，现在队列中的元素为
");
	QueueTraverse(Q,print);
	ClearQueue(Q);
	printf("清空队列后, 队列空否？%u(1:空0:否)
",QueueEmpty(Q));
	j=GetHead(Q,d);
	if(j)
		printf("队头元素为%d
",d);
	else
		printf("无队头元素(空队列)
");
	DestroyQueue(Q);
}

代码运行的结果：