第3章栈和队链队列

《第3章栈和队链队列》由会员分享，可在线阅读，更多相关《第3章栈和队链队列（34页珍藏版）》请在装配图网上搜索。

1、数据结构回目录回目录上一页上一页下一页下一页结结 束束第第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 队

2、列的顺序存储结构及其基本实现队列的顺序存储结构及其基本实现温故知新环节温故知新环节数据结构回目录回目录上一页上一页下一页下一页结结 束束队尾队尾队头队头a1a2a3入队入队出队出队数据结构回目录回目录上一页上一页下一页下一页结结 束束0 1 2 3 4 入队入队出队出队a3a4fronta5rearreara6数据结构回目录回目录上一页上一页下一页下一页结结 束束【0】【1】【2】【3】【4】【5】CDEfrontrearBMaxSize=6char dataMaxSize;rear=5rear=?datarear=F;rear=(rear+1)%MaxSize3.2.2 队列的顺序存储结构及

3、其实现队列的顺序存储结构及其实现- 问题一问题一数据结构回目录回目录上一页上一页下一页下一页结结 束束 循环队列首尾相连循环队列首尾相连, 这可以利用除法取余的运算这可以利用除法取余的运算()来实现来实现: 队首指针进队首指针进1:front=(front+1)MaxSize 队尾指针进队尾指针进1:rear=(rear+1)MaxSize 数据结构回目录回目录上一页上一页下一页下一页结结 束束 队空和队满的条件都是队空和队满的条件都是 front=rear,如何区分？如何区分？ rear 0 1 2 3 4 front (a)空队空队 rear 0 1 2 3 4 front (e)出队出队

4、 多多 次次 , 队空队空 front=rear rear 0 1 2 3 4 front (e),队满队满 ABCDEfront=rear3.2.2 队列的顺序存储结构及其实现队列的顺序存储结构及其实现- 问题二问题二数据结构回目录回目录上一页上一页下一页下一页结结 束束 怎样区分队空与队满之间的差别呢怎样区分队空与队满之间的差别呢?在入队时少用在入队时少用一个数据元素空间一个数据元素空间,以队尾指针加以队尾指针加1等于队首指针判断队等于队首指针判断队满满,即队满条件为即队满条件为: (q-rear+1) % MaxSize=q-front队空条件仍为队空条件仍为: q-rear=q-fro

5、nt数据结构回目录回目录上一页上一页下一页下一页结结 束束1号题号题2号题号题温故知新环节温故知新环节3号题号题4号题号题数据结构回目录回目录上一页上一页下一页下一页结结 束束1号题号题栈和队列都是（）（南京理工）栈和队列都是（）（南京理工）a) 顺序存取的线性结构顺序存取的线性结构b) 链式存储的非线性结构链式存储的非线性结构c) 限制存取点的线性结构限制存取点的线性结构d) 限制存取点的非线性结构限制存取点的非线性结构温故知新环节温故知新环节数据结构回目录回目录上一页上一页下一页下一页结结 束束若用一个大小为若用一个大小为6的数组来实现循环的数组来实现循环队列，且当前队列，且当前rear和

6、和front的值分别为的值分别为0和和3，当从队列中删除一个元素，再，当从队列中删除一个元素，再加入加入2个元素后，个元素后，rear和和front的值分的值分别为多少？别为多少？(浙大浙大)a)1和和5b)2和和4c)4和和2d)5和和12号题号题温故知新环节温故知新环节数据结构回目录回目录上一页上一页下一页下一页结结 束束设栈设栈S和队列和队列Q的初始状态为空，的初始状态为空，元素元素e1,e2,e3,e4,e5,e6依次通过栈依次通过栈S，一个元素出栈后即进入队列一个元素出栈后即进入队列Q，若若6个元素出队的序列是个元素出队的序列是e2,e4,e3,e6,e5,e1,则栈的则栈的容量至少

