队列及其应用.ppt

《队列及其应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、☞5.1队列的基本概念5.2顺序队列及其基本算法5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用☞5.1.1队列的定义5.1.2队列的基本运算5.1队列的基本概念定义队列是满足下列条件的数据元素集合：(1)有限个具有相同数据类型的数据元素的集合，D={ai

2、i=1，2，…，n}，ai为数据元素。(2)数据元素之间的关系为R={

3、ai，ai+1∈D，i=1，2，…，n}；(3)a1为队头元素，an为队尾元素；数据元素按a1，a2，…，an的次序入队，也以相同的次序出队。由定义可以看出，队列是由一组同类型数据元素(a1，a2，…，an)组

4、成的线性序列。其中，ai(1≤i≤n)可以是原子类型(如整型、实型、字符型等)、或是结构类型的数据元素。在一个队列中，元素ai-1是ai的唯一直接前驱，ai+1是ai的唯一直接后继；而队头元素a1无前驱，队尾元素an无后继。因此，队列属于线性逻辑结构。即：队列是限定仅在一端进行插入，而在另一端进行删除操作的线性表。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,…an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,…an，也就是说队列的修改是依先进先

5、出的原则进行的。队列的特点☞根据队列的定义可知，最先入队的元素也是最先出队。☞特点：先进先出（FIFO）也就是说，队列是一种先进先出(FirstInFirstOut)的线性表，简称为FIFO表。a1a2a3…………an出队列入队列队头front队尾rear5.1.1队列的定义☞5.1.2队列的基本运算5.1队列的基本概念☞定义在该逻辑结构上的运算有以下几种基本运算：(1)置空队：InitQueue(Q)，InitQueue运算的结果是将队列Q置成空队列。(2)判队空：QueueEmpty(Q)，如果队列为空，则QueueEmpty返回1，否则QueueEmpty返回

6、0。(3)判队满：QueueFull(Q)，如果队满，则QueueFull返回1，否则QueueFull返回0。(4)入队：Add(Q，x)，Add在队列Q的队尾插入元素x。(5)出队：Delete(Q)，Delete从队列Q中删除队头元素。5.1队列的基本概念☞5.2顺序队列及其基本算法5.3链队列及其基本算法5.4队列的应用举例第5章队列及其应用☞5.2.1顺序队列的概念及数据类型5.2.2循环队列5.2.3循环队列的运算实现5.2顺序队列及其基本算法☞采用顺序存储结构的队列称为顺序队列。☞它是利用一批地址连续的存储单元依次存放自队头到队尾的数据元素,同时设一个

7、尾指针rear指向队尾元素的当前位置。☞由于队列的操作是删除在头、插入在尾，可另设一头指针front指向队头的位置，我们约定指向队头的前一个位置。☞通常用一维数组来实现队列的顺序存储。顺序队列typedefstruct{datatypedata[maxlen];intfront,rear;}SeqQueue;SeqQueue*Q;0123maxlen-1nfrontrear··················dataQ顺序队列的数据类型：0123maxlen-1nfrontrear··················dataQ☞front和rear的初始值在队列初始

8、化时均置为０。☞入队时尾指针加１，并将新元素插入所指的位置。出队时头指针加１，然后删去所指的元素，并返回被删元素。约定：在非空队列里，头指针始终指向队头元素前的空位，而尾指针始终指向队尾元素。０　１　２　３0123(a)队列初始为空０　１　２　３（c)a出队frontrearfront（b）a,b,c入队abcfrontabcfrontbc(d)b出队０　１　２　３frontrearrearrearrearrearfront☞队空：Q->front=Q->rear☞队满：Q->rear=maxsize-1☞队长：Q->rear-Q->front☞入队：将队尾指针加一

9、，即Q->rear=Q->rear+1，再将新元素按rear指示位置加入☞出队：将队头指针加一，即Q->front=Q->front+1，再将front指示的元素取出。此时：可以看出：☞尾指针rear已指到数组的最后一个元素，即rear=maxlen-1,若这时入队，则产生“溢出”；☞此时经过一定数量的出队后，头指针front可指向队列的中间，即数组的前面部分有闲置的空间——这种有可用空间存在的溢出称“假溢出”问题：如何利用数组前面的可用空间？5.3.1顺序队列的数据类型☞5.3.2循环队列5.3.3循环队列的运算实现5.3队列的顺序存储问题的提出：在顺序队列中