《数据结构 教学课件 ppt 作者 宗大华 陈吉人 03堆栈与队列》由会员分享，可在线阅读，更多相关《数据结构 教学课件 ppt 作者 宗大华 陈吉人 03堆栈与队列（96页珍藏版）》请在金锄头文库上搜索。
1、第3章 堆栈与队列,堆栈和队列是两种特殊的线性表，是对线性表施行的操作加以一定限制后得到的数据结构。堆栈和队列在程序设计中是极为有用的一种重要工具。,本章主要介绍以下几个方面的内容： 堆栈的基本知识和存储实现； 队列的基本知识和存储实现； 堆栈和队列的具体应用举例。,3.1 堆 栈,若对线性表加以限定，使得插入和删除操作只能在它的某一端进行，那么这种线性表就被称为“堆栈”，简称为“栈”。所以，栈是一种特殊的线性表。,3.1.1 堆栈的基本知识,在一个栈中，允许进行插入和删除的那一端被称为“栈顶”，不能进行插入和删除的那一端被称为“栈底”。从当前栈顶处插入一个新元素的操作，称为“进栈(push)
2、”；从当前栈顶处删除一个元素的操作，称为“出栈(pop)”。,常把栈称作是有“后进先出（LIFO）”、或有“先进后出（FILO）”逻辑特点的数据结构，其意是元素到达栈的顺序与元素离开栈的顺序恰好是相反的。,图3-1 栈的示意图,例3-1 设有6个元素a1、a2、a3、a4、a5、a6，它们以此顺序依次进栈（即a1必须最先进栈，然后是a2进栈，最后才是a6进栈）。假定要求它们的出栈顺序是a2、a3、a4、a6、a5、a1，那么应该如何安排push和pop操作序列？这个栈的容量至少要有多大？,当采用顺序式存储结构实现一个堆栈时，就称它为“顺序栈”。由于堆栈是线性表的一个特例，因此，顺序栈就是顺序表
3、的一个特例。,3.1.2 堆栈的顺序存储实现,算法3-1 新建顺序栈的算法。 创建一个顺序栈Ss，算法名为Create_Ss()，参数为Ss、Ss_top、Ss_max。,1创建一个顺序栈,Create_Ss (Ss, Ss_top, Ss_max) elemtype SsMAX*size; /*通过数组，申请一个连续的存储区 */ Ss_max = MAX ; /* 将顺序栈可容纳的最多元素个数设置为MAX */ Ss_top = 0 ; /* 设置栈顶指针，开始时为空 */ return Ok; ,图3-2 创建后的空顺序栈示意图,算法3-2 顺序栈的进栈算法。 根据Ss_top的指示，让
4、数据元素x进入顺序栈Ss的栈顶，成为新的栈顶元素。算法名为Push_Ss ()，参数为Ss、Ss_top、Ss_max、x。,2往顺序栈里插入一个新元素进栈,Push_Ss(Ss, Ss_top, Ss_max, x) if (Ss_top = Ss_max) /* 顺序栈已满 */ return ERROR ; else Ss_top+; /* 调整栈顶指针 */ Ss Ss_top = x; /* x进栈 */ ,图3-3 Ss_top与进栈元素间的关系,图3-4 共享存储空间的两个顺序栈,如果在顺序栈满时仍打算进栈，就称为发生了“上溢（Overflow）”出错。,算法3-3 顺序栈的出栈
5、算法。 根据Ss_top的指示，将当前栈顶元素的内容取出送入变量x，然后将其从栈中删除。算法名为Pop_Ss ()，参数为Ss、x。,3删除顺序栈的栈顶元素出栈,Pop_Ss (Ss_top, x) if (Ss_top = 0 ) /* 顺序栈为空 */ printf (“The stack is empty !“); else x = SsSs_top ; Ss_top - ; ,图3-5 元素进、出栈时Ss_top的变化,如果在顺序栈空时仍打算出栈，就称为发生了“下溢（Underflow）”出错。,算法3-4 获取顺序栈栈顶元素的算法。 有顺序栈Ss，将当前栈顶元素值读到变量x。算法名为
6、Get_Ss()，参数为Ss、Ss_top、x。,4获取顺序栈栈顶元素,Get_Ss(Ss, Ss_top, x) if (Ss_top = 0) printf (“The stack is empty !“); else x = SsSs_top ; ,算法3-5 遍历顺序栈算法。 已知顺序栈Ss，把它栈顶到栈底诸元素的值逐个显示出来。算法名为Display_Ss()，参数为Ss、Ss_top。,5对顺序栈进行遍历,Display_Ss(Ss, Ss_top) i = Ss_top ; for ( i, i=0, i-) printf (“%d“, Ssi); ,当采用链式存储结构实现一个堆
7、栈时，就称它为“链栈”。由于堆栈是线性表的一个特例，因此，链栈就是链表的一个特例。 通常，链栈都是以单链表结构的形式来表示的。,3.1.3 堆栈的链式存储实现,图3-6 链栈的示意图,算法3-6 创建一个空链栈。 创建一个空链栈Ls，算法名为,1创建一个链栈,Create_Ls()，参数为Ls_top。 Create_Ls (Ls_top) Ls_top = NULL ; ,算法3-7 链栈进栈算法。 已知链栈Ls。根据Ls_top的指示，让数据元素x进入链栈Ls的栈顶位置，成为新的栈顶元素。算法名为Push_Ls ()，参数为Ls_top、x。,2往链栈里插入一个新元素进栈,Push_Ls(
8、Ls_top, x) ptr = malloc (size) ; /* 申请一个存储结点 */ ptr-Data = x ; ptr-Next = Ls_top ; /* 调整链表指针，完成结点插入 */ Ls_top = ptr ; ,图3-7 一个元素进入链栈的示意图,算法3-8 链栈出栈算法。 已知链栈Ls。根据Ls_top的指示，将栈顶元素取值存入变量x，然后删除。算法名为Pop_Ls ()，参数为Ls_top、x。,3从链栈里删除一个元素出栈,Pop_Ls (Ls_top, x) if (Ls_top = NULL) /* 链栈已空，不能再出栈 */ printf (“The lin
9、ked stack is underflow!“); else /* 实现出栈 */ ptr = Ls_top ; /* 让指针ptr指向栈顶结点 */ x = ptr-Data ; Ls_top = ptr-Next ; free (ptr) ; ,图3-8 一个元素从链栈中出栈的示意图,例3-3 编写一个算法，利用堆栈结构将键盘上输入的字符串逆向输出，整个输入在遇到回车换行符（n）时停止。 解：由于并不知道输入的字符串到底有多长，因此采用链栈来解决这个问题比较合适。在给出的算法里，我们直接调用了上面给出的算法3-7和算法3-8。,Rr_Ls (Ls_top) scanf (“%c“, ,3
10、.2 队 列,若对线性表加以限定，使得插入操作在表的一端进行，删除操作在表的另一端进行，那么这种线性表被称为“队列”。所以，队列是一种特殊的线性表。 队列是一个线性表，队列中数据元素间的逻辑结构呈线性关系； 进入队列（即插入）被限制在一端进行，退出队列（即删除）被限制在另一端进行，进队和出队的位置是不能任意为之的。,3.1.1 认识文件面板,在一个队列中，被允许进入队列的一端称为“队尾（Rear）”，被允许退出队列的一端称为“队首（Front）”。当一个元素从队列的队尾插入时，称此操作为“进队”；从当前的队首删除一个元素时，称此操作为“出队”。 当一个队列里不含有任何数据元素时，称其为“空队列
11、”。,图3-9 队列示意图,最先进入队列的那个元素肯定是最先从队列中移出的。因此，常把队列称作是具有“先进先出（FIFO）”、或具有“后进后出（LILO）”逻辑特点的数据结构，其含意是元素到达队列的顺序与元素离开队列的顺序是完全一致的。,当采用顺序式存储结构实现一个队列时，就称它为“顺序队列”。由于队列是线性表的一个特例，因此，顺序队列就是顺序表的一个特例。,3.2.2 队列的顺序存储实现,算法3-9 创建顺序队列算法。 创建一个顺序队列Qs，算法名为Create_Qs()，参数为Qs、Qs_front、Qs_rear、Qs_max。,1创建一个顺序队列,Create_Qs(Qs, Qs_fr
12、ont, Qs_rear, Qs_max) elemtype QsMAX*size; /* 通过数组，申请一个连续的存储区 */ Qs_max = MAX ; /* 将顺序队列可容纳的最多元素个数设置为MAX */ Qs_front = 0; /* 让指针Qs_front指向顺序队列首 */ Qs_rear = 0 ; /* 让指针Qs_rear指向顺序队列尾 */ return OK ; ,图3-11 创建后的空顺序队列,算法3-10 顺序队列进队算法。 依照队尾指针Qs_rear的指示，往顺序队列Qs的队尾插入一个新元素x。算法名为Insert_Qs()，参数为Qs_rear、Qs_max
13、、x。,2往顺序队列里插入一个元素进队,Insert_Qs(Qs_rear, Qs_max, x) if (Qs_rear = Qs_max) /* 存储区上溢！*/ printf (“The queue is overflow!“); else Qs_rear + ; QsQs_rear = x ; ,图3-12 一种队列满的情形,算法3-11 顺序队列的出队算法。 依照队首指针Qs_front的指示，把顺序队列Qs的队首元素删除。算法名为Delete_Qs()，参数为Qs_front、Qs_rear、x。,3从顺序队列里删除一个元素出队,Delete_Qs(Qs_front, Qs_rea
14、r, x) if (Qs_front = Qs_rear) printf (“The queue is empty!“); else Qs_front+ ; x = QsQs_front ; ,图3-13 顺序队列中进、出队的几种情况,在队列中，有空闲空间、但又不能进行插入的情形，常被称为是“假溢出”。,图3-14 假溢出的情形,算法3-12 顺序队列判空算法。 算法描述：已知顺序队列Qs，若空则返回1，否则返回0。算法名为Empty_Qs()，参数为Qs_front、Qs_rear。,4判顺序队列是否为空,Empty_Qs(Qs_front, Qs_rear) if (Qs_front =
15、Qs_rear) return (1) ; else return (0) ; ,算法3-13 取顺序队列队首元素的算法。 已知顺序队列Qs，返回它的队首元素。算法名为Head_Qs()，参数为Qs、Qs_front、Qs_rear。,5获取顺序队列队首元素,Head_Qs(Qs, Qs_front, Qs_rear) if (Qs_front = Qs_rear) printf (“The queue is empty!“); else x = QsQs_pront+1 ; return (x) ; ,假溢出时队列里的空闲区域是从队首往队尾延伸的。为利用这部分位于队首的空闲区域，就应在顺序队
16、列出现“假溢出”，但还要执行进队、出队操作时，能够让队列的队尾指针Qs_rear、队首指针Qs_front“回指”到存储区的起始位置处去。即把分配给队列的那个连续存储区的首、尾连接在一起，形成一个圆环，不再有队尾、队首之分。这种首、尾相连的顺序队列，称作是“循环顺序队列”，简称为“循环队列”。,3.2.3 循环队列的顺序存储实现,算法3-14 创建循环队列的算法。 创建一个循环队列Cq，算法名为Create_Cq()，参数为Cq、Cq_front、Cq_rear、Cq_max。,1创建一个循环（顺序）队列,Create_Cq(Cq, Cq_front, Cq_rear, Cq_max) elemtype CqMAX*size;
