第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 队列的顺序存储结构及其基本实现,温故知新环节,特殊线性表队列,队列的逻辑结构 队列：只允许在一端进行插入操作，而另一端进行删除操作的线性表。,a1,a2,a3,入队,出队,队列的操作特性：,先进先出,循环队列：将存储队列的数组头尾相接。,如何解决假溢出？,0 1 2 3 4,入队,出队,a3,a4,a5,a6,队列的顺序存储结构及实现（顺序队列）,不存在物理的循环结构，但可用软件方法实现。 求模：（41）mod 50,MaxSize=6 char dataMaxSize; rear=5 rear=? datarear=F;,rear=(rear+1)%MaxSize,3.2.2 队列的顺序存储结构及其实现- 问题一,循环队列首尾相连, 这可以利用除法取余的运算()来实现: 队首指针进1:front=(front+1)MaxSize 队尾指针进1:rear=(rear+1)MaxSize,队空和队满的条件都是 front=rear,如何区分？,front=rear,front=rear,3.2.2 队列的顺序存储结构及其实现- 问题二,怎样区分队空与队满之间的差别呢?在入队时少用一个数据元素空间,以队尾指针加1等于队首指针判断队满,即队满条件为: (q-rear+1) % MaxSize=q-front 队空条件仍为: q-rear=q-front,温故知新环节,栈和队列都是（）（南京理工） 顺序存取的线性结构 链式存储的非线性结构 限制存取点的线性结构 限制存取点的非线性结构,温故知新环节,若用一个大小为6的数组来实现循环队列，且当前rear和front的值分别为0和3，当从队列中删除一个元素，再加入2个元素后，rear和front的值分别为多少？ (浙大) a)1和5 b)2和4 c)4和2 d)5和1,温故知新环节,设栈S和队列Q的初始状态为空， 元素e1,e2,e3,e4,e5,e6依次通过栈S， 一个元素出栈后即进入队列Q， 若6个元素出队的序列是 e2,e4,e3,e6,e5,e1,则栈的 容量至少应该是（） (南京理工) 6 b)4 c)3 d)2,温故知新环节,循环队列存储在数组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),温故知新环节,3.2 队列 3.2.3 队列的链式存储结构及其基本实现 循环队列：必须预先确定一个固定的长 度，所以有存储元素个数的限制和空间 浪费的问题。还有队满的情况发生。,新语新知环节,链队列：队列的链接存储结构,队头指针即为链表的头指针,如何改造单链表实现队列的链接存储？,队列的链式存储结构及实现（链队列）,非空链队列,q,rear,空链队列,front,rear,队列的链式存储结构及实现（链队列）,q,链列的入队和出队操作示意图,front,rear,q,(a),链队初态,front,rear,(c),出队,1,个元素,b,c,3.2.3 队列的链式存储结构及其基本运算的实现,q,(1) 存储队列元素的结点数据类型,单链表中数据结点类型QNode定义如下: typedef struct qnode ElemType data; /*数据元素*/ struct qnode *next; QNode;,3.2.3 队列的链式存储结构及其基本运算的实现,(2) 指向队头和队尾指针的链队头结点,链队中头结点类型LiQueue定义如下: typedef struct QNode *front; /*指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点*/ LiQueue;,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,front,rear,q-front=s,q- rear=s,S-next=NULL,S-next=NULL,q-rear-next=s,q-rear=s,q,3.2.3 队列的链式存储结构及其基本运算的实现-入队,front,rear,c,队中有多个结点的时候,Free(p),P= q-front,front,rear,b,队中有一个结点的时候,P= q-front,q-front=q-rear=NULL,Free(p),3.2.3 队列的链式存储结构及其基本运算的实现-出队,q,q,q-front=p-next,(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; ,3.2.3 队列的链式存储结构及其基本运算的实现-初始化,(2) 判断队列是否为空QueueEmpty(q) 若链队结点的rear域值为NULL,表示队列为空,返回1；否则返回0。对应算法如下: int QueueEmpty(LiQueue *q) if (q-rear=NULL) return 1; else return 0; ,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=NULL; ,front,rear,q,a,b,c,(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; ,(5) 销毁队列ClearQueue(q) 释放队列占用的存储空间,包括链队头结点和所有数据结点的存储空间。对应算法如下: void ClearQueue(LiQueue *q) QNode *p=q-front,*r; while(p!=NULL) /*释放数据结点占用空间*/ r=p-next; free(p); p=r; free(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) 灵活运用栈和队列这两种数据结构解决一些综合应用问题。,
