第3章栈和队列链队列.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,数据结构,回目录,上一页,下一页,结 束,第3章 栈和队列,教学目标,3.1,栈,3.1.1 栈的定义,3.1.2 栈的顺序存储结构及其基本实现,3.1.3 栈的链式存储结构及其基本实现,3.2 队列,3.2.1 队列的定义,3.2.2 队列的顺序存储结构及其基本实现,3.2.3 队列的链式存储结构及其基本实现,本章小结,3.2 队列,3.2.1 队列的定义,3.2.2 队列的顺序存储结构及其基本实现,温故知新环节,特殊线性表队列,队列的逻辑结构,队列：,只允许在,一端,进行插入操作，而,另一端,进行删除操作的线性表。,队尾,队头,a,1,a,2,a,3,入队,出队,队列的操作特性：,先进先出,循环队列：,将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a,3,a,4,front,a,5,rear,rear,a,6,队列的顺序存储结构及实现（顺序队列）,不存在物理的循环结构，但可用软件方法实现。,求模,：（,41）mod 50,【0】,【1】,【2】,【3】,【4】,【5】,C,D,E,front,rear,B,MaxSize=6,char dataMaxSize;,rear=5,rear=?,datarear=F;,rear=(rear+1)%MaxSize,3.2.2 队列的顺序存储结构及其实现-,问题一,怎样区分队空与队满之间的差别呢?,在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为:,(q-rear+1)%MaxSize=q-front,队空条件仍为:,q-rear=q-front,1号题,2号题,温故知新环节,3号题,4号题,1号题,栈和队列都是（）（南京理工）,顺序存取的线性结构,链式存储的非线性结构,限制存取点的线性结构,限制存取点的非线性结构,温故知新环节,若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入2个元素后，rear和front的值分别为多少？,(浙大),a)1和5b)2和4,c)4和2d)5和1,2号题,温故知新环节,设栈S和队列Q的初始状态为空，,元素e1,e2,e3,e4,e5,e6依次通过栈S，,一个元素出栈后即进入队列Q，,若6个元素出队的序列是,e2,e4,e3,e6,e5,e1,则栈的,容量至少应该是（）,(南京理工),6b)4,c)3d)2,3号题,温故知新环节,循环队列存储在数组A0m中，则入队时的操作为（）,A.rear=rear+1,B.rear=(rear+1)mod(m-1),C.rear=(rear+1)mod m,D.rear=(rear+1)mod(m+1),4号题,温故知新环节,3.2 队列3.2.3 队列的链式存储结构及其基本实现,循环队列：必须预先确定一个固定的长,度，所以有存储元素个数的限制和空间,浪费的问题。还有队满的情况发生。,新语新知环节,链队列：,队列的链接存储结构,队头指针即为链表的头指针,q,a,1,a,2,a,n,如何改造单链表实现队列的链接存储？,rear,front,队列的链式存储结构及实现（链队列）,非空链队列,q,a,1,a,2,a,n,rear,空链队列,front,rear,队列的链式存储结构及实现（链队列）,q,链列的入队和出队操作示意图,front,rear,q,(a),链队初态,front,rear,(c),出队,1,个元素,b,c,3.23 队列的链式存储结构及其基本运算的实现,front,rear,q,(b),入队,3,个元素,a,b,c,q,(1)存储队列元素的结点数据类型,单链表中数据结点类型QNode定义如下:,typedef struct qnode,ElemType data;/*数据元素*/,struct qnode*next;,QNode;,3.2.3 队列的链式存储结构及其基本运算的实现,front,rear,q,a,b,c,(2)指向队头和队尾指针的链队头结点,链队中头结点类型LiQueue定义如下:,typedef struct,QNode*front;/*指向单链表队头结点*/,QNode*rear;/*指向单链表队尾结点*/,LiQueue;,front,rear,q,(b),入队,3,个元素,a,b,c,3.2.3 队列的链式存储结构及其基本运算的实现,(1)存储队列元素的单链表,(2)指向队头和队尾指针的链队头结点,单链表中数据结点类型QNode定义如下:,typedef struct qnode,ElemType data;/*数据元素*/,struct qnode*next;,QNode;,链队中头结点类型LiQueue定义如下:,typedef struct,QNode*front;/*指向单链表队头结点*/,QNode*rear;/*指向单链表队尾结点*/,LiQueue;,front,rear,q,(b),入队,3,个元素,a,b,c,d,s,front,rear,q-front=s,q-rear=s,S-next=NULL,d,s,S-next=NULL,q-rear-next=s,q-rear=s,q,3.2.3 队列的链式存储结构及其基本运算的实现,-入队,front,rear,c,b,队中有多个结点的时候,Free(p),p,P=q-front,front,rear,b,p,队中有一个结点的时候,P=q-front,q-front=q-rear=NULL,Free(p),3.2.3 队列的链式存储结构及其基本运算的实现,-出队,q,q,q-front=pnext,(1)初始化队列InitQueue(q),(2)判断队列是否为空QueueEmpty(q),(3)入队列enQueue(q,e),(4)出队列deQueue(q,&e),(5)销毁队列ClearQueue(q),3.2.3 队列的链式存储结构及其基本运算的实现,(1)初始化队列InitQueue(q),构造一个空队列,即只创建一个链队头结点,其front和rear域均置为NULL,不创建数据元素结点。对应算法如下:,LiQueue,*,InitQueue(void),LiQueue,*q;,q=(LiQueue*)malloc(sizeof(LiQueue);,q-front=q-rear=NULL;,return q;,front,rear,q,(a),链队初态,3.2.3 队列的链式存储结构及其基本运算的实现,-初始化,(2)判断队列是否为空QueueEmpty(q),若链队结点的rear域值为NULL,表示队列为空,返回1；否则返回0。对应算法如下:,int QueueEmpty(LiQueue*q),if(q-rear=NULL),return 1;,else,return 0;,front,rear,q,3.2.3 队列的链式存储结构及其基本运算的实现,-判空,(3)入队列enQueue(q,e),创建data域为e的数据结点*s。若原队列为空,则将链队结点的两个域均指向*s结点,否则,将*s链到单链表的末尾,并让链队结点的rear域指向它。对应算法如下:,3.2.3 队列的链式存储结构及其基本运算的实现,-入队,void enQueue(LiQueue*q,ElemType e),QNode*s;,s=(QNode*)malloc(sizeof(QNode);,s-data=e;,if(q-rear=NULL),/*若原链队为空,新结点是队首结点又是队尾结点*/,q-front=q-rear=s;,s-next=NULL;,else,q-rear-next=s;/*将*s结点链到队尾,rear指向它*/,q-rear=s;,s-next=NULLd,s,front,rear,q,front,rear,q,a,b,c,d,s,(4)出队列deQueue(q,e),若原队列不为空,则将第一个数据结点的data域值赋给e,并删除之。若出队之前队列中只有一个结点,则需将链队结点的两个域均置为NULL,表示队列已为空。对应的算法如下:,队空,队中只有一个结点,队中多个结点,3.2.3 队列的链式存储结构及其基本运算的实现,-出队,int deQueue(LiQueue*q,ElemType*e),QNode*p;,if(q-rear=NULL)return 0;/队空,p=q-front;/让P指向要删除的结点,if(q-front=q-rear)/原链队中只有一个结点时,q-front=q-rear=NULL;,else /原链队中有多个结点时,q-front=p-next;,*e=p-data;,free(p);,return 1;,q,front,rear,b,p,front,rear,c,b,p,q,(5)销毁队列ClearQueue(q),释放队列占用的存储空间,包括,链队头结点,和,所有数据结点,的存储空间。对应算法如下:,void ClearQueue(LiQueue*q),QNode*p=q-front,*r;,while(p!=NULL)/*释放数据结点占用空间*/,r=p-next;,free(p);,p=rfree(q);/*释放链队结点占用空间*/,（1）设有N个人站成一排，从左到右的编号分别是1到N,现在从左到右报数“1，2，1，2，1，2”数到1的人出列,数到2的人立即站到队伍的右边.报数过程反复进行,直到N个人都出列为止。要求给出他们的出列顺序。,（2）数据组织,先进先出，这是个用队列解决出列的问题，采用环形顺序队列,（3）设计运算算法,将N个人编号入队，然后反复执行如下操作，直到队列为空：,出队一个元素，输出其编号,若队列不空，则再出队一个元素，并将刚出列的元素进队站到队尾,3.2.4 队列的实例,printf(n依次进队元素1-%d:t,n);,for(i=1;i,e);,if(QueueEmpty(q)=1)printf(空队);,else,deQueue(q,e);,enQueue(q,e);,本章小结,本章基本学习要点如下:,(1)理解栈和队列的特性以及它们之间的差异,知道在何时使用哪种数据结构。,(2)重点掌握在顺序栈上和链栈上实现栈的基本运算算法,注意栈满和栈空的条件。,(3)重点掌握在顺序队上和链队上实现队列的基本运算算法,注意循环队上队满和队空的条件。,(4)灵活运用栈和队列这两种数据结构解决一些综合应用问题。,