资源描述：
《数据结构中栈介绍79134》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、数据结构中栈的介绍79134有些事，明知是错的，也要去坚持，因为不甘心；有些人，明知是爱的，也要去放弃，因为没结局；有时候，明知没路了，却还在前行，因为习惯了。数据结构中栈的介绍 1.栈的概念 栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。 栈的修改是按后进先出的原则进行的。栈又称为后进先出(LastInFirstOut)表，简称为LIFO表。 如图1所示：假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元素。
2、 图1 图2 2.栈的存储与操作 由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针t（称为栈顶指针）来指示栈顶元素的当前位置。 我们用一个数组s[1..m]来表示一个栈时，将栈底固定在数组的底部，即s[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。当t=0时，表示这个栈为一个空栈。当t=m时，表示这个栈已满。 可以用下列方式定义栈： const m=栈表目数的上限; type stack=array[1..m]ofstype;{栈的数据类型} var s:stac
3、k; t:integer;{栈顶指针} 进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）：(1)进栈过程（push）①若t≥m时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作②）；②置t=t+1（栈指针加１，指向进栈地址）；③S(t)=x，结束（x为新进栈的元素）；procedurepush(vars:stack;x:integer;vart:integer);beginift=mthenwriteln('overflow')elsebegint:=t+1;s[t]:=x;endend;(2)退栈函数（pop）①若t≤0，则给出下溢信
4、息，作出错处理(退栈前先检查是否已为空栈，空则下溢；不空则作②)；②x=s(t)，（退栈后的元素赋给x）；③t=t-1，结束（栈指针减１，指向栈顶）。functionpop(vars:stack;vart:integer):integer;beginift=0thenwriteln('underflow')elsebeginpop:=s[t];t:=t-1;endend;(3)读栈顶元素函数（top）functiontop(vars:stack;t:integer):integer;beginift=0thenwriteln('underflow')elsetop:=s[t
5、];end;3栈的应用举例【例10-4】.设栈S的初始状态为空，元素a,b,c,d,e,f,g依次入栈，以下出栈序列不可能出现的是（）。A.a,b,c,e,d,f,gB.b,c,a,f,e,g,dC.a,e,d,c,b,f,gD.d,c,f,e,b,a,gE.g,e,f,d,c,b,a 题解：此题可以采用模拟的方法，依次判断各个选项是否能出现。如A，每个元素依次进栈然后出栈，即得到此序列。再来看B，a,b进栈，然后b出栈，c进栈后出栈，a出栈，d，e，f进栈，f，e出栈，g进栈后出栈，d出栈，可以满足。依此类推，发现只有E不能满足，答案为E。【例10-5】.如下图,有一个
6、无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数。出口←←12345S↓ 题解：首先必是1，2，3进栈，然后3出栈，此时栈中有元素1，2，未进栈元素有4，5。我们可以分情况讨论，由于2一定在1之前出栈，我们可以讨论4，5的出栈顺序，如下：(1)4先出栈：此时相当于4，5不经过栈直接到出口。相当于1，2，4，5四个数字的一个排列，2排在1前，4排在5前，共有种数/4=6（种）。(2)5先出栈：此时4和5的出栈顺序必连续，有以下三种排
7、列：5421；2541；2154。综上所述，总的排列数是9种。【例1】计算后缀表达式题目描述 数学上使用的是中缀表达式，在中缀表达式中需要使用括号来改变运算的优先级。事实上我们可以用后缀表达式或前缀表达式，这两种表达式里就可以完全避免使用括号。后缀表达式：运算符放在两个运算对象之后。所有计算按运算符出现的顺序，由左而右进行。例如：3*(5-2)+7对应的后缀表达式为3.5.2.-*7.+@ 现有一后缀表达式，让你求表达式的值，已知运算符仅限于"+","-","*","/"四种运算。输入@表示表达式结束，'.'为
