计算机科学与编程导论模块13

1、模块十二堆栈与队列（二）堆栈与队列（二）n 队列的定义及其运算队列的定义及其运算n 抽象队列类的定义抽象队列类的定义n 队列的定义及其实现队列的定义及其实现n 队列顺序存储结构队列顺序存储结构n 循环队列循环队列n 链式队列链式队列主要内容主要内容13.6 队列的概念及其运算队列的概念及其运算n队列的概念队列的概念n队列的有关运算队列的有关运算 队列的概念队列的概念n队列简称队列简称队队，是一种只允许在，是一种只允许在表的一端进表的一端进行插入操作行插入操作而在表的而在表的另一端进行删除操作另一端进行删除操作的线性表。的线性表。n允许进行插入的一端称为允许进行插入的一端称为队尾队尾，允许删除，

2、允许删除的一端称为的一端称为队头队头。队列的插入运算也简称。队列的插入运算也简称进队进队，删除运算简称为，删除运算简称为出队出队。n队列也称为队列也称为先进先出表先进先出表(FIFO)。 队列的概念队列的概念n假设假设Q=(a1，a2，an-1，an)为一个队结构，为一个队结构，则队头为则队头为a1，队尾为，队尾为an。该队列是按。该队列是按a1，a2，an-1，an的顺序进入的，退出该队列的顺序进入的，退出该队列也只能按这个顺序进行。也只能按这个顺序进行。n队列和堆栈一样，也是动态结构，同样存在队列和堆栈一样，也是动态结构，同样存在溢出问题，在进行插入、删除运算之前，应溢出问题，在进行插入、

3、删除运算之前，应进行队满、队空的判断。进行队满、队空的判断。 队列的有关运算队列的有关运算n进队：进队：在队列的尾部插入一个新元素在队列的尾部插入一个新元素n出队：出队：删除队列的队头元素删除队列的队头元素n测试队空：测试队空：测试队列是否为空测试队列是否为空n测试队满：测试队满：测试队列是否为满测试队列是否为满n清队：清队：创建一个空队列创建一个空队列 13.3 抽象队列类抽象队列类templateclass abque /定义抽象队列类模板定义抽象队列类模板 protected : int qsize;/队列长度队列长度 public: bool IsEmpty( ) /判队列是否为空判队

4、列是否为空 return (qsize=0)?true:false; virtual void PushTail(type&)=0; /将元素插入队尾将元素插入队尾 virtual bool PopFront(type&)=0; /从对头提取元素从对头提取元素 virtual void Clear( )=0; /清空队列清空队列 ; 13.7 队列的定义与实现队列的定义与实现n队列的顺序存储结构队列的顺序存储结构n循环队列的定义循环队列的定义n循环队列类的定义及常用成员函数的实现循环队列类的定义及常用成员函数的实现n链式队列的定义链式队列的定义n链式队列类的定义及常用成员函数的

5、实现链式队列类的定义及常用成员函数的实现13.7.1 队列的顺序存储结构队列的顺序存储结构n队列的顺序存储结构的实现队列的顺序存储结构的实现n队列的顺序存储结构的特点队列的顺序存储结构的特点n假溢出问题假溢出问题 队列顺序存储结构的实现队列顺序存储结构的实现 n可以用可以用一维数组一维数组来描述队列的顺序存储结构。来描述队列的顺序存储结构。n首先定义一维数组首先定义一维数组elementsmaxsize来存放队来存放队列元素，列元素，同时还需要设置两个变量同时还需要设置两个变量front与与 rear分别指出队头元素和队尾元素的分别指出队头元素和队尾元素的下标下标。n约定约定：队头指针：队头指

6、针front指出实际队头元素所在指出实际队头元素所在位置的位置的前一个位置前一个位置，而队尾指针，而队尾指针rear指出实际指出实际队尾元素队尾元素所在的位置。所在的位置。初始时，初始时，front=rear= -1，测试一个队列是否，测试一个队列是否为空的条件是为空的条件是rear= =front。 以下是队列示意图：以下是队列示意图： 队列顺序存储结构的特点队列顺序存储结构的特点n进行插入运算，必须先测试队满与否。进行插入运算，必须先测试队满与否。若队满，若队满，则调用相关算法处理有关溢出问题；否则，将则调用相关算法处理有关溢出问题；否则，将队尾指针加队尾指针加1，然后将新元素插入到当前队

