栈的基本知识及应用

1、栈的基本知识及应用1. 栈的概念和特性栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗 看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。 而在使用时，却是从顶上拿収，也就是说，后冼的先取用，后摞上的先取用。好果我们把冼 净的碗“摞上'称为进栈（压栈），把“取用碗”称为出栈（弹出），那么，上例的特点是：后进 栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”都在最顶上进行， 或者说，元素的插入和删除是在表的一端进行而已。一般而言，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入 和删除的一

2、端称栈顶（top）,不允许插入和删除的一端称栈底（bottom）o若给定一个栈s= （a 1,辺，a3,，an）,则称ai为栈底元素，如为栈顶元素，元素爲位于元素吋之上。栈中元 素按ab a2, a3,，an的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为务， an.p，纲。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特 征。因此栈又称为后进先出（lifolast in first out）表。我们常用一个图來形象地表示栈，其形式如下图：通常，对栈进行的运算主要有以下几种：在使用栈之前，首先需要建立一个空栈，称建栈；往栈顶加入一个新元素，称进栈（压栈）；删除栈顶元素，

3、称出栈（退栈、弹出）；查看当前的栈顶元素，称读栈；注意与的区别在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。2. 栈的存储结构栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。因此，当用编程语言 写程序时，用一维数组來建栈十分方便。例如，设一维数组stackll.nj表示一个栈，其 中n为栈的容量，即可存放元素的最大个数。栈的第-个元素，或称栈底元素，是存放在s tack1处，第二个元素存放在stack2处，第i个元素存放在stacki处。另外，由于 栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈屮没有元素即 栈空时，令top=0,当top=n时，

4、表示栈满。如果一个栈已经为空，但用户还继续做出栈(读栈)操作，则会出现栈的“下溢”；如 果一个栈已经满了，用户还继续做进栈操作，则会出现栈的“上溢”。两种情况统称为栈的 溢出。3. 对栈的几种运算的实现方法：(1) 建栈这比较简单，只要建立一个一维数组，再把栈顶指针置为零。栈的容量根据具体的应用 要求而定。比如：type arraytype= arrayfl. n of integer;var stack:arraytype;top:i nteger;再在程序开始吋，置top:=0；(2) 测试栈测试栈顶指针的值，若top=0,则栈空；若top=n,则栈满。(3) 读栈若top=0,则栈空，无

5、栈顶元索可读，出错；若top<>0,贝恫送栈顶元素的值stackt opo(4) 进栈(push)将栈顶指针加1后，再把新元素送到栈顶。假设新元素x为整型，栈的最大深度为n, x和n设置为值型参。而栈和栈顶指针要设置成变量型参。procedure push(var stack:anaytype;var top:integer;n:integer;x:integer);beginif top=nthen begin writelncstack full! j; halt endelse begin top:二top+1; stacktop:= x endend;(5) 退栈(pop)

6、取得栈顶元素的值后，再把栈顶指针top减1。注意都用变量型参。procedure pop(var stack:arraytype;var top:integer;var x:integer);beginif top=0then begin writelncstack empty!'); halt endelse begin x:=stacktop; top:=top-l endend;注意：rti于栈本身和栈顶指针是密不可分的，所以有时我们把他们定义成一个记录来处理。 如：type stack=recordvec:arrayl.n of integer; n为栈可达到的最大深度top:

7、integer;end;则以上几种运算的实现只要稍做修改即可。procedure push(var s:stack;x:integer);beginif s.top=nthen begin writelncstack full!，)； halt endelse begin s.top:=s.top+l; s.vecls.top:= x endend;procedure pop(var s:stack;var x:integer);begin讦 s.top=0then begin writelncstack empty!'）; halt endelse begin x:=s.vecs.t

8、op; s.top:=s.top-l endend;出栈有时也可用函数实现，如：function pop（var s:stack）:integer;beginif s.top=0then begin writelncstack empty!'）; halt endelse begin pop:=s.vecs.topl; s.top:=s.top-l endend;栈在计算机科学领域有着广泛的应用。比如在编译和运行计算机程序的过程中，就需 要用栈进行语法检查（如检查begin和end、“（”和“）”等是否匹配）、计算表达式的值、 实现过程和函数的递归调用等。下面举例说明栈在这些方面的应用

9、。例1、假设一个表达式有英文字母（小写）、运算符（+, ，*, /）和左右小（圆）括号构成，以“”作为表达式的结朿符。请编写一个程序检查表达式中的左右圆括号 是否匹配,若匹配,则返回“yes”；否则返回“no”。表达式长度小于255,左圆 括号少于20个。分析：假设输入的字符串存储在c中（var c:string2551）o我们可以定义一个栈：var s:arrayl.maxn of char;top:integer;用它來存放表达式中从左往右的左圆括号。算法的思路为：顺序（从左往右）扫描表达式的每个字符ci,若是“（”，则让它进 栈；若遇到的是“）”，则让栈顶元素出栈；当栈发生下溢或当表达式

10、处理完毕而栈非空时, 表示不匹配，返回“yes”，否则表示匹配返回“no”。程序代码如下：var c:string;function doit（c: string）:boolean;var s:arrayl.20 of char;top,i： integer;ch:char;begintop:=0;i:=l;ch:=ci;while chv> dobeginif (ch='(') or (ch=')') thencase ch of©begin top:=top+l ;stop:=rc end;y：if top>0 then top:=to

11、p-lelse begin doit:=false;exit end;end;i:=i+l;ch:=ci;end;if top=0 then doit:=trueelse doit:=false;end;beginassign(input/in.txtr);reset(input);readln(c);writeln(doit(c);close(input);end.2、背包问题问题：假设有n件质量分配为w|, w2,，wn的物品和一个最多能装载总质量为t的 背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包 所能装载的最大质量,即wii+wi2+.+wi汙t。若

12、能，则背包问题有解,否则无解。算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总 质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件 物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物 品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选， 重复此过程，直至装满背包（有解），或无物品可选（无解）为止。具体实现：设用数组weightri.nl，stackl,n分别存放物品重量和已经装入背包（栈） 的物品序号，ma

13、xw表示背包的最大装载量。每进栈一个物品，就从maxw中减去该物品 的质量，设i为待选物品序号，若maxw-weighti>=0,则该物品可选；若maxw-weighti < 0,则该物品不可选，且若i>n,则需退栈，若此吋栈空，则说明无解。（本题作为课后作业，具体程序请大家自行完成）栈的应用举例1、若已知一个栈的入栈顺序是1, 2, 3,n,其输出序列为pl, p2, p3,pn,若p1是n,则pi是（）oa）i b）n-1 c）n-i+ld）不确定2、以下哪一个不是栈的基本运算（）。a）删除栈顶元素 b）删除栈底的元素c）判断栈是否为空 d）将栈置为空栈3、设栈s和队列q初始状态为空，元素e , e 2，e 3，e 4，c 5，e 6依次通过栈s,一个元素出栈后即进入队列q，若出队的顺序为e 2，e 4，e 3，e 6，e 5，e】，则 栈s的容量至少应该为（）oa） 2 b） 3 c） 4 d） 54、设栈s的初始状态为空，现有5个元素组成的序列1,2,3,4,5,对该序列在s栈上依次进行如下操作（从序列中的1开始，出栈后不在进栈）:进栈，进栈，进栈，出栈，进栈，出栈，进栈，问出栈 的元素序列是:，栈顶指针的值为，栈顶元素为:。5、设栈s和队列q初始状态为空，元素e , e 2，e 3，e 4，e 5，e 6依次通过栈s, 一个元素岀栈后即进入队列q