7、应该是（）容量至少应该是（） (南京理工南京理工)a) 6b)4c)3d)23号题号题温故知新环节温故知新环节数据结构回目录回目录上一页上一页下一页下一页结结 束束循环队列存储在数组循环队列存储在数组A0m中，则中，则入队时的操作为（）入队时的操作为（）A.rear=rear+1B.rear=(rear+1)mod(m-1)C.rear=(rear+1)mod mD.rear=(rear+1)mod(m+1)4号题号题温故知新环节温故知新环节数据结构回目录回目录上一页上一页下一页下一页结结 束束3.2 队列队列3.2.3 队列的链式存储结构及其基本实现队列的链式存储结构及其基本实现新语新知环节

8、新语新知环节数据结构回目录回目录上一页上一页下一页下一页结结 束束qa1a2anrearfront数据结构回目录回目录上一页上一页下一页下一页结结 束束qa1a2anrearfrontrearq数据结构回目录回目录上一页上一页下一页下一页结结 束束链列的入队和出队操作示意图链列的入队和出队操作示意图 front rear q q(a)(a)链队初态链队初态 front rear (c)(c)出队出队 1 1 个元素个元素 b bc c3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现 front rear q q(b)(b)入队入队 3 3 个元素

9、个元素 a a b b c cq q数据结构回目录回目录上一页上一页下一页下一页结结 束束 (1) 存储队列元素的结点数据类型存储队列元素的结点数据类型单链表中数据结点类型单链表中数据结点类型QNode定义如下定义如下: typedef struct qnode ElemType data;/*数据元素数据元素*/struct qnode *next; QNode;3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现 front rear q q a a b b c c数据结构回目录回目录上一页上一页下一页下一页结结 束束(2) 指向队头和队尾指针的

10、链队头结点指向队头和队尾指针的链队头结点链队中头结点类型链队中头结点类型LiQueue定义如下定义如下:typedef struct QNode *front;/*指向单链表队头结点指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点指向单链表队尾结点*/ LiQueue; front rear q q(b)(b)入队入队 3 3 个元素个元素 a a b b c c3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现数据结构回目录回目录上一页上一页下一页下一页结结 束束 (1) 存储队列元素的单链表存储队列元素的单链表(2) 指

11、向队头和队尾指针的链队头结点指向队头和队尾指针的链队头结点单链表中数据结点类型单链表中数据结点类型QNode定义如下定义如下: typedef struct qnode ElemType data;/*数据元素数据元素*/struct qnode *next; QNode;链队中头结点类型链队中头结点类型LiQueue定义如下定义如下:typedef struct QNode *front;/*指向单链表队头结点指向单链表队头结点*/ QNode *rear; /*指向单链表队尾结点指向单链表队尾结点*/ LiQueue; 数据结构回目录回目录上一页上一页下一页下一页结结 束束 front r

12、ear q q (b)(b) 入队入队 3 3 个元素个元素 a a b b c c d ds frontrearq-front=sq- rear=sS-next=NULLd dsS-next=NULLq-rear-next=sq-rear=sq q3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现-入入队队数据结构回目录回目录上一页上一页下一页下一页结结 束束 front rear c cb b队中有多个结点的时候队中有多个结点的时候Free(p)pP= q-front front rear b bp队中有一个结点的时候队中有一个结点的时候P=

13、q-frontq-front=q-rear=NULLFree(p)3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现-出出队队q qq qq-front=p-next数据结构回目录回目录上一页上一页下一页下一页结结 束束 (1) 初始化队列初始化队列InitQueue(q) (2) 判断队列是否为空判断队列是否为空QueueEmpty(q) (3) 入队列入队列enQueue(q,e) (4) 出队列出队列deQueue(q,&e) (5) 销毁队列销毁队列ClearQueue(q)3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的