7、尾指，然后将新元素插入到当前队尾指针所指的位置。针所指的位置。n删除队头元素，必须先测试队列是否为空。删除队头元素，必须先测试队列是否为空。若若队空，则调用相关算法处理有关信息；否则，队空，则调用相关算法处理有关信息；否则，删除队头元素删除队头元素(队头指针加队头指针加1)，如果需要，可以，如果需要，可以把被删除元素保存起来。把被删除元素保存起来。frontrearfrontreara3元素元素a2出队后的状态出队后的状态front rear元素元素a3出队后的状态出队后的状态 假溢出问题假溢出问题n在队列的插入算法中，当队尾指针在队列的插入算法中，当队尾指针rear=maxsize-1时，再

8、做插入运算好象会产生溢出，而实际上这时，再做插入运算好象会产生溢出，而实际上这时队列的前端还有许多空的位置，称为时队列的前端还有许多空的位置，称为“假溢假溢出出”。n解决假溢出问题，有两种办法：解决假溢出问题，有两种办法：1、每次删除队头一个元素后，把每次删除队头一个元素后，把整个队列整个队列往前移往前移动一个位置，过程如图所示。在这种情况下，队动一个位置，过程如图所示。在这种情况下，队头指针头指针front就没有用处了。就没有用处了。 2、可以把队列设想成可以把队列设想成头尾相连头尾相连的循环表，即把的循环表，即把存储队列元素的表从逻辑上看成一个环，这种存储队列元素的表从逻辑上看成一个环，这

9、种队列通常称为队列通常称为循环队列循环队列。循环队列操作图示循环队列操作图示空队列空队列J1,J2,J3J1,J2,J3入队列入队列J1,J2,J3J1,J2,J3出队出队J4,J5,J6J4,J5,J6入队入队rearfront J1J1 J2J2 J3J3 rearfront J6J6 J5J5 J4J4rearfrontrearfront 又有又有J7入队入队,该怎么办？该怎么办？假溢出n存在问题存在问题设数组大小为设数组大小为M，则：则：n当当front=0，rear= M 时，再入队发生溢时，再入队发生溢出出真溢出真溢出n当当front 0，rear= M 时，再入队发生溢时，再入队

10、发生溢出出假溢出假溢出n解决方案解决方案n队首固定，每次出队后将剩余元素向下队首固定，每次出队后将剩余元素向下移动移动浪费时间浪费时间n循环队列循环队列n基本思想：把队列设想成环形，让基本思想：把队列设想成环形，让 elementsM-1 接在接在 elements0 之之后，若后，若rear+1=M，则令则令rear=0;rear123450J4,J5,J6入队入队J4J5J6front0M-11frontrear.实现：利用实现：利用“模模”运算运算入队：入队：elementsrear=e; rear=(rear+1)%M; 出队：出队：e=elementsfront; front=(fr

11、ont+1)%M; 队满、队空判定条件队满、队空判定条件?012345rearfrontJ7J5J6012345frontJ4J9J8rearJ5J6J4012345rearfrontJ4,J5,J6出队出队J7,J8,J9入队入队队空：队空：front=rear解决方案：解决方案：1.另外另外设一个标志设一个标志以区别队空、队以区别队空、队满满2.少用一个元素空间：少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front队满：队满：front=rearJ4,J5,J6出队出队J7,J8入队入队队满：队满：front=(rear+1)%Mn 少用一个元

12、素空间：少用一个元素空间： 队空：队空：front=rear 队满：队满：(rear+1)%M=front队空：队空：front=rearJ5J6J4012345rearfront012345rearfrontJ7J5J6012345frontJ4J8rear在循环队列示意图中，可以看到队列空和队在循环队列示意图中，可以看到队列空和队列满时，都有列满时，都有rear= =front。为区分队空队满，可采用两种处理方法：为区分队空队满，可采用两种处理方法：u设一个设一个标志位标志位以区别队列是空还是满；以区别队列是空还是满；u少用一个元素空间，约定以少用一个元素空间，约定以“队列头指针队列头指针

