// 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("\n");
}
// 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:否)\n",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\n",QueueLength(Q));
printf("现在队列空否？%u(1:空0:否)\n",QueueEmpty(Q));
printf("连续%d次由队头删除元素,队尾插入元素:\n",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("现在队列中的元素为\n");
QueueTraverse(Q,print);
printf("共向队尾插入了%d个元素\n",i+MAX_QSIZE);
if(l-2>0)
printf("现在由队头删除%d个元素: \n",l-2);
while(QueueLength(Q)>2)
{
DeQueue(Q,d);
printf("删除的元素值为%d\n",d);
}
j=GetHead(Q,d);
if(j)
printf("现在队头元素为%d\n",d);
ClearQueue(Q);
printf("清空队列后, 队列空否？%u(1:空0:否)\n",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("\n");
}
// 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:否)\n",QueueEmpty(Q));
printf("队列长度为%d\n",QueueLength(Q));
printf("请输入%d个整型队列元素:\n",n);
for(i=0;i<n;i++)
{
scanf("%d",&d);
EnQueue(Q,d);
}
printf("队列长度为%d\n",QueueLength(Q));
printf("现在队列空否？%u(1:空0:否)\n",QueueEmpty(Q));
printf("现在队列中的元素为\n");
QueueTraverse(Q,print);
for(i=1;i<=3;i++)
DeQueue(Q,d);
printf("由队头删除3个元素，最后删除的元素为%d\n",d);
printf("现在队列中的元素为\n");
QueueTraverse(Q,print);
j=GetHead(Q,d);
if(j)
printf("队头元素为%d\n",d);
else
printf("无队头元素(空队列)\n");
for(i=1;i<=5;i++)
EnQueue(Q,i);
printf("依次向队尾插入1～5，现在队列中的元素为\n");
QueueTraverse(Q,print);
ClearQueue(Q);
printf("清空队列后, 队列空否？%u(1:空0:否)\n",QueueEmpty(Q));
j=GetHead(Q,d);
if(j)
printf("队头元素为%d\n",d);
else
printf("无队头元素(空队列)\n");
DestroyQueue(Q);
}
代码运行的结果：
