顺序循环队列的表示和实现

《顺序循环队列的表示和实现》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。

1、队列的基本概念队列也是一种特殊的线性表，队列的数据元素以及数据元素间的逻辑关系与线性表完全相同，其差别是线性表允许在任意位置插入和删除，而队列只允许在其一端进行插入操作，在其另一端进行删除操作。队列中允许进行插入操作的一端称为队尾。允许进行删除操作的一端称为队头。队头和队尾分别由队头指针和队尾指针指示。队列的插入操作称为入队列，队列的删除操作称为出队列。最先入队列的元素总是最先出队列，所以队列也称为先进先出表。下图是一个一次向队列中插入数据元素a0,a1,a2,….an-1后的示意图，其中，a0是当前队头数据元素，an-1是当前队尾的数据元素。队头队尾a0a1a2……an-1<-出<

2、-入队列抽象数据类型数据集合：队列的数据集合可以表示为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)：取队

3、头数据元素并由参数d带回。如取到数据元素返回1，否则，返回0。顺序队列顺序存储结构的队列称作顺序队列假设为队列开辟的数组单元数目为MAX_QUEUE，在C语言中，它的下标在0~MAX_QUEUE-1之间，若增加队头或队尾指针，可以利用取模运算（一个整数数值整除以另一个整数数值的余数）实现。如下所示：front=(front+1)%MAX_QUEUE；rear=(rear+1)%MAX_QUEUE；当front或rear为MAXQUEUE-1时，上述两个公式计算的结果就为0。这样，就使得指针自动由后面转到前面，形成循环的效果。队空和队满的标志问题：队列变为空，队头和队尾指针相等3．顺序

4、循环队列的实现根据对顺序循环队列的分析，其结构体定义如下：typedefstruct{DataTypequeue[MaxQueueSize];intrear;/*队尾指针*/intfront;/*队头指针*/intcount;/*计数器*/}SeqCQueue;采用计数器法判断队列空和满的顺序循环队列的算法实现如下：（1）初始化QueueInitiate(SeqCQueue*Q)voidQueueInitiate(SeqCQueue*Q)/*初始化顺序循环队列Q*/{Q->rear=0;/*定义初始化队尾指针下标值*/Q->front=0;/*定义初始化头指针下标值*/Q->coun

5、t=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*/{if(Q->count>0&&Q->rear==Q->front)/*判断队列满

6、否*/{printf(“队列已满无法插入!”);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(“队列已空无数据元素出队列!”);return0;}else{*d=Q->queue

7、[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(“队列已空无数据元素可取!”);return0;}els