《数据结构中栈的介绍》由会员分享，可在线阅读，更多相关《数据结构中栈的介绍（5页珍藏版）》请在金锄头文库上搜索。
1、数据结构中栈的介绍1.栈的概念栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。栈的修改是按后进先出的原则进行的。栈又称为后进先出(Last In First Out)表，简称为 LIFO 表。如图 1 所示：假设一个栈 S 中的元素为 an,an-1,.,a1，则称 a1为栈底元素，a n为栈顶元素。图 1图 22.栈的存储与操作由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针 t（称为栈顶指针）来指示栈顶元素的当前位置。我们用一个数组 s1.m来表示一个栈时，将栈底固定
2、在数组的底部，即 s1为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。当 t=0 时，表示这个栈为一个空栈。当 t=m 时，表示这个栈已满。可以用下列方式定义栈：constm=栈表目数的上限;typestack=array1.m of stype; 栈的数据类型vars:stack;t:integer; 栈顶指针进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）： (1)进栈过程（push）若 tm 时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢出；不满则作） ；置 t=t+1（栈指针加，指向进栈地址） ；S(t)=x，结束（x 为新进栈的元素） ；proce
3、dure push(var s:stack; x:integer;var t:integer);beginif t=m then writeln(overflow)else1tbegint:=t+1;st:=x;endend;(2)退栈函数（pop）若 t0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈， 空则下溢；不空则作)；x=s(t)， （退栈后的元素赋给 x） ；t=t-1，结束（栈指针减，指向栈顶） 。function pop(var s:stack;var t:integer):integer;beginif t=0 then writeln(underflow)elseb
4、eginpop:=st;t:=t-1;endend;(3)读栈顶元素函数（top）function top(var s:stack; t:integer):integer;beginif t=0 then writeln(underflow)elsetop:=st;end;3 栈的应用举例【例 10-4】.设栈 S 的初始状态为空，元素 a,b,c,d,e,f,g 依次入栈，以下出栈序列不可能出现的是（ ） 。A.a,b,c,e,d,f,g B.b,c,a,f,e,g,d C.a,e,d,c,b,f,gD.d,c,f,e,b,a,g E.g,e,f,d,c,b,a题解：此题可以采用模拟的方法，
5、依次判断各个选项是否能出现。如 A，每个元素依次进栈然后出栈，即得到此序列。再来看 B，a,b 进栈，然后 b 出栈，c 进栈后出栈，a 出栈，d，e，f 进栈，f，e 出栈， g 进栈后出栈，d 出栈，可以满足。依此类推，发现只有 E不能满足，答案为 E。【例 10-5】.如下图,有一个无穷大的的栈 S,在栈的右边排列着 1,2,3,4,5 共五个车厢。其中每个车厢可以向左行走,也可以进入栈 S 让后面的车厢通过。现已知第一个到达出口的是 3号车厢，请写出所有可能的到达出口的车厢排列总数。出口 1 2 3 4 5 S 题解：首先必是 1，2，3 进栈，然后 3 出栈，此时栈中有元素 1，2，
6、未进栈元素有4，5。我们可以分情况讨论，由于 2 一定在 1 之前出栈，我们可以讨论 4，5 的出栈顺序，如下：(1)4 先出栈：此时相当于 4，5 不经过栈直接到出口。相当于 1，2，4，5 四个数字的一个排列，2 排在 1 前，4 排在 5 前，共有种数 /4=6（种）。4A(2)5 先出栈：此时 4 和 5 的出栈顺序必连续，有以下三种排列：5 4 2 1；2 5 4 1；2 1 5 4。综上所述，总的排列数是 9 种。【例 1】计算后缀表达式题目描述数学上使用的是中缀表达式，在中缀表达式中需要使用括号来改变运算的优先级。事实上我们可以用后缀表达式或前缀表达式，这两种表达式里就可以完全避
7、免使用括号。后缀表达式：运算符放在两个运算对象之后。所有计算按运算符出现的顺序，由左而右进行。例如：3*(5-2)+7 对应的后缀表达式为 3.5.2.- *7.+现有一后缀表达式，让你求表达式的值，已知运算符仅限于+,-,*,/四种运算。输入表示表达式结束， .为操作数的结束符。如：后缀表达式 3.5.2.- *7.+的值为16。输入一个后缀表达式，无需判错， “/”作为整除运算。 输出后缀表达式的值，一个整数。参考程序：program ex10_6;constn=30;typestack=array1.n of integer;vars:stack;a:string;t,i,j,k,q:i
8、nteger;procedure push(var s:stack; x:integer;var top:integer);beginif top=n then writeln(overflow)elsebegintop:=top+1;stop:=x;endend;function pop(var s:stack;var top:integer):integer;beginif top=0 then writeln(underflow)elsebeginpop:=stop;top:=top-1;endend;begini:=1; t:=0;readln(a);while ai=0，则该物品可选
9、；若 tot-wi 0)and (i=0)and(i0)thenI=n 时退栈begini:=stacktop;dec(top);tot:=tot+wi;if (i=n)and(top0) then begin如退栈后 I=n，即退栈的元素是最后一个，则需再次退栈，因为此时已无法选择下一个物品i:=stacktop;dec(top);tot:=tot+wi;end;end;inc(i);end;end;exit(false);end;beginreadln(t,n);for i:=1 to n do read(wi);if knap(t) then writeln(Yes)else writeln(No);end.
