栈的原理与应用PPT学习课件

2.2栈的原理与应用,栈的基本概念,栈（stack）是一种运算受限的线性表，它限定只能在表的一端进行插入和删除等操作。,（a1,a2,.,ai-1,ai,ai+1,an）,插入,删除,02,栈的基本概念,允许进行插入和删除操作的一端称为栈顶（top）另一端称为栈底（bottom）不含元素的栈称为空栈,出栈Pop,进栈Push,栈顶,栈底,top,空栈,top,bottom,bottom,03,栈的基本概念,栈的特点：先进后出（FILO）或后进先出（LIFO）,bottom,bottom,A,A,B,C,D,E,A,B,A进栈,BCDE进栈,EDC出栈,C,D,E,图2.1进栈与出栈操作,04,05,栈的应用举例,（a）车轨设置（b）驶入（c）驶出,图2.2火车调度模型,火车头1,火车头2,火车头2,火车头1,火车调度装置的功能与栈的功能类同,思考：假设有A,B,C三个元素进S栈的顺序是A,B,C，写出所有可能的出栈序列。,CBA,ACB,ABC,CAB,BAC,BCA,06,栈的问题实例,07,栈的基本操作,（1）构造栈。（2）判栈空。（3）判栈满。,（4）进栈。（5）出栈。（6）取栈顶元素。,08,栈的顺序存储结构,1.顺序栈的类型定义#defineStackSize100/顺序栈存储空间的总分配量typedefstruct/顺序栈存储类型DataTypedataStackSize;/存放顺序栈的数组inttop;/记录栈顶元素位置的变量SeqStack;,顺序栈被定义为一个结构体类型，其中DataType为栈元素的数据类型，可以根据需要而指定某种具体的类型。data为一个一维数组，用于存储栈中的数据元素，top为int类型，用于记录栈顶元素所在的位置。,顺序栈的图示,栈空：top=-1,栈满：top=StackSize-1,约定栈顶指针指向栈顶元素的位置。,栈的顺序存储结构,09,10,顺序栈的基本操作实现,首先创建一个空栈，并将栈顶下标top初始化为-1,voidInitStack(SeqStack*S)S-top=-1;/初始化的顺序栈为空,（1）初始化栈操作,11,顺序栈的基本操作实现,（2）判断栈空操作,判断是否是空栈（即S-top=-1），若栈S为空，则返回1；否则返回0。,#defineTRUE1#defineFALSE0intStackEmpty(SeqStack*S)if(S-top=-1)/栈为空returnTRUE;elsereturnFALSE;,（3）判栈满操作,判断是否是满栈（即S-top=StackSize-1），若栈S为满栈，则返回1；否则返回0。,intStackFull(SeqStack*S)if(S-top=StackSize-1)returnTRUE;elsereturnFALSE;,顺序栈的基本操作实现,12,x进栈后,（4）进栈操作,图2.3进栈操作过程图,StackSize-1nn-1n-210,StackSize-1nn-1n-210,StackSize-1nn-1n-210,顺序栈的基本操作实现,13,（4）进栈操作intPush(SeqStack*S,DataTypex)if(StackFull(S)/栈为满printf(栈满!);returnFALSE;/栈满不能进栈else/栈不为满S-top+;S-dataS-top=x;returnTRUE;,顺序栈的基本操作实现,14,an出栈后,（5）出栈操作,图2.4出栈操作过程图,StackSize-1nn-1n-210,StackSize-1nn-1n-210,StackSize-1nn-1n-210,顺序栈的基本操作实现,15,顺序栈的基本操作实现,intPop(SeqStack*S,DataType*x)if(StackEmpty(S)/判断栈是否为空printf(栈空!);returnFALSE;/栈空不能出栈else/栈不为空*x=S-dataS-top;S-top-;returnTRUE;,（5）出栈操作,16,顺序栈的基本操作实现,intStackTop(SeqStack*S,DataType*x)if(StackEmpty(S)/判断栈是否为空printf(栈空!);returnFALSE;else/栈不为空*x=S-dataS-top;returnTRUE;,（6）取栈顶元素,将栈顶元素赋给指针变量*x，操作结果只是读取栈顶元素，栈S不发生变化。,17,18,小结,(1)栈是一种加了限制条件的线性结构，进栈和出栈只能从栈的一个端点进行；(2)栈是“后进先出”或者“先进后出”的线性表；(3)栈中的元素个数可以是0，此时是空栈；(4)栈的元素的个数是可以变化的，可以是多个，但不能是无穷多个；(5)每个栈中的元素的类型相同。,19,课后作业:括号匹配检验,算法思想：在检