栈和队列学习课件

第三章栈和队列7/2/2023【课前思考前思考】1.什么是什么是线性性结构？构？简单地说，线性结构是一个数据元素的序列。2.你你见过餐餐馆中一叠一叠的中一叠一叠的盘子子吗？如果它？如果它们是按是按1,2,n 的次序往上叠的，那么使用的次序往上叠的，那么使用时候的次序候的次序应是什么是什么样的？的？必然是依从上往下的次序，即n,2,1。它们遵循的是后进先出的规律，这正是本章要讨论的栈的结构特点。3.在日常生活中，在日常生活中，为了了维持正常的社会秩序而出持正常的社会秩序而出现的常的常见现象是什么？象是什么？是排队。在计算机程序中，模拟排队的数据结构是队列。7/2/2023【学学习目目标】1.掌握栈和队列这两种抽象数据类型的特点，并能在相应的应用问题中正确选用它们。2.熟练掌握栈类型的两种实现方法。3.熟练掌握循环队列和链队列的基本操作实现算法。4.理解递归算法执行过程中栈的状态变化过程。7/2/2023栈和队列是在程序设计中被广泛使用的两种线性数据结构，因此本章的学习重点在于掌握这两种结构的特点，以便能在应用问题中正确使用。【知【知识点】点】顺序栈、链栈、循环队列、链队列【重点和重点和难点点】7/2/2023【学学习指南指南】在这一章中，主要是学习如何在求解应用问题中适当地应用栈和队列，栈和队列在两种存储结构中的实现都不难，但应该对它们了如指掌，特别要注意它们的基本操作实现时的一些特殊情况，如栈满和栈空、队满和队空的条件以及它们的描述方法。本章要求必须完成的算法设计题为：3.15，3.17，3.19，3.22，3.27,3.28，3.30，3.31，3.32。其中前4个主要是练习栈的应用，后4个主要是有关队列的实现方法的练习。7/2/2023通常称，栈和队列是限定插入和删除插入和删除只能只能在表的“端点端点”进行的线性表。线性表线性表 栈栈 队列队列Insert(L,i,x)Insert(S,n+1,x)Insert(Q,n+1,x)1in+1Delete(L,i)Delete(S,n)Delete(Q,1)1in栈和队列是两种常用的数据类型栈和队列是两种常用的数据类型7/2/20233.1 栈栈3.2 栈的应用举例栈的应用举例3.4 队列队列目目 录录3.3 栈与递归的实现栈与递归的实现退出退出7/2/20233.1 栈栈一、栈的定义一、栈的定义栈栈(stack)作为一种限定性线性表，是将线性表的插入和删除运算限制为仅在表的一端进行，通常将表中允许进行插入、删除操作的一端称为栈顶(Top)，因此栈顶的当前位置是动态变化的，它由一个称为栈顶指针的位置指示器指示。同时表的另一端为固定的一端，被称为栈底(Bottom)。当栈中没有元素时称为空栈。栈的插入操作被形象地称为进栈或入栈，删除操作称为出栈或退栈。根据栈的定义可知，最先放入栈中元素在栈底，最后放入的元素在栈顶，而删除元素刚好相反，最后放入的元素最先删除，最先放入的元素最后删除。也就是说，栈是一种后进先出(LastInFirstOut)的线性表，简称为LIFO表。7/2/2023图图3.1 栈栈7/2/2023二、栈的主要运算二、栈的主要运算1.初始化栈：初始化栈：InitStack(&S)将栈S置为一个空栈(不含任何元素)。2.进栈：进栈：PUSH(&S,X)将元素X插入到栈S中，也称为“入栈”、“插入”、“压入”。3.出栈：出栈：POP(&S，&e)删除栈S中的栈顶元素，也称为”退栈”、“删除”、“弹出”。4.取栈顶元素：取栈顶元素：GETTOP(S，&e)取栈S中栈顶元素。5.判栈空：判栈空：EMPTY(S)判断栈S是否为空，若为空，返回值为1，否则返回值为0。7/2/2023三、三、栈的抽象数据类型描述栈的抽象数据类型描述ADTStack 数据对象数据对象：D=ai|aiElemSet，i=1,2,n,n0 数据关系数据关系：R1=|ai-1,aiD,i=1,2,n 基本操作：基本操作：InitStack(&S)操作前提：S为未初始化的栈。操作结果：将S初始化为空栈。ClearStack(&S)操作前提：栈S已经存在。操作结果：将栈S置成空栈。StackEmpty(S)操作前提：栈S已经存在。操作结果：若栈S为空，则返回TRUE,否则FALSE。7/2/2023StackLength(S)操作前提：栈S已经存在。操作结果：返回S的元素个数即栈的长度。IsFull(S)操作前提：栈S已经存在。操作结果：判栈满函数，若S栈已满，则函数值为TRUE，否则为FALSE。StackTraverse(S,visit()操作前提：栈S已经存在且非空。操作结果：从栈底到栈顶依次对S底每个元素调用函数visit()。一旦visit()失败，则操作失效。7/2/2023Push(&S,e)操作前提：栈S已经存在。操作结果：在S的顶部插入(亦称压入)元素e；若S栈未满，将e插入栈顶位置，若栈已满，则返回FALSE，表示操作失败，否则返回TRUE。Pop(&S,&e)操作前提：栈S已经存在。操作结果：删除(亦称弹出)栈S的顶部元素，并用e带回该值；若栈为空，返回值为FALSE，表示操作失败，否则返回TRUE。GetTop(S,&e)操作前提：栈S已经存在。操作结果：取栈S的顶部元素。与Pop(&S,&e)不同之处在于GetTop(S,&e)不改变栈顶的位置。ADTStack7/2/2023 1.顺序栈顺序栈顺序栈是用顺序存储结构实现的栈，即利用一组地址连续的存储单元依次存放自栈底到栈顶的数据元素，同时由于栈的操作的特殊性，还必须附设一个位置指针top（栈顶指针）来动态地指示栈顶元素在顺序栈中的位置。通常以top=0或top=-1表示空栈。顺序栈的存储结构可以用C语言中的一维数组来表示。栈的顺序存储结构定义如下：四、四、栈的表示和实现栈的表示和实现 7/2/2023#define STACK_INIT_SIZE 100 /存储空间初始分配量#define STACKINCREMENT 10 /存储空间分配增量typedef struct SElemType*base;/在栈构造前和销毁后base值为NULL SElemType*top;/栈顶指针 int stacksize;SqStack;/当前已分配存储空间或简单定义如下：#define M 100 int sM;int top;7/2/2023图3.2顺序栈中的进栈和出栈初态：初态：top=0;空栈，栈中无元素，进栈：进栈：stop=x;top=top+1;退栈：退栈：top=top-1;取stop;栈满：栈满：top=M;栈溢出（上益），不能再进栈（错误状态）top=0时不能退栈，下益（正常状态，常作控制条件）7/2/2023（1）构造空顺序栈算法构造空顺序栈算法:初始化栈初始化栈Status InitStack(SqStack&S)/构造一个空栈构造一个空栈 SS.base=(SElemType*)malloc(STACK_INIT_SIZE*sizeof(SElemType);if(!S.base)exit(OVERFLOW);/为为栈栈分分配配存存储储空空间失败间失败S.top=S.base;/令栈顶指针令栈顶指针=栈底指针栈底指针S.stacksize=STACK_INIT_SIZE;/设设置置栈栈的的当当前前可可使用的最大容量使用的最大容量return OK;/InitStackInitStack2.顺序栈基本操作的实现如下顺序栈基本操作的实现如下:7/2/2023程序描述：程序描述：/This program is to initialize a stack#include#include#include#define STACK_INIT_SIZE 100#define STACKINCREMENT 10#define OK 1#define ERROR 0 typedef int SElemType;typedef struct/define structure SqStack()SElemType*base;SElemType*top;int stacksize;SqStack;7/2/2023 int InitStackint InitStack(SqStackSqStack&S)/&S)/InitStackInitStack()sub-function ()sub-function S.base=S.base=(SElemTypeSElemType)mallocmalloc(STACK_INIT_SIZE*(STACK_INIT_SIZE*sizeofsizeof(SElemTypeSElemType););if(!S.base)if(!S.base)printfprintf(“Allocate space failure!n“);(“Allocate space failure!n“);return(ERROR);return(ERROR);S.top=S.base;S.top=S.base;S.S.stacksizestacksize=STACK_INIT_SIZE;=STACK_INIT_SIZE;return(OK);/return(OK);/InitStackInitStack()end()end void main()/main()function void main()/main()function SqStackSqStack S;S;if(if(InitStackInitStack(S)(S)printfprintf(Success!The stack has been created (Success!The stack has been created!n“);!n“);printf printf(.OK!n“);(.OK!n“);getchgetch();();7/2/2023（2）取顺序栈的栈顶元素取顺序栈的栈顶元素 Status GetTop(SqStack S,SElemType&e)/如如果果栈栈 S 空空，返返回回 ERROR；如如果果栈栈 S 不不空空，用用 e 返返回回栈栈 S 的的栈栈顶元素，并返回顶元素，并返回 OK。if(S.top=S.base)return ERROR;/如果栈如果栈 S 为空，则返回为空，则返回 ERROR e=*(S.top-1);/将栈顶指针减将栈顶指针减 1 后所指向的单元内的值赋给后所指向的单元内的值赋给 e return OK;/GetTop GetTop7/2/2023（3）将元素压入顺序栈算法（将元素压入顺序栈算法（进栈）进栈）Status Push(SqStack&S,SElemType e)/将元素将元素 e 插入到栈插入到栈 S 中，成为新的栈顶元素中，成为新的栈顶元素 if(S.top-S.base S.stacksize)/如果栈满，则追加存储空间如果栈满，则追加存储空间 S.base S.base=(SElemTypeSElemType *)reallocrealloc (S.base,S.base,(S.S.stacksixestacksixe+STACKINCREMENT*+STACKINCREMENT*sizeofsizeof(SElemType SElemType););if(!S.base)exit(OVERFLOW);/if(!S.base)exit(OVERFLOW);/追加存储空间失败追加存储空间失败 S.top=S.base+S.S.top=S.base+S.stacksizestacksize;/;/修改栈顶指针修改栈顶指针 S.S.stacksizestacksize+=STACKINCREMENT;/+=STACKINCREMENT;/修改当前栈的存储空间修改当前栈的存储空间 /if if 结束结束 *S.top+=e;/S.top+=e;/先将先将 e e 送入栈顶，然后将栈顶指针加