14、链式存储结构及其基本运算的实现数据结构回目录回目录上一页上一页下一页下一页结结 束束 (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 q (a)(a) 链队初态

15、链队初态 3.2.3 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 q 3.2.3 3.2.3 队列的链式存储结构及其

16、基本运算的实现队列的链式存储结构及其基本运算的实现-判空判空数据结构回目录回目录上一页上一页下一页下一页结结 束束 (3) 入队列入队列enQueue(q,e) 创建创建data域为域为e的数据结点的数据结点*s。若原队列为空。若原队列为空,则将链队结点的两个域均指向则将链队结点的两个域均指向*s结点结点,否则否则,将将*s链链到单链表的末尾到单链表的末尾,并让链队结点的并让链队结点的rear域指向它。域指向它。对应算法如下对应算法如下:3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现-入队入队数据结构回目录回目录上一页上一页下一页下一页结结 束

17、束 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; d ds frontrearq front rear q q a a b b c c

18、 d ds数据结构回目录回目录上一页上一页下一页下一页结结 束束 (4) 出队列出队列deQueue(q,e) 若原队列不为空若原队列不为空,则将第一个数据结点的则将第一个数据结点的data域域值赋给值赋给e,并删除之。若出队之前队列中只有一个结并删除之。若出队之前队列中只有一个结点点,则需将链队结点的两个域均置为则需将链队结点的两个域均置为NULL,表示队表示队列已为空。对应的算法如下列已为空。对应的算法如下:队空队空队中只有一个结点队中只有一个结点队中多个结点队中多个结点3.2.3 3.2.3 队列的链式存储结构及其基本运算的实现队列的链式存储结构及其基本运算的实现-出队出队数据结构回目录

19、回目录上一页上一页下一页下一页结结 束束 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 bp front rear c c b bpq

20、q数据结构回目录回目录上一页上一页下一页下一页结结 束束 (5) 销毁队列销毁队列ClearQueue(q) 释放队列占用的存储空间释放队列占用的存储空间,包括包括链队头结点链队头结点和和所有所有数据结点数据结点的存储空间。对应算法如下的存储空间。对应算法如下: void ClearQueue(LiQueue *q) QNode *p=q-front,*r;while(p!=NULL)/*释放数据结点占用空间释放数据结点占用空间*/ r=p-next; free(p); p=r;free(q);/*释放链队结点占用空间释放链队结点占用空间*/ 数据结构回目录回目录上一页上一页下一页下一页结结

21、束束（1）设有）设有N个人站成一排，从左到右的编号分别是个人站成一排，从左到右的编号分别是1到到N,现在现在从左到右报数从左到右报数“1，2，1，2，1，2”数到数到1的人出列的人出列,数到数到2的人立即站到队伍的右边的人立即站到队伍的右边.报数过程反复进行报数过程反复进行,直到直到N个个人都出列为止。要求给出他们的出列顺序。人都出列为止。要求给出他们的出列顺序。（2）数据组织）数据组织先进先出，这是个用队列解决出列的问题，采用环形顺序队列先进先出，这是个用队列解决出列的问题，采用环形顺序队列（3）设计运算算法）设计运算算法将将N个人编号入队，然后反复执行如下操作，直到队列为空：个人编号入队，

22、然后反复执行如下操作，直到队列为空： 出队一个元素，输出其编号出队一个元素，输出其编号 若队列不空，则再出队一个元素，并将刚出列的元素进队站若队列不空，则再出队一个元素，并将刚出列的元素进队站到队尾到队尾3.2.4 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);数据结构回目录回目录上一页上一页下一页下一页结结 束束本章小结本章小结本章基本学习要

23、点如下本章基本学习要点如下: (1) 理解栈和队列的特性以及它们之间的差异理解栈和队列的特性以及它们之间的差异,知知道在何时使用哪种数据结构。道在何时使用哪种数据结构。 (2) 重点掌握在顺序栈上和链栈上实现栈的基本重点掌握在顺序栈上和链栈上实现栈的基本运算算法运算算法,注意栈满和栈空的条件。注意栈满和栈空的条件。数据结构回目录回目录上一页上一页下一页下一页结结 束束 (3) 重点掌握在顺序队上和链队上实现队列的重点掌握在顺序队上和链队上实现队列的基本运算算法基本运算算法,注意循环队上队满和队空的条件。注意循环队上队满和队空的条件。 (4) 灵活运用栈和队列这两种数据结构解决一灵活运用栈和队列这两种数据结构解决一些综合应用问题。些综合应用问题。