资源描述：
《栈和队列课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第三章栈和队列3.1栈3.2栈的应用举例3.3递归3.4队列3.5队列应用举例【教学目的】掌握特殊的线性表桟与队列的工作原理，桟与队列的顺序、链式存储结构下操作的实现，理解计算机系统中桟和队列的重要作用和应用【教学重点】桟与队列的工作原理及其操作实现【教学难点】入栈和出栈时的栈空和栈满，进栈和出栈时栈顶指针修改的先后顺序，理解多栈，应用栈和利用栈来理解递归，处理循环队列的队空和队满的确定，队列应用。3.1栈一栈的定义及基本操作栈：限定仅在表的一端进行插入和删除操作的线性表栈顶：允许进行插入和删除的一端栈底：不允许进行插入和删除的一端空栈：不含元素的空表入/压/进栈：栈的插入操作退/出栈：栈的删
2、除操作例：栈s=(a1,a2,a3……an)即：元素按a1……an顺序依次进栈，则第一个出栈的元素？栈的特点:先进后出/后进先出（FirstInLastOut）又称为FILO/LIFO线性表ADTStack{数据对象：D＝{ai
3、ai∈ElemSet,i=1,2,...,n,n≥0}数据关系：R1＝{
4、ai-1,ai∈D,i=2,...,n}约定an端为栈顶，a1端为栈底。基本操作：InitStack(&S)操作结果：构造一个空栈S。DestroyStack(&S)初始条件：栈S已存在。操作结果：栈S被销毁。ClearStack(&S)初始条件：栈S已存在。操作结果：将S清为
5、空栈。StackEmpty(S)初始条件：栈S已存在。操作结果：若栈S为空栈，则返回TRUE，否则FALE。StackLength(S)初始条件：栈S已存在。操作结果：返回S的元素个数，即栈的长度。GetTop(S,&e)初始条件：栈S已存在且非空。操作结果：用e返回S的栈顶元素。Pop(&S,&e)初始条件：栈S已存在且非空。操作结果：删除S的栈顶元素，并用e返回其值。Push(&S,e)初始条件：栈S已存在。操作结果：插入元素e为新的栈顶元素。StackTraverse(S,visit())初始条件：栈S已存在且非空，visit()为元素的访问函数。操作结果：从栈底到栈顶依次对S的每个元素
6、调用函数visit()，一旦visit()失败，则操作失败。}ADTStack栈结构的基本操作：1、栈初始化：Init_Stack(S)初始条件：栈S不存在操作结果：构造了一个空栈。2、销毁栈：Destroy_Stack(S)初始条件：栈S已存在操作结果：销毁一个已存在的栈。3、判栈空：Empty_Stack(S)操作结果：若S为空栈返回为1，否则返回为0。4、入栈：Push_Stack(S，x)初始条件：栈S已存在操作结果：在栈s的顶部插入一个新元素x，x成为新的栈顶元素。栈发生变化5、出栈：Pop_Stack(S)初始条件：栈S存在且非空操作结果：栈S的顶部元素从栈中删除，栈中少了一个元素
7、。栈发生变化6、取栈顶元素：GetTop_Stack(S)初始条件：栈S存在且非空操作结果：栈顶元素作为结果返回，栈不变化二、栈的顺序存储及操作的实现用一组连续的存储单元依次存放栈中的每个数据元素，并用起始端作为栈底。（顺序栈）类型定义如下所示：#defineMAXSIZE100typedefstruct{DataTypedata[MAXSIZE];inttop;}SeqStack,*PSeqStack;1、初始化栈：PSeqStackInit_SeqStack(void){//创建一顺序栈，入口参数无，返回一个指向顺序栈的指针，为零表示分配空间失败PSeqStackS;S=(PSeqStac
8、k)malloc(sizeof(SeqStack));if(S)S->top=-1;returnS;}2、销毁栈：顺序栈的销毁操作是初始化操作的逆运算。由于要修改栈的指针变量，所以要将指针地址传给该函数。voidDestroy_SeqStack(PSeqStack*S){//销毁顺序栈，入口参数：为要销毁的顺序栈指针地址if(*S)free(*S);*S=NULL;//return;}主程序中如何调用main(){PSeqStackS;S=Init_SeqStack();……Destroy_SeqStack(&S);}3、判栈空：判断栈中是否有元素，只需判断top是否等于-1intEmpty_
9、SeqStack(PSeqStackS){//判断栈是否为空，入口参数：顺序栈，返回值：1表示为空，0表示非空if(S->top==-1)return1;elsereturn0;}清空：s->top=-1求栈的长度：s->top+14、入栈入栈操作是在栈的顶部进行插入一个元素。首先判断栈是否已满，若满退出，否则，由于栈的top指向栈顶，只要将入栈元素赋到top+1的位置同时top++即可intPu
