信息学奥赛数据结构教程PASCAL版.doc

《信息学奥赛数据结构教程PASCAL版.doc》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。

1、信息学奥赛数据结构教程PASCAL版第二课　堆栈和队列一、堆栈1．概述　　栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。好果我们把冼净的碗“摞上”称为进栈，把“取用碗”称为出栈，那么，上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”，或者说，元素的插入和删除是在表的一端进行而已。　　一般而言

2、，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。若给定一个栈S=（a1,a2，a3，…，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。栈中元素按a1,a2，a3，…，an的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an,an-1，…，a1。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此栈又称为后进先出(LIFO—LastInFirstOut)表。我

3、们常用一个图来形象地表示栈，其形式如下图：　　通常，对栈进行的运算主要有以下几种：　　（1）往栈顶加入一个新元素，称进栈；　　（2）删除栈顶元素，称退栈；　　（3）查看当前的栈顶元素，称读栈。　　此外，在使用栈之前，首先需要建立一个空栈，称建栈；在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。2．栈的存储结构　　栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。因此，当用编程语言写程序时，用一维数组来建栈十分方便。例如，设一维数组STACK[1..n]表示一个栈，其中n为栈的容量，即可存

4、放元素的最大个数。栈的第一个元素，或称栈底元素，是存放在STACK[1]处，第二个元素存放在STACK[2]处，第i个元素存放在STACK[i]处。另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0，当top=n时，表示栈满。3．对栈的几种运算的实现方法：　（1）建栈　　这比较简单，只要建立一个一维数组，再把栈顶指针置为零。栈的容量根据具体的应用要求而定。　（2）测试栈　　测试栈顶指针的值，若top=0，则栈空；若top=n，则栈满。　（3）读栈

5、　　若top=0，则栈空，无栈顶元素可读，出错；若top<>0，则回送栈顶元素的值STACK[top]。使用一维数组来实现以上三种运算都比较简单，不必为其专门编写过程，只要在需要时，在程序中直接写入适当的语句即可。至于进栈和出栈也不复杂，下面给出它们的算法。　（4）进栈　　将栈顶指针加1后，再把新元素送到栈顶。假设新元素x为整型。procedurepushstack(varstack:arraytype;vartop:integer;n:integer;x:elementtype);begin　iftop=

6、n　thenbeginwiteln(‘Stackfull!’);haltend　elsebegintop:=top+1;stack[top]:=xendend;　（5）退栈　　取得栈顶元素的值后，再把栈顶指针top减1。procedurepopstack(stack:arraytype;vartop:integer;varx:elementtype);begin　iftop=0　thenbeginwriteln(‘Stackempty!’);haltend　elsebeginx:=stack[top];to

7、p:=top-1endend;4．栈的应用举例　　处理表达式是高级语言的编绎中的一个基本问题。它的实现是栈的一个重要应用。通过对处理表达式的讨论，可以帮助我们进一步了解栈的性能。【例5-1】为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为后缀{运算符在后，如X/Y写为XY/}表达式。在这样的表示中可以不用括号即可确定求值的顺序，如：(P+Q)*(R－S)→PQ+RS－*。　　后缀表达式的处理过程如下：扫描后缀表达式，凡遇操作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压

8、栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由＋（加）、－（减）、×（乘）、／（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法