第三章 队列精选PPT.ppt

第三章 队列第1页，本讲稿共50页 3.1 3.1 什么是队列什么是队列 3.2 3.2 链队列链队列 3.3 3.3 顺序队列顺序队列 3.4 3.4 队列的应用举例队列的应用举例栈队队 列列第2页，本讲稿共50页一、什么是队列一、什么是队列队列队列队列队列：限定仅在限定仅在限定仅在限定仅在一端一端一端一端进行插入进行插入进行插入进行插入，而在另，而在另，而在另，而在另一端一端一端一端进行进行进行进行删除操作删除操作删除操作删除操作的线性表的线性表的线性表的线性表。a a1 1 a a2 2 a a3 3 a an n出队列出队列出队列出队列入队列入队列入队列入队列队尾队尾队尾队尾 rearrear 队头队头队头队头 frontfrontn n 允许删除的一端称为允许删除的一端称为允许删除的一端称为允许删除的一端称为队头队头队头队头(front)(front)(front)(front)n n 允许插入的一端称为允许插入的一端称为允许插入的一端称为允许插入的一端称为队尾队尾队尾队尾(rear)(rear)(rear)(rear)n n 队列中没有元素时称为队列中没有元素时称为队列中没有元素时称为队列中没有元素时称为空队列空队列空队列空队列第3页，本讲稿共50页例如：排队购物。操作系统中的作业排队。先进入队列的成员总是先离开队列。因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an，也就是说队列的修改是依先进先出的原则进行的。第4页，本讲稿共50页二、队列的特点二、队列的特点n n根据队列的定义可知，最先放入队列的元素最先出队根据队列的定义可知，最先放入队列的元素最先出队根据队列的定义可知，最先放入队列的元素最先出队根据队列的定义可知，最先放入队列的元素最先出队列。列。列。列。n 特点特点特点特点 ：先先先先进先出进先出进先出进先出n 也就是说，队列是一种后进先出的线性表，简称为也就是说，队列是一种后进先出的线性表，简称为也就是说，队列是一种后进先出的线性表，简称为也就是说，队列是一种后进先出的线性表，简称为FIFO FIFO(FirstFirst In First OutIn First Out)表。表。表。表。第5页，本讲稿共50页例例例例1 1 1 1：有一个栈，进：有一个栈，进：有一个栈，进：有一个栈，进 栈栈栈栈 序列为序列为序列为序列为A A A A、B B B B、C C C C，试给出所有可能，试给出所有可能，试给出所有可能，试给出所有可能的出的出的出的出 栈栈栈栈 序列。序列。序列。序列。不可能产生输出序列不可能产生输出序列 CABCABA A进进进进 B B进进进进 C C进进进进 C C出出出出 B B出出出出 A A出出出出 CBA CBA A A进进进进 A A出出出出 B B进进进进 B B出出出出 C C进进进进 C C出出出出 ABCABCA A进进进进 A A出出出出 B B进进进进 C C进进进进 C C出出出出 B B出出出出 ACBACBA A进进进进 B B进进进进 B B出出出出 A A出出出出 C C进进进进 C C出出出出 BACBACA A进进进进 B B进进进进 B B出出出出 C C进进进进 C C出出出出 A A出出出出 BCABCA 队列队列队列队列队列队列队列队列 只可能产生的输出序列只可能产生的输出序列 ABCABC第6页，本讲稿共50页三、队列的抽象数据类型三、队列的抽象数据类型ADT ADT QueueQueue 数据对象数据对象数据对象数据对象：D D a ai i|a|ai i ElemSet,i=1,2,.,n,n0 ElemSet,i=1,2,.,n,n0 数据关系数据关系数据关系数据关系：R R a|a|ai-1i-1,a,ai iD,i=2,.,n D,i=2,.,n 约定约定约定约定a an n 端为队尾，端为队尾，端为队尾，端为队尾，a a1 1 端为队头端为队头端为队头端为队头。基本操作：基本操作：基本操作：基本操作：InitQueue(&Q)InitQueue(&Q)/操作结果：构造一个空队列操作结果：构造一个空队列操作结果：构造一个空队列操作结果：构造一个空队列QQ。DestroyQueue(&Q)DestroyQueue(&Q)/操作结果：队列操作结果：队列操作结果：队列操作结果：队列QQ被销毁。被销毁。被销毁。被销毁。ClearQueue(&Q)ClearQueue(&Q)/操作结果：将操作结果：将操作结果：将操作结果：将QQ清为队列清为队列清为队列清为队列第7页，本讲稿共50页 QueueEmpty(Q)QueueEmpty(Q)/操作结果：若队列操作结果：若队列操作结果：若队列操作结果：若队列QQ为空队列，则返回为空队列，则返回为空队列，则返回为空队列，则返回TRUETRUE，否则，否则，否则，否则FALSEFALSE。QueueLength(Q)QueueLength(Q)/操作结果：返回操作结果：返回操作结果：返回操作结果：返回QQ的元素个数，即队列的长度。的元素个数，即队列的长度。的元素个数，即队列的长度。的元素个数，即队列的长度。GetHead(Q,&e)GetHead(Q,&e)/操作结果：用操作结果：用操作结果：用操作结果：用e e返回返回返回返回QQ的队头元素的队头元素的队头元素的队头元素。EnQueue(&Q,e)EnQueue(&Q,e)/操作结果：插入元素操作结果：插入元素操作结果：插入元素操作结果：插入元素e e为新的队尾元素为新的队尾元素为新的队尾元素为新的队尾元素。DeQueue(&Q,&e)DeQueue(&Q,&e)/操作结果：删除操作结果：删除操作结果：删除操作结果：删除QQ的队头元素，并用的队头元素，并用的队头元素，并用的队头元素，并用e e返回其值。返回其值。返回其值。返回其值。/ADT Stack/ADT Stack第8页，本讲稿共50页 3.1 3.1 什么是队列什么是队列 3.2 3.2 链队列链队列 3.3 3.3 顺序队列顺序队列 3.4 3.4 队列的应用举例队列的应用举例栈队队 列列第9页，本讲稿共50页 显然，仅有单链表的头指针不便于在表尾做插入操作，为显然，仅有单链表的头指针不便于在表尾做插入操作，为显然，仅有单链表的头指针不便于在表尾做插入操作，为显然，仅有单链表的头指针不便于在表尾做插入操作，为此再增加一个尾指针，指向链表的最后一个结点。于是此再增加一个尾指针，指向链表的最后一个结点。于是此再增加一个尾指针，指向链表的最后一个结点。于是此再增加一个尾指针，指向链表的最后一个结点。于是，一个链队列由头指针和尾指针唯一确定一个链队列由头指针和尾指针唯一确定一个链队列由头指针和尾指针唯一确定一个链队列由头指针和尾指针唯一确定。链队列链队列：用链表来存储队列：用链表来存储队列 队头指针队头指针队头指针队头指针 为为为为 Q.frontQ.front 队尾指针队尾指针队尾指针队尾指针 为为为为 Q.rearQ.reara2ana1frontrear头头头头结结结结点点点点队头队头队头队头结点结点结点结点队尾队尾队尾队尾结点结点结点结点QQ第10页，本讲稿共50页typedef structtypedef struct QNodeQNode QElemType QElemType data;data;structstruct QNode QNode*next*next;QNodeQNode,*QueuePtrQueuePtr;队尾队尾队尾队尾队头队头队头队头frontfront rear rear QQtypedef structtypedef struct QueuePtr QueuePtr frontfront;/队头指针队头指针队头指针队头指针 QueuePtr QueuePtr rearrear;/队尾指针队尾指针队尾指针队尾指针 LinkQueueLinkQueue;LinkQueue Q;LinkQueue Q;第11页，本讲稿共50页Status Status InitQueue InitQueue(LinkQueue&Q)(LinkQueue&Q)Status Status DestroyQueueDestroyQueue(LinkQueue&Q)(LinkQueue&Q)Status Status EnQueueEnQueue(LinkQueue&Q,QElemType e)(LinkQueue&Q,QElemType e)Status Status DeQueueDeQueue(LinkQueue&Q,QElemType&e)(LinkQueue&Q,QElemType&e)二、链队列的基本操作二、链队列的基本操作第12页，本讲稿共50页void void InitQueueInitQueue(LinkQueue&Q)(LinkQueue&Q)frontfrontrearrear一个空队列：一个空队列：一个空队列：一个空队列：Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);Q.front=Q.rear=(QueuePtr)malloc(sizeof(QNode);if(!Q.front)exit(OVERFLOW);if(!Q.front)exit(OVERFLOW);Q.front-next=NULL;Q.front-next=NULL;QQ第13页，本讲稿共50页Status Status DestroyQueueDestroyQueue(LinkQueue&Q)(LinkQueue&Q)队尾队尾队尾队尾队头队头队头队头frontfront rear rear while(Q.front)while(Q.front)Q.rear=Q.front-next;Q.rear=Q.front-next;free(Q.front);free(Q.front);Q.front=Q.rear;Q.front=Q.rear;/从前到后，逐个摘下结点并释放结点所用的内存空间从前到后，逐个摘下结点并释放结点所用的内存空间从前到后，逐个摘下结点并释放结点所用的内存空间从前到后，逐个摘下结点并释放结点所用的内存空间 return OK;return OK;第14页，本讲稿共50页Status Status DestroyQueueDestroyQueue(LinkQueue&Q)(LinkQueue&Q)队尾队尾队尾队尾队头队头队头队头front front rear rear while(Q.front)while(Q.front)Q.rear=Q.front-next;Q.rear=Q.front-next;free(Q.front);free(Q.front);Q.front=Q.rear;Q.front=Q.rear;/从前到后，逐个摘下结点并释放结点所用的内存空间从前到后，逐个摘下结点并释放结点所用的内存空间从前到后，逐个摘下结点并释放结点所用的内存空间从前到后，逐个摘下结点并释放结点所用的内存空间 return OK;return OK;第15页，本讲稿共50页Status Status EnQueueEnQueue(LinkQueue&Q,QElemType e)(LinkQueue&Q,QElemType e)p=(QueuePtr)malloc(sizeof(QNode);p=(QueuePtr)malloc(sizeof(QNode);if(!p)exit(if(!p)exit(OVERFLOWOVERFLOW););p-data=e;p-next=NULL;p-data=e;p-next=NULL;Q.rear-next=p;Q.rear-next=p;Q.rear=p;Q.rear=p;return OK;return OK;队尾队尾队尾队尾队头队头队头队头frontfront rear rear QQe=2e=2p p2 2第16页，本讲稿共50页Status Status DeQueueDeQueue(LinkQueue&Q,QElemType&e)(LinkQueue&Q,QElemType&e)return ERROR;return ERROR;p=Q.front-next;e=p-data;p=Q.front-next;e=p-data;if(Q.rear=p)Q.rear=Q.front;if(Q.rear=p)Q.rear=Q.front;free(p);free(p);return OK;return OK;队尾队尾队尾队尾队头队头队头队头frontfront rear rear QQp=Q.front;p=Q.front;Q.front=p-next;Q.front=p-next;e=Q.front-dada;e=Q.front-dada;p pif(Q.front=Q.rear)if(Q.front=Q.rear)Q.front-next=p-next;Q.front-next=p-next;第17页，本讲稿共50页Status Status DeQueueDeQueue(LinkQueue&Q,QElemType&e)(LinkQueue&Q,QElemType&e)if(Q.front=Q.rear)return ERROR;if(Q.front=Q.rear)return ERROR;p=Q.front-next;e=p-data;p=Q.front-next;e=p-data;Q.front-next=p-next;Q.front-next=p-next;if(Q.rear=p)Q.rear=Q.front;if(Q.rear=p)Q.rear=Q.front;free(p);free(p);return OK;return OK;队尾队尾队尾队尾frontfront rear rear QQp=Q.front;p=Q.front;Q.front=p-next;Q.front=p-next;e=Q.front-dada;e=Q.front-dada;p p删除队列头元素算法中的特殊情况：当队列中最后一个元素被删除后，队尾指针也丢失了，因此需对队尾指针重新赋值。第18页，本讲稿共50页 3.1 3.1 什么是队列什么是队列 3.2 3.2 链队列链队列 3.3 3.3 顺序队列顺序队列 3.4 3.4 队列的应用举例队列的应用举例栈队队 列列第19页，本讲稿共50页顺序队列：顺序队列：用数组存储的队列用数组存储的队列n n由于队列的操作是由于队列的操作是由于队列的操作是由于队列的操作是尾入头出尾入头出尾入头出尾入头出，所以为了操，所以为了操，所以为了操，所以为了操作方便，设置作方便，设置作方便，设置作方便，设置frontfront 和和和和 rearrear2 25 59 93 36 68 87 70123456789frontfrontrearrear#define#define MAXQSIZE MAXQSIZE 100 100typedef struct typedef struct QElemType*base;QElemType*base;SqQueue;SqQueue;int front;int front;/头指针头指针头指针头指针 int rear;int rear;/尾指针尾指针尾指针尾指针第20页，本讲稿共50页SqQueue QSqQueue Q；2 25 59 93 36 68 87 701234567890 07 7basebasefrontfrontrearrearQQ空队列什么空队列什么空队列什么空队列什么样样样样？第21页，本讲稿共50页01234567890 00 0basebasefrontfrontrearrear初始建立队列时初始建立队列时初始建立队列时初始建立队列时:Q.frontQ.frontQ.frontQ.front=Q.rearQ.rearQ.rearQ.rear=0 0 0 0 QQInitQueueInitQueue(Q)(Q)EnQueue(Q,2)EnQueue(Q,2)？第22页，本讲稿共50页01234567890 01 1basebasefrontfrontrearrear元素元素元素元素 e e e e 入队入队入队入队 ：Q.baseQ.rearQ.baseQ.rearQ.baseQ.rearQ.baseQ.rear+=e;e;e;e;2 2QQ5 52 2EnQueueEnQueue(Q,e)(Q,e)EnQueue(Q,5)EnQueue(Q,5)？第23页，本讲稿共50页01234567890 03 3basebasefrontfrontrearrear元素元素元素元素 e e e e 出队出队出队出队 ：e e e e=Q.baseQ.front+;Q.baseQ.front+;Q.baseQ.front+;Q.baseQ.front+;2 2QQ5 53 3DeQueueDeQueue(Q,e)(Q,e)e=2e=21 1DeQueue(Q,e)DeQueue(Q,e)？第24页，本讲稿共50页01234567890 01 1basebasefrontfrontrearrear2 2QQQueueLengthQueueLength(Q)(Q)5 53 31 16 62 2 3 34 45 51 12 2Q.rear-Q.frontQ.rear-Q.front队中元素的个数队中元素的个数队中元素的个数队中元素的个数?QueueEmptyQueueEmpty(Q)(Q)判断队空判断队空判断队空判断队空?Q.rear=Q.frontQ.rear=Q.front3 34 45 5队最多放几个元素队最多放几个元素队最多放几个元素队最多放几个元素?MAXQSIZE-1 MAXQSIZE-1 注意：注意：注意：注意：Q.rearQ.rear所指的位置不存放队列元素所指的位置不存放队列元素所指的位置不存放队列元素所指的位置不存放队列元素第25页，本讲稿共50页01234567890 01 1basebasefrontfrontrearrearQQ2 23 34 49 91 1 9 9当当当当Q.rear=MAXQSIZE-1Q.rear=MAXQSIZE-1,但但但但Q.front0Q.front0时，时，时，时，（队列中元素个数未（队列中元素个数未（队列中元素个数未（队列中元素个数未“满满满满”）若再有元素入队，）若再有元素入队，）若再有元素入队，）若再有元素入队，会使下标出界，此时的溢出称为假上溢会使下标出界，此时的溢出称为假上溢会使下标出界，此时的溢出称为假上溢会使下标出界，此时的溢出称为假上溢假上溢：假上溢：假上溢：假上溢：第26页，本讲稿共50页顺序队列操作第27页，本讲稿共50页循环队列操作第28页，本讲稿共50页循环队列循环队列0 0 0 01 1 1 12 2 2 23 3 3 34 4 4 45 5 5 56 6 6 67 7 7 78 8 8 89 9 9 91010101011111111121212121313131314141414示意图：设示意图：设示意图：设示意图：设MAXQSIZE MAXQSIZE MAXQSIZE MAXQSIZE 为为为为 15151515，（下标从，（下标从，（下标从，（下标从0 0 0 014141414）Q.front=(Q.front+1)%MAXQSIZEQ.front=(Q.front+1)%MAXQSIZEQ.front+Q.front+Q.rear+Q.rear+Q.rear=(Q.rear+1)%MAXQSIZEQ.rear=(Q.rear+1)%MAXQSIZE队中元素个数队中元素个数队中元素个数队中元素个数n=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZEn=(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE第29页，本讲稿共50页frontfrontghkeabdrear0123456frontghkeabdrearrearrearrearrearfrontfrontfrontfrontfrontfront入队入队出队出队队满队满队满队满队空队空队空队空讨论：队空与队满的描述讨论：队空与队满的描述讨论：队空与队满的描述讨论：队空与队满的描述只凭只凭只凭只凭Q.front=Q.rearQ.front=Q.rear 不能判断队列是不能判断队列是不能判断队列是不能判断队列是“空空空空”还是还是还是还是“满满满满”处理方法：少用一个空间，约定队头在队尾的下一个就算处理方法：少用一个空间，约定队头在队尾的下一个就算处理方法：少用一个空间，约定队头在队尾的下一个就算处理方法：少用一个空间，约定队头在队尾的下一个就算“满满满满”rearrear0123456frontfront第30页，本讲稿共50页n n循环队列空：循环队列空：循环队列空：循环队列空：Q.front=Q.rearQ.front=Q.rearn n循环队列满：循环队列满：循环队列满：循环队列满：(Q.rear+1)%MAXQSIZE=Q.front(Q.rear+1)%MAXQSIZE=Q.front第31页，本讲稿共50页Status Status InitQueue InitQueue(SqQueue&Q)(SqQueue&Q)Q.base=(QElemType*)malloc Q.base=(QElemType*)malloc (MAXQSIZE*sizeof(QElemType)MAXQSIZE*sizeof(QElemType););if(!Q.base)exit(OVERFLOW);if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;Q.front=Q.rear=0;return OK;return OK;0 1 2 3 4 5 60 1 2 3 4 5 60 00 0basebasefrontfrontrearrearQQ第32页，本讲稿共50页int int QueueLengthQueueLength(SqQueue Q)(SqQueue Q)return ;return ;(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE(Q.rear-Q.front+MAXQSIZE)%MAXQSIZE第33页，本讲稿共50页Status Status EnQueue EnQueue(SqQueue&Q,QElemType e)(SqQueue&Q,QElemType e)if if return ERROR;return ERROR;Q.baseQ.rear=e;Q.baseQ.rear=e;Q.rear=;Q.rear=;return OK;return OK;(Q.rear+1)%MAXQSIZE(Q.rear+1)%MAXQSIZE(Q.rear+1)%MAXQSIZE=Q.front)(Q.rear+1)%MAXQSIZE=Q.front)第34页，本讲稿共50页Status Status DeQueueDeQueue(SqQueue&Q,QElemType&e)(SqQueue&Q,QElemType&e)if()return ERROR;if()return ERROR;e=Q.baseQ.front;e=Q.baseQ.front;return OK;return OK;Q.front=(Q.front+1)%MAXQSIZEQ.front=(Q.front+1)%MAXQSIZEQ.rear=Q.frontQ.rear=Q.front第35页，本讲稿共50页 3.1 3.1 什么是队列什么是队列 3.2 3.2 链队列链队列 3.3 3.3 顺序队列顺序队列 3.4 3.4 队列的应用举例队列的应用举例栈队队 列列第36页，本讲稿共50页例一 杨辉三角这个问题的程序可以有很多种写法，一种最直接的想法是利用两个数组，其中一个存放已经计算得到的第 k 行的值，然后输出第 k 行的值同时计算第 k+1行的值。如此写得的程序显然结构清晰，但需要两个辅助数组的空间，并且这两个数组在计算过程中需相互交换。如若引入循环队列，则可以省略一个数组的辅助空间，而且可以利用队列的操作将一琐碎操作屏蔽起来，使程序结构变得清晰，容易被人理解。第37页，本讲稿共50页void YangHuiTriangle(int n)SeqQueue Q;InitQueue(Q);EnterQueue(Q,1);/*第一行元素入队*/for(i=2;i=n;i+)/*产生第n行元素并入队，同时打印第n-1行的元素*/EnterQueue(Q,1);/*第n行的第一个元素入队*/for(j=1;jtws.top1)return OVERFLOW;/栈满 if(i=0)*tws.top0+=x;else if(i=1)*tws.top1-=x;else return ERROR;return OK;/push 第49页，本讲稿共50页出栈 Status pop(BDStacktype&tws,int i,Elemtype&x)/x出栈出栈,i=0表示低端栈表示低端栈,i=1表示高端栈表示高端栈if(i=0)if(tws.top0=tws.base0)return OVERFLOW;x=*-tws.top0;else if(i=1)if(tws.top1=tws.base1)return OVERFLOW;x=*+tws.top1;else return ERROR;return OK;/pop 第50页，本讲稿共50页