【10】Chapter6队列-循环队列.ppt

《【10】Chapter6队列-循环队列.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、数据结构与算法2009年秋季授课教师：张剑波方芳授课班级：111081-4班115081-2班Chapter6队列（Queue）本章教学内容6.1队列结构特性6.2抽象数据类型6.3公式化描述（顺序队列）6.4链表描述（链队列）6.5应用1.火车车厢重排6.1队列结构特性2、几个相关的概念1、定义队列是一种特殊的线性表，是一种只允许在表的一端进行插入操作，而在另一端进行删除操作的线性表。a1a2a3…an入队列出队列队头（front）队尾（rear）3、重要特征每次进队列的元素都放在原队列队尾之后而成为新的队尾元素

2、；每次出队列的数据元素都是原队头元素；先入队列的元素先出队列，后入队列的元素后出队列。队列是一个先进先出的线性表（FirstInFirstOut，FIFO）。如：（1）日常生活中的排队；（2）操作系统中的作业队列。C课堂练习3、设栈S和队列Q的初始状态为空，元素e1，e2，e3，e4，e5和e6依次通过栈S，一个元素出栈后即进队列Q，若6个元素出队的序列是e2，e4，e3，e6，e5，e1，则栈S的容量至少应该是。A、6B、5C、3D、26.2队列的抽象数据类型描述ADTQueue{实例有序线性表，一端称为fron

3、t，一端称为rear操作Create();//创建一个空的队列IsEmpty();//如果队列为空，返回true,否则返回falseIsFull();//如果队列满，返回true,否则返回falseFirst();//返回队列中的第一个元素Last();//返回队列中的最后一个元素Add(x);//向队列添加元素xDelete(x);//删除队首元素，并将它传递给x}队列的两种描述形式队列的物理存储可以用：顺序存储结构链式存储结构a1，a2，a3，…，an出队列入队列队头队尾datalinkfrontrear队列的

4、顺序存储结构，简称顺序队列；顺序队列可用一个一维数组queue[MaxSize]来存储，其中MaxSize是队列能存放的最大元素个数；为了指示队头和队尾，需要设立一个队头指示器和一个队尾指示器，或称队头指针、队尾指针，为了算法设计上的方便，约定：front（头指针）：指向实际队头元素的前一个位置；rear（尾指针）：指向实际队尾元素所在的位置。6.3队列的公式化描述（顺序存储结构）（1）初始化（2）入队列（插入）建立一个空队列，即队头指针front=-1，队尾指针rear=-1。当队满时（队满条件：rear==Ma

5、xSize-1），产生溢出；当队不满时，尾指针加1（rear=rear+1），然后把待插元素x送入尾指针所指数组分量。1、顺序队列的基本操作（3）出队列（删除）当队不空时（队空条件：front==rear），队头指针加1（front=front+1），返回原队头元素，即头指针所指数组分量的值。公式化描述-1location(i)=i–1;front=0，rear为最后一个元素的位置length=rear+1;插入耗时Θ(1)，删除耗时Θ(n)，移动元素!公式化描述-2location(i)=location(1)+

6、i–1;front=location(1)，rear=location(最后一个元素)length=rear-front+1;插入耗时O(n)，删除耗时Θ(1)最坏情况下插入43210432C1B0A432104E3D210front=rear=-1front=-1队列空A，B，C入队列D，E入队列rear=2rear=front=2A，B，C出队列队空front=2rear=42、“假溢出”问题【方法一】按最大可能的进队列操作次数，设置顺序队列的最大元素个数，这种方法很浪费空间，而且有时会因为估计不准而出错；【方

7、法二】修改出队列算法，设每次出队列后，都把队列中剩余数据元素向队头方向移用一个位置，时间复杂度为O(n)，浪费了时间。【方法三】修改入队列算法，当为真溢出时，返回false；当为假溢出时，则把队列中的数据元素向队头方向移动front+1个位置，使队头元素位于队列的最前端后再完成新数据元素的入队操作；当为其它情况时，进队列操作算法同前。此算法的时间复杂度也为O(n)。解决“假溢出”的方法【方法四】将数组的存储区0～MaxSize-1看成是一个首尾相接的环形区域location(i)=(location(1)+i-1)

8、%MaxSize;3、循环队列循环队列的特点循环队列头、尾指针的特点:头指针front：队列中第一个元素的下一个位置（逆时针方向）；尾指针rear：指向队列中最后一个元素。rearfront10……J3J2J1MaxSize-1初始化：front=rear=0;（1）插入或删除一个元素的实现插入：在队尾进行，尾指针向顺时针方向移动一个位置动态描述：rear=