13、在队列尾指针的下一位置上在队列尾指针的下一位置上”作为队列满作为队列满的标志。的标志。 循环队列的首尾相接，当队头指针循环队列的首尾相接，当队头指针front和队尾指针和队尾指针rear进到进到maxsize-1时，再前进时，再前进一个位置就自动到一个位置就自动到0，利用，利用除法取余除法取余的运算的运算来实现。来实现。插入运算修改队尾指针：插入运算修改队尾指针： rear=(rear+1)%maxsize删除运算修改队头指针：删除运算修改队头指针： front=(front+1)%maxsize11.7.2 循环队列类的定义及常用成员函数的实现循环队列类的定义及常用成员函数的实现templa

14、teclass SeqQuene: public abqueprotected: int head； /队头指针队头指针 int tail; /队尾指针队尾指针 type *elements; /存放队列元素的数组存放队列元素的数组 int maxsize; /队列最大可容纳元素个数队列最大可容纳元素个数 SeqQuene & Copy(SeqQuene & q); /队列拷贝函数队列拷贝函数 public: SeqQuene(int i=10); /构造函数，缺省参数构造函数，缺省参数 SeqQuene( ) /析构函数析构函数 Clear( ); void PushTail

15、 (type &); /将新元素插入在队尾将新元素插入在队尾 bool PopFront (type &); /从队头取一个元素从队头取一个元素 void Clear( ) /清空队列清空队列 delete elements; /重载赋值运算符，用来对同类队列赋值重载赋值运算符，用来对同类队列赋值 SeqQuene & operator=(SeqQuene & q) Copy(q); return *this; bool IsFull( ) const /判队列是否为满判队列是否为满 return(tail+1)%maxsize=head?ture:false;

16、 bool IsEmpty( ) /判队列是否为空判队列是否为空 return head=tail?ture:false; ;const的含义：该成的含义：该成员函数的算法不修改员函数的算法不修改该类的成员变量的值该类的成员变量的值13.7.2 循环队列类的定义及常用成员函数的实现循环队列类的定义及常用成员函数的实现n构造函数构造函数 ：首先将队列设置为空队列，设置队列最首先将队列设置为空队列，设置队列最大长度，为队列分配空间。大长度，为队列分配空间。templateSeqQuene: SeqQuene(int i) head=tail=0; /将队列设置为空队列将队列设置为空队列 maxsi

17、ze=i10?10:i; /设置队列的最大长度，最小为设置队列的最大长度，最小为10 qsize=0; /队列实际长度队列实际长度 elements=new typemaxsize; /给队列分配内存空间给队列分配内存空间 assert(elements!=0); /失败，警告失败，警告n插入运算插入运算(进队进队)：进队之前，先判断队满与否。进队之前，先判断队满与否。 若队满，则退出程序的执行；否则，将队尾指针若队满，则退出程序的执行；否则，将队尾指针加加1后求模，然后将新元素插入到当前队尾指针所后求模，然后将新元素插入到当前队尾指针所在位置，队长加在位置，队长加1。templateSeqQ

