计算机科学与编程导论模块ppt课件.ppt

《计算机科学与编程导论模块ppt课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、模块十二堆栈与队列（二）队列的定义及其运算抽象队列类的定义队列的定义及其实现队列顺序存储结构循环队列链式队列主要内容一队列的概念及其运算队列的概念队列的有关运算队列的概念队列简称队，是一种只允许在表的一端进行插入操作而在表的另一端进行删除操作的线性表。允许进行插入的一端称为队尾，允许删除的一端称为队头。队列的插入运算也简称进队，删除运算简称为出队。队列也称为先进先出表(FIFO)。队列的概念假设Q=(a1，a2，…，an-1，an)为一个队结构，则队头为a1，队尾为an。该队列是按a1，a2，…，an-1，an的顺

2、序进入的，退出该队列也只能按这个顺序进行。队列和堆栈一样，也是动态结构，同样存在溢出问题，在进行插入、删除运算之前，应进行队满、队空的判断。队列的有关运算进队：在队列的尾部插入一个新元素出队：删除队列的队头元素测试队空：测试队列是否为空测试队满：测试队列是否为满清队：创建一个空队列二抽象队列类templateclassabque//定义抽象队列类模板{protected:intqsize;//队列长度public:boolIsEmpty()//判队列是否为空{return(qsize==0)?

3、true:false;}virtualvoidPushTail(type&)=0;//将元素插入队尾virtualboolPopFront(type&)=0;//从对头提取元素virtualvoidClear()=0;//清空队列};三队列的定义与实现队列的顺序存储结构循环队列的定义循环队列类的定义及常用成员函数的实现链式队列的定义链式队列类的定义及常用成员函数的实现队列的顺序存储结构队列的顺序存储结构的实现队列的顺序存储结构的特点假溢出问题队列顺序存储结构的实现可以用一维数组来描述队列的顺序存储结构。首先定义一维

4、数组elements[maxsize]来存放队列元素，同时还需要设置两个变量front与rear分别指出队头元素和队尾元素的下标。约定：队头指针front指出实际队头元素所在位置的前一个位置，而队尾指针rear指出实际队尾元素所在的位置。初始时，front=rear=-1，测试一个队列是否为空的条件是rear==front。以下是队列示意图：队列顺序存储结构的特点进行插入运算，必须先测试队满与否。若队满，则调用相关算法处理有关溢出问题；否则，将队尾指针加1，然后将新元素插入到当前队尾指针所指的位置。删除队头元素，必

5、须先测试队列是否为空。若队空，则调用相关算法处理有关信息；否则，删除队头元素(队头指针加1)，如果需要，可以把被删除元素保存起来。frontrearfrontreara3元素a2出队后的状态frontrear元素a3出队后的状态假溢出问题在队列的插入算法中，当队尾指针rear==maxsize-1时，再做插入运算好象会产生溢出，而实际上这时队列的前端还有许多空的位置，称为“假溢出”。解决假溢出问题，有两种办法：1、每次删除队头一个元素后，把整个队列往前移动一个位置，过程如图所示。在这种情况下，队头指针front就没

6、有用处了。2、可以把队列设想成头尾相连的循环表，即把存储队列元素的表从逻辑上看成一个环，这种队列通常称为循环队列。循环队列操作图示空队列J1,J2,J3入队列J1,J2,J3出队J4,J5,J6入队rearfrontJ1J2J3rearfrontJ6J5J4rearfrontrearfront又有J7入队,该怎么办？？假溢出存在问题设数组大小为M，则：当front=0，rear=M时，再入队发生溢出——真溢出当front0，rear=M时，再入队发生溢出——假溢出解决方案队首固定，每次出队后将剩余元素向下移动——

7、浪费时间循环队列基本思想：把队列设想成环形，让elements[M-1]接在elements[0]之后，若rear+1==M，则令rear=0;rear123450J4,J5,J6入队J4J5J6front0M-11frontrear…...…...实现：利用“模”运算入队：elements[rear]=e;rear=(rear+1)%M;出队：e=elements[front];front=(front+1)%M;队满、队空判定条件?012345rearfrontJ7J5J6012345frontJ4J9J8re

8、arJ5J6J4012345rearfrontJ4,J5,J6出队J7,J8,J9入队队空：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front队满：front==rearJ4,J5,J6出队J7,J8入队队满：front==(rear+1)%M少用一个元