顺序循环队列表实现2————————————————————————————————作者：————————————————————————————————日期：3队列的基本概念队列也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系与线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作，在其另一端进行删除操作。队列中允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。队头和队尾分别由队头指针和队尾指针指示。队列的插入操作称为入队列，队列的删除操作称为出队列。最先入队列的元素总是最先出队列，所以队列也称为先进先出表。下图是一个一次向队列中插入数据元素a0,a1,a2,⋯.an-1后的示意图，其中，a0是当前队头数据元素，an-1是当前队尾的数据元素。队头队尾a0a1a2⋯⋯an-1<-出<-入队列抽象数据类型数据集合：队列的数据集合可以表示为a0,a1,a2,a3⋯.an-1，每个数据元素的数据类型为DataType。操作集合：（1）初始化QueueInitiate(Q)：初始化队列Q（2）非空否QueueNotEmpty(Q)：队列Q非空否，若队列非空，函数返回值为1。否则，函数返回0。（3）入队列QueueAppend(Q,x)：在队列Q的队尾插入数据元素x。入队列成功返回1；失败则返回0。（4）出队列QueueDelete(Q,d)：把队列Q的队头数据元素删除并由参数d带回。如出队列成功，返回1；失败则返回0。（5）取队头数据元素QueueGet(Q,d)：取队头数据元素并由参数d带回。如取到数据元素返回1，否则，返回0。顺序队列顺序存储结构的队列称作顺序队列4假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。队空和队满的标志问题：队列变为空，队头和队尾指针相等53．顺序循环队列的实现根据对顺序循环队列的分析，其结构体定义如下：typedefstruct{DataTypequeue[MaxQueueSize];intrear;/*队尾指针*/intfront;/*队头指针*/intcount;/*计数器*/}SeqCQueue;采用计数器法判断队列空和满的顺序循环队列的算法实现如下：（1）初始化QueueInitiate(SeqCQueue*Q)voidQueueInitiate(SeqCQueue*Q)/*初始化顺序循环队列Q*/{Q->rear=0;/*定义初始化队尾指针下标值*/Q->front=0;/*定义初始化头指针下标值*/Q->count=0;/*定义初始化计数器值*/}（2）非空否QueueNotEmpty(SeqCQueueQ)intQueueNotEmpty(SeqCQueueQ)/*判断顺序循环队列Q非空否，非空返回1，否则返回0*/{if(Q.count!=0)return1;elsereturn0;}(3)入队列QueueAppend(SeqCQueue*Q,DataTypex)intQueueAppend(SeqCQueue*Q,DataTypex)/*把数据元素值x插入顺序循环队列Q的队尾，成功返回1，失败则返回0*/{6if(Q->count>0&&Q->rear==Q->front)/*判断队列满否*/{printf(“队列已满无法插入!\n”);return0;}else{Q->queue[Q->rear]=x;Q->rear=(Q->rear+1)%MaxQueueSize;Q->count++;return1;}}(4)出队列QueueDelete(SeqCQueue*Q,DataType*d)intQueueDelete(SeqCQueue*Q,DataType*d)/*删除顺序循环队列Q的队头元素并赋给d，成功返回1，失败返回0*/{if(Q->count==0){printf(“队列已空无数据元素出队列!\n”);return0;}else{*d=Q->queue[Q->front];Q->front=(Q->front+1)%MaxQueueSize;Q->count--;return1;}}(5)取队头数据元素QueueGet(SeqCQueueQ,DataType*d)intQueueGet(SeqCQueueQ,DataType*d)/*取顺序循环队列Q的当前队头元素并赋给d，成功返回1，失败返回0*/{if(Q.count==0){printf(“队列已空无数据元素可取!\n”);return0;}else{*d=Q.queue[Q.front];return1;7}}