18、uene: PushTail(type & x) assert(!IsFull( ); /若队满，警告，出错处理若队满，警告，出错处理 tail=(tail+1)%maxsize; /尾指针加尾指针加1 elementstail=x; /给队尾赋值给队尾赋值 qsize+; /队长加队长加1n删除运算删除运算(出队出队)：删除队头元素之前，先测试队列是否删除队头元素之前，先测试队列是否 为空。若为空，则退出程序；否则，删除队头元素为空。若为空，则退出程序；否则，删除队头元素(队头队头指针加指针加1)，队列长度减，队列长度减1。如果需要，可以把删除的元素。如果需要，可以把删除的元素保存起

19、来。保存起来。templateSeqQuene: PopFront(type & x) assert(!IsEmpty( ); /若队空，警告，出错处理若队空，警告，出错处理 x=elementshead; /取出队头元素取出队头元素 head=(head+1)%maxsize; /头指针加头指针加1 qsize-; /队长减队长减1 return true; n 拷贝函数拷贝函数：将队列将队列que拷贝到当前队列。拷贝到当前队列。templateSeqQuene&SeqQuene:Copy(SeqQuene&que) if(elements) /若当前队列不为空，删除

20、当前队列元素若当前队列不为空，删除当前队列元素 delete elements; maxsize=que.maxsize; qsize=que.qsize; tail=que.tail; head=que.head; /按按que队列的大小，为当前队列分配内存空间队列的大小，为当前队列分配内存空间 elements=new typemaxsize; assert(elements)； /内存分配成功，复制队列的内容内存分配成功，复制队列的内容 memmove(elements, que.elements, sizeof(type)*maxsize); return *this;13.7.4 链

21、式队列的定义链式队列的定义n链式队列的定义链式队列的定义n链式队列类的定义链式队列类的定义n链式队列中常用成员函数的实现链式队列中常用成员函数的实现13.7.4 链式队列的定义链式队列的定义n队列的链式存储结构就是用一个队列的链式存储结构就是用一个线性链表线性链表来来表示队列，简称表示队列，简称链式队链式队；n把线性链表的把线性链表的头指针定义为头指针定义为“队头指针队头指针” head，把链表的，把链表的最后结点指针作为最后结点指针作为“队尾指队尾指针针” tail，并且限定只能在链头进行删除，只，并且限定只能在链头进行删除，只能在链尾进行插入。该线性链表就成为一个能在链尾进行插入。该线性链

22、表就成为一个链式队列；链式队列；n链式队列的队头指针与队尾指针都指向实际链式队列的队头指针与队尾指针都指向实际 的队头与队尾结点。的队头与队尾结点。a1a2anheadtailheadtaila1非空链队列非空链队列空的链队列空的链队列NULLNULLheadtail 链式队列图示链式队列图示u 对如下的一般链接队列：对如下的一般链接队列：u 测试链式队列测试链式队列“是否为空是否为空”的条件为的条件为: head =NULLu 插入一个新元素就是在队尾结点后添加一个新结点插入一个新元素就是在队尾结点后添加一个新结点; u 删除一个元素就是删除链表的第一个结点。删除一个元素就是删除链表的第一个

23、结点。 13.7.5 链式队列类的定义及常用成员函数的实现链式队列类的定义及常用成员函数的实现n队列结点结构的定义队列结点结构的定义templatestruct QueneNode /定义队列的结点类型定义队列的结点类型 type data; /结点数据元素值结点数据元素值 QueneNode *next; /结点指针值结点指针值;n链式队列类的定义链式队列类的定义template /定义链式队列类定义链式队列类class LinkQuene: public abque protected: QueneNode *head; /队头队头 QueneNode *tail; /队尾队尾 /队列拷贝

24、函数队列拷贝函数 LinkQuene & Copy(LinkQuene & q)； public: LinkQuene( ); /构造函数构造函数 LinkQuene(LinkQuene & q) /拷贝构造函数拷贝构造函数 head=NULL; tail=NULL; Copy(q); LinkQuene( ) /析构函数析构函数 Clear( ); void PushTail(type &); /将新元素插入在队尾将新元素插入在队尾 bool PopFront(type &); /从队头取一个元素从队头取一个元素 void Clear( ); /清空队

25、列清空队列 /重载赋值运算符，对同类队列赋值重载赋值运算符，对同类队列赋值 LinkQuene & operator=(LinkQuene & q) Copy(q); return *this; ;11.7.5 链式队列类的定义及常用成员函数的实现链式队列类的定义及常用成员函数的实现n构造函数：构造函数：建立一个空队列。建立一个空队列。template /定义构造函数定义构造函数LinkQuene : LinkQuene( ) head=tail=NULL; qsize=0; /构造一个空队列构造一个空队列 n 进队函数进队函数(入队入队)：链式队列插入运算一般不会链式队列插入

26、运算一般不会溢出。插入运算时可不判断队满，但插入每个结点溢出。插入运算时可不判断队满，但插入每个结点都要动态分配存储空间，要修改头、尾指针。都要动态分配存储空间，要修改头、尾指针。template /向队尾插入元素向队尾插入元素void LinkQuene:PushTail(type & x) QueneNode *p; p=new QueneNode; /建立新结点建立新结点 assert(p)； /分配失败，设置错误信息，返回分配失败，设置错误信息，返回 p-data=x; /给新结点赋值给新结点赋值 if(tail) /若队列非空若队列非空 p-next=NULL; tail-n

27、ext=p; /将新结点链接到队尾将新结点链接到队尾 tail=p; /修改队尾指针修改队尾指针 else /若队列为空若队列为空 p-next=NULL; tail=p; /将将p结点设置为队列头和队列尾结点设置为队列头和队列尾 head=p; qsize+; /队长加队长加1n 出队函数出队函数(出队出队)：删除前，先判断队列是否为空。删除前，先判断队列是否为空。若为空，返回；若非空，先将队头结点数据元素赋给若为空，返回；若非空，先将队头结点数据元素赋给x，再修改队头指针。若队列已删空，应将，再修改队头指针。若队列已删空，应将tail改为改为NULL。修改指针后，应释放。修改指针后，应释放

28、(删除删除)原队头指向的结原队头指向的结点，队列长度减点，队列长度减1。template /从队头取一结点从队头取一结点bool LinkQuene:PopFront(type & x) QueneNode *p; if(head) /若队列非空若队列非空 x=head-data; /将队头结点数据元素值赋给将队头结点数据元素值赋给x p=head; head=head-next; /修改队头，后移一个结点位置修改队头，后移一个结点位置 /修改修改head后，若队列被删空，将后，若队列被删空，将tail改为改为NULL if(head=NULL) tail=NULL; delete p

29、; /删除或释放原队头结点占用的空间删除或释放原队头结点占用的空间 qsize-; /队长减队长减1 return true; return false; /队列空时，返回队列空时，返回falsen 拷贝函数拷贝函数，注意两点：注意两点： 1、 插入每个结点都要动态分配存储空间；插入每个结点都要动态分配存储空间； 2、 头、尾指针都要修改。头、尾指针都要修改。templateLinkQuene& LinkQuene:Copy(LinkQuene&que) QueneNode *p, *q, *r; if(head)/若当前队列非空，先收回队列结点占用的空间若当前队列非空，先收回

30、队列结点占用的空间 Clear( ); qsize=que.qsize; /复制队列长度复制队列长度 head=tail=NULL; if(!que.head) /若若que队列为空，返回队列为空，返回 return *this; /为当前队列结点分配存储空间为当前队列结点分配存储空间 head=new QueneNode; assert(head); /若分配失败，返回若分配失败，返回/将将que队列头结点内容复制给当前队列结点队列头结点内容复制给当前队列结点 head-data=que.head-data; head-next=NULL; /将队列头和尾均指向此结点，因队列只含一个结点将队

31、列头和尾均指向此结点，因队列只含一个结点 tail=head; p=head; /p指向当前队列头指向当前队列头 /将指向队列将指向队列que第二个结点的指针赋给第二个结点的指针赋给q q=que.head-next; while(q) /从第二个结点至队尾进行结点间赋值从第二个结点至队尾进行结点间赋值 r=new QueneNode; /建立一个新结点建立一个新结点 assert(r)； /失败，返回失败，返回 r-data=q-data; /给结点赋值给结点赋值 r-next=NULL; p-next=r; /将新拷贝的结点链接到当前队列尾将新拷贝的结点链接到当前队列尾 tail=r; /

32、队尾指针指向新结点，即最后一个结点队尾指针指向新结点，即最后一个结点 p=p-next; /当前队列指针后移一个结点当前队列指针后移一个结点 q=q-next; /que队列指针后移一个结点队列指针后移一个结点 return *this; n 清清队函数队函数templatevoid LinkQuene:Clear() type p; /从队头至队尾，循环提取队列中各元素（保存从队头至队尾，循环提取队列中各元素（保存 到到p中），实现清除中），实现清除 while(PopFront(p); head=tail=NULL;顺序队列与链式队列的比较顺序队列与链式队列的比较 n顺序队列顺序队列 n固定的存储空间固定的存储空间n方便访问队列内部元素方便访问队列内部元素n链式链式队列队列n可以满足可以满足大小无法估计的情况大小无法估计的情况 n访问队列内部元素不方便访问队列内部元素不方便队列的应用队列的应用 n只要满足先来先服务特性的应用均可采用队只要满足先来先服务特性的应用均可采用队列作为其数据组织方式或中间数据结构。列作为其数据组织方式或中间数据结构。 n调度或缓冲调度或缓冲n消息缓冲器消息缓冲器 n邮件缓冲器邮件缓冲器 n计算机的硬设备之间的通信也需要队列作为数