《数据结构队列》PPT课件.ppt

《《数据结构队列》PPT课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第五章队列5.1何谓队列队列数据结构规定：在有序列表中数据的输出、输入是分别由不同端进行处理，输出端称为前端(front)，输入端称为后端(rear)，这样会使得先存入的数据会先被取出，也就是具有先进先出FIFO的特性。1队列的应用也很多，下面列出几个较常见的：1.图形的广度优先搜索法。2.优先队列，此种队列在取出元素时是根据所存元素的某项特性值或优先权而取出具最小或最大数值的元素。3.操作系统中的工作调度，若工作的优先权相同，则采用先到先做的原则。4.用于“spooling”(假脱机，信息暂存,当信息需进一步处理时，对其进行暂时存贮)，先将输出数据写在磁盘上，再由打印机把先存入者先处理的顺

2、序将数据输出。队列和堆栈一样也可使用两种结构：数组结构和链表结构。2抽象数据类型Queue元素：无限制，由应用决定结构：保持元素先进先出的特性。操作：(1)voidInit(Queue&Q)//初始化生成一个空栈(2)voidAddqueue(Elemente,Queue&Q)/入队操作(3)voidDelqueue(Elment&e,Queue&Q)//出队操作(4)ElementTop(QueueQ)//读队首元素值(5)boolEmpty(QueueQ)//判队列空操作(6)boolFull(QueueQ)//判队列满操作35.2用数组仿真队列队列本身是有序列表，若使用数组的结构来存储

3、队列的结构，则队列结构数组的声明如下:structqueue{intqueue[MaxSize]；intfront；intrear；}其中MaxSize是该队列的最大容量。因为队列的输出、输入分别从前后端来处理，因此需要两个变量front和rear分别记录队列前后端的索引值，front会随着数据输出而变动，而rear则是随着数据输入而改变。4初始化队列voidinit(queue&q){q.front=-1;q.rear=-1;}5判断队列空empty函数boolempty(queueq){return(q.front==q.rear);}6判断队列满full函数boolfull(queue

4、q){return(q.rear==maxsize-1);}7当我们将数据存入队列时称为“addqueue”，addqueue的处理主要有两个步骤：(1)将队尾指针往前移：rear+1；(2)若尾指针rear小于等于队列的最大索引值MaxSize-1，则将数据存入rear所指的数组元素中，否则无法存入数据。8入队addqueue函数voidaddqueue(queue&q,charx){q.rear++;q.data[q.rear]=x;}9从队列中取出数据项称为“delqueue”，delqueue的操作可分为4个步骤：(1)检查队列中是否有数据存在。(2)若头指针front等于尾指针re

5、ar，则表示队列中无数据。(3)若头指针front不等于尾指针rear，则将队列头指针往前移front+1。(4)取出队头指针所指的数组元素内容。10出队delqueue函数voiddelqueue(queue&q,char&x){q.front++;x=q.data[q.front];}11显示队列数据print函数voidprint(queueq){inti;for(i=q.front+1;i<=q.rear;i++)cout<

6、ructnode{chardata;node*next;};structqueue{node*front,*rear;};其中front和rear是作为队列前后端的输出、输入指针的控制，由于刚刚建立的队列为空，故先将front和rear指向NULL。13初始化队列voidinit(queue&q){q.front=q.rear=NULL;}14判断队列空empty函数boolempty(queueq){returnq.front==NULL;}15队列数据的输入是从后端rear进行，其步骤如下：步骤1：将rear指针所指位置的next指针指向新节点步骤2：将rear指针移动到新节点之上。16

7、入队addqueue函数voidaddqueue(queue&q,charx){node*New;New=(node*)new(node);New->data=x;New->next=NULL;if(q.rear==NULL)q.front=q.rear=New;else{q.rear->next=New;q.rear=New;}}17数据输出是从队列的前端front处理，其步骤如下：步骤1：先保留对头指针f