栈的基本概念.doc

栈内容提要1、 栈的概念和特性；2、 栈的存储结构；3、 栈的几种运算（操作）实现；4、 栈的应用举例；重点难点1、 栈的概念和特性；2、 栈的应用场合；3、 栈的操作实现；内容讲授 1栈的概念和特性 栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。好果我们把冼净的碗“摞上”称为进栈（压栈），把“取用碗”称为出栈（弹出），那么，上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”都在最顶上进行，或者说，元素的插入和删除是在表的一端进行而已。 一般而言，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。若给定一个栈S=（a1, a2，a3，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。栈中元素按a1, a2，a3，an 的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，a1 。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此栈又称为后进先出(LIFOLast In First Out)表。我们常用一个图来形象地表示栈，其形式如下图： 通常，对栈进行的运算主要有以下几种：在使用栈之前，首先需要建立一个空栈，称建栈；往栈顶加入一个新元素，称进栈（压栈）； 删除栈顶元素，称出栈（退栈、弹出）； 查看当前的栈顶元素，称读栈；注意与的区别在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。2栈的存储结构栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。因此，当用编程语言写程序时，用一维数组来建栈十分方便。例如，设一维数组STACK1.n 表示一个栈，其中n为栈的容量，即可存放元素的最大个数。栈的第一个元素，或称栈底元素，是存放在STACK1处，第二个元素存放在STACK2处，第i个元素存放在STACKi处。另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0，当top=n时，表示栈满。如果一个栈已经为空，但用户还继续做出栈（读栈）操作，则会出现栈的“下溢”；如果一个栈已经满了，用户还继续做进栈操作，则会出现栈的“上溢”。两种情况统称为栈的溢出。3对栈的几种运算的实现方法：（1）建栈 这比较简单，只要建立一个一维数组，再把栈顶指针置为零。栈的容量根据具体的应用要求而定。比如： type arraytype= array1. n of integer;var stack:arraytype; top:integer; 再在程序开始时，置top:=0； （2）测试栈 测试栈顶指针的值，若top=0，则栈空；若top=n，则栈满。（3）读栈 若top=0，则栈空，无栈顶元素可读，出错；若top0，则回送栈顶元素的值STACKtop。（4）进栈（push） 将栈顶指针加1后，再把新元素送到栈顶。假设新元素x为整型，栈的最大深度为n，x和n设置为值型参。而栈和栈顶指针要设置成变量型参。 procedure push(var stack:arraytype;var top:integer;n:integer;x:integer); begin if top=n then begin writeln(Stack full!); halt end else begin top:=top+1; stacktop:= x end end;（5） 退栈(pop) 取得栈顶元素的值后，再把栈顶指针top减1。注意都用变量型参。 procedure pop(var stack:arraytype;var top:integer;var x:integer); begin if top=0 then begin writeln(Stack empty!); halt end else begin x:=stacktop; top:=top-1 endend;注意：由于栈本身和栈顶指针是密不可分的，所以有时我们把他们定义成一个记录来处理。如：type stack=record vec:array1.n of integer; n为栈可达到的最大深度 top:integer; end; 则以上几种运算的实现只要稍做修改即可。 procedure push(var s:stack;x:integer); begin if s.top=n then begin writeln(Stack full!); halt end else begin s.top:=s.top+1; s.vecs.top:= x end end; procedure pop(var s:stack;var x:integer); begin if s.top=0 then begin writeln(Stack empty!); halt end else begin x:=s.vecs.top; s.top:=s.top-1 endend; 出栈有时也可用函数实现，如： function pop(var s:stack):integer; begin if s.top=0 then begin writeln(Stack empty!); halt end else begin pop:=s.vecs.top; s.top:=s.top-1 endend;栈的应用举例1、若已知一个栈的入栈顺序是1，2，3，n，其输出序列为P1，P2，P3，Pn，若P1是n，则Pi是( C )。A)i B)n-1 C)n-i+1 D)不确定2、以下哪一个不是栈的基本运算( B )。A)删除栈顶元素 B)删除栈底的元素 C)判断栈是否为空 D)将栈置为空栈3、设栈S和队列Q初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队的顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为（ B ）。 A）2 B）3 C）4 D）54、设栈S的初始状态为空,现有5个元素组成的序列1,2,3,4,5,对该序列在S 栈上依次进行如下操作(从序列中的1开始,出栈后不在进栈):进栈,进栈,进栈,出栈,进栈,出栈,进栈,问出栈的元素序列是:_,栈顶指针的值为_，栈顶元素为:_。 解答：出栈序列为3，4，栈顶指针值为3，栈顶元素为5。5、设栈S和队列Q初始状态为空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通过栈S，一个元素出栈后即进入队列Q，若出队顺序为e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，e 1 ，则栈S的容量至少应该为_。 解答：为3。6、如下图,有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5共五个车厢。其中每个车厢可以向左行走,也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是3号车厢，请写出所有可能的到达出口的车厢排列总数(不必给出每种排列)。出口 1 2 3 4 5 S解答：9program exp ; 火车进站问题 const n=4 ;type tt=array1.100 of char ;var inp, t : tt ; k , num : integer ;procedure push (out ,s :tt; it,ot,st :integer); var k: integer; c: tt ; beginif it 0 then begin c:=s ; cst+1:=inpit ; push(out , c, it-1,ot,st+1); end; if st0 then begin c:=out ; cot+1:=sst; push(c, s, it,ot+1,st-1); end;if ot=n then begi