chapt3栈和队列队列

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第3章 栈和队列,1 栈,2,队列,本章小结,1,堆栈和队列是数据结构的另外两种基本类型。从逻辑结构上看，堆栈和队列也是线性表，但它们是两种特殊的线性表。其特殊性在于，它们是运算受限的线性表，这里所说的运算是指对于数据的存取过程。,堆栈的存取只能在堆栈顶端进行,；,队列则通常限定从一端输入,，,从另一端端输出,。因此，堆栈和队列也被称为,限定性的数据结构,。,堆栈的运算规则是：,后进先出（Last In First Out）。,队列的运算规则是：,先进先出（First In First Out）。,2,1.1 队列的概述,1.2 队列的顺序存储结构及其基本运算实现,1.3 队列的链式存储结构及其基本运算实现,1.4 队列的应用,2 队列,3,1.1.1 队列的定义,队列（,queue,）是一种先进先出的线性表（,First In First Out,，缩写为,FIFO,）。这种限定性的数据结构，只允许,在一端进行输入，而在另一端输出,。,在队列中，允许输入的一端叫做,队尾,（也叫后端，,rear,），允许输出的一端叫做,队头,（也叫前端，,front,）。,向队列中插入新元素称为,入队,从队列中删除元素称为,出队,。,队列的逻辑示意图如下页所示：,1.1 队列的概述,4,假设队列为q=(a1,a2,a3an)，a1就是队头元素，an是队尾元素。队列中的元素是按照 a1,a2an的顺序入队的，出队时也必须依照这个顺序依次退出。也就是说，an-1出队后才轮到an出队。,队头 队尾,front rear,出队列 入队列,a1 a2 a3an,5,1,、图形的广度优先搜索,2,、优先队列：依据元素的某种特性和优先权存取元素。如模拟生活中的离散事件（排队问题）,3,、操作系统中的工作调度。,优先权相同者，先到先出,。,如,CPU,调度。同时有几项作业运行时，均须通过通道（可以是多端控制）输出，按照请求的先后次序排队，逐个输出。,如打印缓冲管理“,spooling”,，先将输出数据写在磁盘上（缓冲区），由打印机按照先存入者先打印的顺序输出数据。,1.1.2 队列的应用范围,6,1.2 队列的顺序存储结构及其基本运算实现,与顺序栈的处理方式相似，可以设置两个向量,front,、,rear,，做为指向队列前端（队首）和末端（队尾）的两个指针。初始值均为,1,时，表示队列为空。如下图：,队列的入队和出队操作示意图,7,顺序队列类型定义,假设队列的元素个数最大不超过整数,MaxSize,，所,有,的元素都具有同一数据类型,ElemType,，则顺序队列类型,SqQueue,定义如下,:,typedef,struct,ElemType,dataMaxSize,；,int,front,rear,；,/*,队首和队尾指针*,/,SqQueue,8,顺序队列的空间管理问题,从上图可以看出，这种,两端向量的线性空间配置并不能有效地利用空间。,如，图,(a),为队列的初始状态,有,front=rear,成立,该条件可以,作为队列空的条件,；但是,rear=MaxSize-1,却不能作为队满的条件。,如图,(d),中，队列为空，但仍满足,rear=MaxSize-1,。此时再入队则出现“上溢出”，但这种溢出并不是真正的溢出，队列中仍有可存放元素的空位置，所以这是一种假溢出。,在实际应用过程中，通常使用,环状队列,解决空间利用的问题。其实就是改变队列首尾指针的控制方式，使线性空间从逻辑上形成一个闭合的环，物理上仍是线性静态的存储空间分配。,9,环状队列的逻辑示意图如下：,front,rear,a1,a3,a2,a5,a4,环状队列逻辑示意图,Maxsize1,front,rear,2,1,0,a,n,a,n-1,b,1,环状队列的存储逻辑示意图,10,插入数据时，队尾指针rear会沿着逆时针方向前进，数据存入rear指向的位置。直到rear向前移到等于front时，表示队列已满，无法输入数据。,输出数据时，队首指针front也沿着逆时针方向前进。,从逻辑图式可以看出，这种处理方式的特殊点是,front指向一个空位置,，该位置不存储数据，所以,环状队列的可使用空间,不再是Maxsize，而,是“Maxsize1”,。,输出元素就是front的下一个元素,（如上图所示a1）。,同样的，当front前移至等于rear时，表示队列已空，无法输出数据。,上述逻辑环实际上还是如右上图所示的展开形式，是线性存储结构。当rear指针到达Maxsize1时，欲再存入元素，rear又再次回到原队列首端，相当于index=0的元素位置（如存入b1），以达到环状输入目的。front指针也要如此循环。,11,循环队列首尾指针的行走方式：,当首尾指针达到,MaxSize-1,后，再前进一个位置就自动到,0,，这可以利用除法取余的运算,(,),来实现,:,队首指针进,1:,front=(front+1),MaxSize,队,尾指针进,1:,rear=(rear+1),MaxSize,循环队列的头指针和尾指针初始值都置为,0,指针初始值：,front=rear=0,循环队列队满与队空的条件,队满条件：,(q-rear+1) %,MaxSize,=q-front,队空条件：,q-rear=q-front,12,循环队列入队和出队操作示意图,13,循环队列的基本运算,(1),初始化队列,InitQueue(&q,),构造一个空队列,q,，将,front,和,rear,指针均设置成初始状态，即,0,值。,对应算法如下,:,void,InitQueue(SqQueue,*&q),q=(,SqQueue,*),malloc,(,sizeof(SqQueue,);,q-front=q-rear=0;,14,(2) 销毁队列ClearQueue(&q),释放队列q占用的存储空间。对应算法如下:,void ClearQueue(SqQueue *&q),free(q);,(3) 判断队列是否为空QueueEmpty(q),若队列q满足q-front=q-rear条件,则返回1；否则返回0。对应算法如下:,int QueueEmpty(SqQueue *q),return(q-front=q-rear);,15,(4) 入队列enQueue(q,e),在队列不满的条件下，先将队尾指针rear循环增1，然后将元素添加到该位置。,对应算法如下:,int enQueue(SqQueue *&q,ElemType e),if (q-rear+1)%MaxSize=q-front),/*队满*/,return 0;,q-rear=(q-rear+1)%MaxSize;,q-dataq-rear=e;,return 1;,16,(5) 出队列deQueue(q,e),在队列q不为空的条件下，将队首指针front循环增1，并将该位置的元素值赋给e。,对应算法如下:,int deQueue(SqQueue *&q,ElemType &e),if (q-front=q-rear),/*队空*/,return 0;,q-front=(q-front+1)%MaxSize;,e=q-dataq-front;,return 1;,17,【例3.6】什么是队列的上溢现象和假溢出现象？解决它们有哪些方法？,答: 在队列的顺序存储结构中，设头指针为front，队尾指针为rear，队列容量(存储空间的大小)为MaxSize。当有元素入队列时，若队已满则会产生上溢。可利用指针控制队列的数据上溢，如当rear=MaxSize(初始时rear=0)则发生队列的上溢现象，则可作为条件控制元素不能再入队。,队列的假溢出现象：队列中还有剩余空间，但元素却不能入队列。造成这种现象的原因是由于队列首尾两端的操作控制方法所致。解决方法：平移元素：每当队列中加入一个元素时，队列中已有元素均向队头移动一个位置（需有空闲的空间可供移动）；每当删除一个队头元素时，也依次移动队中的元素，始终使front指针指向队列中的第一个位置；采用循环队列方式：把队列看成一个首尾相接的逻辑环，在循环队列上进行插入或删除运算时仍然遵循“先进先出”的原则。,18,1.3 队列的链式存储结构及其基本运算实现,当数据元素的变动较大，或者无法预计顺序存储所需空间时，队列的链式存储结构也比顺序存储结构更加有利。,使用链表描述的队列称为链队列。,一个链队列显然也需要两个分别指向队头和队尾的指针,front,、,rear,。其逻辑结构示意图如下：,front rear,NULL,链队列逻辑结构图,a,1,a,2,a,n,19,链列的入队和出队操作示意图,也可设置头结点指向链队列两端。如下图所示：,20,链队列的类型定义,链队中,数据结点,类型,QNode,定义如下,:,typedef,struct,qnode,ElemType,data;,/*,数据元素*,/,struct,qnode,*next;,QNode,;,链队中,头结点,类型,LiQueue,定义如下,:,typedef,struct,QNode,*front;,/*,指向单链表队头结点*,/,QNode,*rear;,/*,指向单链表队尾结点*,/,LiQueue,;,21,链队列的基本运算,(1),初始化队列,InitQueue(q,),构造一个空队列，即只创建一个链队头结点，其,front,和,rear,域均置为,NULL,，不创建数据元素结点。,对应算法如下,:,void,InitQueue(LiQueue,*&q),q=(,LiQueue,*),malloc(sizeof(LiQueue,);,q-front=q-rear=NULL;,22,(2) 销毁队列ClearQueue(q),释放队列占用的存储空间，包括链队头结点和所有数据结点的存储空间。对应算法如下:,void ClearQueue(LiQueue *&q),QNode *p=q-front,*r;,if (p!=NULL),/*释放数据结点占用空间*/, r=p-next;,while (r!=NULL), free(p);,p=r;r=p-next;,/*p和r指针同步后移*/,free(q);,/*释放链队结点占用空间*/,23,(3) 判断队列是否为空QueueEmpty(q),若链队结点的rear域值为NULL，表示队列为空，返回1；否则返回0。,对应算法如下:,int QueueEmpty(LiQueue *q),if (q-rear=NULL),return 1;,else,return 0;,24,(4) 入队列enQueue(q,e),创建data域为e的数据结点*s。若原队列为空，则将链队结点的两个域均指向*s结点；否则，将*s链到单链表的末尾，并让链队结点的rear域指向它。对应算法如下:,void enQueue(LiQueue *&q,ElemType e), QNode *s;,s=(QNode *)malloc(sizeof(QNode);,s-data=e;,s-next=NULL;,if (q-rear=NULL),q-front=q-rear=s;,/*若原链队为空,新结点是队首结点又是队尾结点*/,else, q-rear-next=s;,q-rear=s;,/*将*s结点链到队尾,rear指向它*/,25,(5) 出队列deQueue(q,e),若原队列不为空,则将第一个数据结点的data域值赋给e，并删除之。若出队之前队列中只有一个结点，则需将链队结点的两个域均置为NULL，表示队列已为空。对应的算法如下:,int deQueue(LiQueue *&q,ElemType &e),QNode *t;,if (q-rear=NULL) return 0;,/*队列为空*/,t=q-front;,/*,t,指向第一个数据结点*/,if (q-front=q-rear),/*原链队中只有一个结点时*/,q-front=q-rear=NULL;,else,/*原链队中有多个结点时*/,q-front=q-front-next;,e=t-data;,free(t);,return 1;,26,1.4 队列的应用,队列在实际应用中，可以改变输入输出方向的限制。,例如“,双端队列,(,Deque,)”,，这是一种可以在任何一端进行插入和删除的线性表。逻辑示意图如下：,a1 a2 an,端1 front 端2 rear,插入,删除,插入,删除,仍可将左端1视为前端（front），右端2视为后端（rear）。这种数据结构在计算机中的应用常见于服务器中CPU不同性质的工作调度。,双端队列的设计方案有很多种，最常见到的是：输入端受限的,输入限制性双端队列,（只允许从一个端点输入，但是可以从两端输出）；输出端受限的,输出限制性双端队列,（只允许从一个端点输出，但是可以从两端输入）。,27,队列应用举例,双端队列队首输入、队尾输出的算法,教材,【,例,3.7】,、,【,例,3.8】,求解报数问题,教材,p83,求解迷宫问题,算法如下：（教材,p84,）,使用一个队列,Qu,记录走过的方块，该队列的结构如下,:,struct,int,i,j,;,/*,方块的位置*,/,int,pre;,/*,本路径中上一方块在,Qu,中的下标*,/,QuMaxSize,;,int,front=,-,1,rear=,-,1;,/*,队首指针和队尾指针*,/,这里的队列,Qu,不是循环队列,(,因为要利用出队的元素找路径,),因此在出队时,不会将出队元素真正从队列中删除,因为要利用它输出路径。,28,(1) 首先将(1,1)入队;,(2) 在队列Qu不为空时循环：出队一次(由于不是循环队列，该出队元素仍在队列中)，称该出队的方块为当前方块，front为该方块在Qu中的下标。,如果当前方块是出口，则输出路径并结束。,否则按顺时针方向找出当前方块的四个方位中可走的相邻方块（对应的mg数组值为0），将这些可走的相邻方块均插入到队列Qu中，其pre设置为本搜索路径中上一方块在Qu中的下标值，也就是当前方块的front值，并将相邻方块对应的mg数组值置为-1，以避免重复搜索。,(3) 若队列为空仍未找到出口，即不存在路径。,本算法的思想是从(1,1)开始，利用队列的特点一层一层向外扩展可走的点,直到找到出口为止。这个方法就是将在第8章介绍的图的广度优先搜索方法。,搜索从(1,1)到(M-2,N-2)路径：,29,算法如下：,void mgpath(),/*搜索路径为:(1,1)-(M-2,N-2)*/, int i,j,find=0,di;,rear+;,Qurear.i=1;Qurear.j=1;Qurear.pre=,-,1;,/*(1,1)入队*/,mg11=,-,1;,/*将其赋值-1,以避免回过来重复搜索*/,while (front=rear & !find), front+;,/*出队,由于不是循环队列,该元素仍在队中*/,i=Qufront.i;j=Qufront.j;,/*新位置为队首*/,if (i=M-2 & j=N-2),/*找到了出口,输出路径*/, find=1;,print,(front);,/*调用print函数输出路径*/,30,for (di=0;di3;di+),/*把每个可走的方块插入队列中*/, switch(di), case 0:i=Qufront.i-1;j=Qufront.j;break;,case 1:i=Qufront.i;j=Qufront.j+1;break;,case 2:i=Qufront.i+1;j=Qufront.j;break;,case 3:i=Qufront.i,j=Qufront.j-1;break;,if (mgij=0), rear+;,/*将该相邻方块插入到队列中*/,Qurear.i=i;Qurear.j=j;,/*新位置为队尾*/,Qurear.pre=front;,/*指向路径中上一方块下标*/,mgij=-1;,/*将其赋值-1,以避免重复搜索*/,if (!find) printf(不存在路径!n);,31,本章小结,本章基本学习要点如下:,(1) 掌握栈和队列的特性、结构定义以及它们之间的差异；了解这两种数据结构的应用。,(2) 掌握在顺序栈上和链栈上实现栈的基本运算算法，注意栈满和栈空的条件。,利用栈实现表达式求值和转换（中序 后序）。,掌握递归的特性、递归调用与普通函数调用的规则与过程；掌握函数栈尤其是递归工作栈的工作原理及工作记录内容。,(3) 掌握在顺序队上（循环队列）和链队上实现队列的基本运算算法，注意循环队上队满和队空的条件。,(4) 灵活运用栈和队列这两种数据结构解决一些实际应用问题。,32,