栈及栈的应用.doc

栈[内容提要]1、栈的概念和特性;2、栈的存储结构;3、栈的几种运算(操作)实现;4、栈的应用举例;[重点难点]1、栈的概念和特性;2、栈的应用场合;3、栈的操作实现;[内容讲授](stack)是一种特殊的线性表。作为一个简单的例子,可以把食堂里冼净的一摞碗看作一个栈。在通常情况下,最先冼净的碗总是放在最底下,后冼净的碗总是摞在最顶上。而在使用时,却是从顶上拿取,也就是说,后冼的先取用,后摞上的先取用。好果我们把冼净的碗“摞上”称为进栈(压栈),把“取用碗”称为出栈(弹出),那么,上例的特点是:后进栈的先出栈。然而,摞起来的碗实际上是一个表,只不过“进栈”和“出栈”都在最顶上进行,或者说,元素的插入和删除是在表的一端进行而已。一般而言,栈是一个线性表,其所有的插入和删除均是限定在表的一端进行,允许插入和删除的一端称栈顶(Top),不允许插入和删除的一端称栈底(Bottom)。若给定一个栈S=(a1,a2,a3,„,an),则称a1为栈底元素,an为栈顶元素,元素ai位于元素ai-1之上。栈中元素按a1,a2,a3,„,an的次序进栈,如果从这个栈中取出所有的元素,则出栈次序为an,an-1,„,a1。也就是说,栈中元素的进出是按后进先出的原则进行,这是栈结构的重要特征。因此栈又称为后进先出(LIFO—LastInFirstOut)表。我们常用一个图来形象地表示栈,其形式如下图:通常,对栈进行的运算主要有以下几种:⑴在使用栈之前,首先需要建立一个空栈,称建栈;⑵往栈顶加入一个新元素,称进栈(压栈);⑶删除栈顶元素,称出栈(退栈、弹出);⑷查看当前的栈顶元素,称读栈;{注意与⑶的区别}⑸在使用栈的过程中,还要不断测试栈是否为空或已满,称为测试栈。,在计算机中用向量作为栈的存储结构最为简单。因此,当用编程语言写程序时,用一维数组来建栈十分方便。例如,设一维数组STACK[1..n]表示一个栈,其中n为栈的容量,即可存放元素的最大个数。栈的第一个元素,或称栈底元素,是存放在STACK[1]处,第二个元素存放在STACK[2]处,第i个元素存放在STACK[i]处。另外,由于栈顶元素经常变动,需要设置一个指针变量top,用来指示栈顶当前位置,栈中没有元素即栈空时,令top=0,当top=n时,表示栈满。如果一个栈已经为空,但用户还继续做出栈(读栈)操作,则会出现栈的“下溢”;如果一个栈已经满了,用户还继续做进栈操作,则会出现栈的“上溢”。两种情况统称为栈的溢出。:(1)建栈这比较简单,只要建立一个一维数组,再把栈顶指针置为零。栈的容量根据具体的应用要求而定。比如:typearraytype=array[1..n]ofinteger;varstack:arraytype;top:integer;再在程序开始时,置top:=0;(2)测试栈测试栈顶指针的值,若top=0,则栈空;若top=n,则栈满。(3)读栈若top=0,则栈空,无栈顶元素可读,出错;若top<>0,则回送栈顶元素的值STACK[top]。(4)进栈(push)将栈顶指针加1后,再把新元素送到栈顶。假设新元素x为整型,栈的最大深度为n,x和n设置为值型参。而栈和栈顶指针要设置成变量型参。procedurepush(varstack:arraytype;vartop:integer;n:integer;x:integer);beginiftop=nthenbeginwriteln(‘Stackfull!’);haltendelsebegintop:=top+1;stack[top]:=xendend;(5)退栈(pop)取得栈顶元素的值后,再把栈顶指针top减1。注意都用变量型参。procedurepop(varstack:arraytype;vartop:integer;varx:integer);beginiftop=0thenbeginwriteln(‘Stackempty!’);haltendelsebeginx:=stack[top];top:=top-1endend;注意:由于栈本身和栈顶指针是密不可分的,所以有时我们把他们定义成一个记录来处理。如:typestack=recordvec:array[1..n]ofinteger;{n为栈可达到的最大深度}top:integer;end;则以上几种运算的实现只要稍做修改即可。procedurepush(vars:stack;x:integer);=nthenbeginwriteln(‘Stackfull!’);:=+1;[]:=xendend