详解数据结构 第3章 栈和队列.pptVIP

第3章 栈和队列 3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现 3.4 队列 第3章 栈和队列 一.基本内容 栈和队列的结构特性;在两种存储结构上如何实现栈和队列的基本操作;栈和队列在程序设计中的应用. 第3章 栈和队列 二.学习要点 1.掌握栈和队列的特点,能在应用问题中正确选用它们. 2.熟练掌握栈类型的两种实现方法,即两种存储结构表示时的基本操作实现算法,特别应注意栈满和栈空的条件及其描述方法. 3.熟练掌握循环队列和链队列的基本操作实现算法,特别注意队满和队空的描述方法. 3.1 栈 3.1.1 抽象数据类型栈的定义 1. 栈的定义：仅在表尾插入和删除的线性表。 特点:后进先出LIFO(Last-in First -out)的线性表 允许插入和删除的一端称为栈顶 (top)，另一端称为栈底(bottom) 栈底：表头； 栈顶：表尾 2.栈的基本操作： 初始化，判空，入栈，出栈， 取栈顶元素，置空，求长度 3.1 栈 3.1.2 栈的表示和实现 1.顺序栈,即栈的顺序存储结构. 2.链栈,即栈的链式存储结构. 3.静态分配整型指针 1.顺序栈 1).顺序栈的表示 1.顺序栈 说明： base称为栈底指针，始终指向栈底； 当base = NULL时，表明栈结构不存在。 top为栈顶指针 a. top的初始值指向栈底，即top=base b. 空栈：当top=base时为栈空的标记 c. 当栈非空时，top的位置：指向当前栈 顶元素的下一个位置 stacksize ——当前栈可使用的最大容量 进栈示例 退栈示例 几点说明： 栈空条件：s. top =s. base 此时不能出栈 栈满条件：s.top-s.base=s.stacksize 进栈操作：*s.top++=e; 或*s.top=e; s.top++; 退栈操作：e=*--s.top； 或s.top--； e=*s.top； 当栈满时再做进栈运算必定产生空间溢出， 简称“上溢”; 当栈空时再做退栈运算也将产生溢出，简 称“下溢”。 1.顺序栈 栈的基本运算有如下几种： （1）InitStack(S) 主要功能是：初始化操作，构造一个空栈操作。 （2）DestroyStack(S) 主要功能是：将已经存在的栈销毁。 （3）ClearStack(S) 主要功能是：将已经存在的栈清空。 （4）StackEmpty(S) 主要功能是：判断栈是否为空，若S为空，则返回TRUE,否则返回FALSE。 （5）StackLength(S) 主要功能是：返回当前栈中元素的个数。 1.顺序栈 （6）GetTop(S) 主要功能是：若栈S不空，则取栈顶元素的值，注意栈顶元素不被删除，栈顶指针top也不被改变。 （7）Push(S, x) 主要功能是：入栈操作，在S栈的顶部插入一个元素x，栈顶位置由top指针指出。 （8）Pop(S) 主要功能是：出栈操作，若栈S不空，则在栈顶删除栈顶元素，并返回被删除元素的值。 （9）DisplayStack 主要功能是：栈的遍历操作，即从栈底到栈顶逐次显示栈中的元素。 1.顺序栈 2).顺序栈基本操作的实现 1.顺序栈 思考题：如果进栈的数据元素序列为A、B、C、D，则可能得到的出栈序列有多少种？写出全部可能的序列。 2.链栈 不带头结点的单链表，其插入和删除操作仅限制在表头位置上进行。链表的头指针即栈顶指针。 类型定义： typedef struct SNode{ SElemType data; struct SNode *next; }SNode, *LinkStack; LinkStack s; 2.链栈 链栈示意图 p47 图3.3 栈空条件： s=NULL 栈满条件： 无 / 无Free Memory可申请 2.链栈 进栈操作 Status Push_L (LinkStack s，SElemType e) { p=(LinkStack)malloc(sizeof(SNode)); if (!p) exit(Overflow); p-data = e; p-next = s; s=p; return OK; } 2.链栈 退栈操作 Status Pop_L (LinkStack s, SElemType e) { if (!s) return ERR