全国青少年信息学奥林匹克联赛
数据结构——堆栈和队列
一、堆栈 1．概述
栈（stack）是一种特殊的线性表。作为一个简单的例子，可以把食堂里冼净的一摞碗看作一个栈。在通常情况下，最先冼净的碗总是放在最底下，后冼净的碗总是摞在最顶上。而在使用时，却是从顶上拿取，也就是说，后冼的先取用，后摞上的先取用。好果我们把冼净的碗“摞上”称为进栈，把“取用碗”称为出栈，那么，上例的特点是：后进栈的先出栈。然而，摞起来的碗实际上是一个表，只不过“进栈”和“出栈”，或者说，元素的插入和删除是在表的一端进行而已。
一般而言，栈是一个线性表，其所有的插入和删除均是限定在表的一端进行，允许插入和删除的一端称栈顶(Top)，不允许插入和删除的一端称栈底(Bottom)。若给定一个栈S=（a1, a2，a3，…，an），则称a1为栈底元素，an为栈顶元素，元素ai位于元素ai-1之上。栈中元素按a1, a2，a3，…，an 的次序进栈，如果从这个栈中取出所有的元素，则出栈次序为an, an-1，…，a1 。也就是说，栈中元素的进出是按后进先出的原则进行，这是栈结构的重要特征。因此栈又称为后进先出(LIFO—Last In First Out)表。我们常用一个图来形象地表示栈，其形式如下图：
通常，对栈进行的运算主要有以下几种： （1） 往栈顶加入一个新元素，称进栈； （2） 删除栈顶元素，称退栈； （3） 查看当前的栈顶元素，称读栈。
此外，在使用栈之前，首先需要建立一个空栈，称建栈；在使用栈的过程中，还要不断测试栈是否为空或已满，称为测试栈。 2．栈的存储结构
栈是一种线性表，在计算机中用向量作为栈的存储结构最为简单。因此，当用编程语言写程序时，用一维数组来建栈十分方便。例如，设一维数组STACK[1..n] 表示一个栈，其中n为栈的容量，即可存放元素的最大个数。栈的第一个元素，或称栈底元素，是存放在STACK[1]处，第二个元素存放在STACK[2]处，第i个元素存放在STACK[i]处。另外，由于栈顶元素经常变动，需要设置一个指针变量top，用来指示栈顶当前位置，栈中没有元素即栈空时，令top=0，当top=n时，表示栈满。 3．对栈的几种运算的实现方法：
（1）建栈
这比较简单，只要建立一个一维数组，再把栈顶指针置为零。栈的容量根据具体的应用要求而定。 （2）测试栈
测试栈顶指针的值，若top=0，则栈空；若top=n，则栈满。 （3）读栈
若top=0，则栈空，无栈顶元素可读，出错；若top<>0，则回送栈顶元素的值STACK[top]。 使用一维数组来实现以上三种运算都比较简单，不必为其专门编写过程，只要在需要时，在程序中直接写入适当的语句即可。至于进栈和出栈也不复杂，下面给出它们的算法。 （4）进栈
将栈顶指针加1后，再把新元素送到栈顶。假设新元素x为整型。 procedure pushstack(var stack:arraytype;var top:integer;n:integer;x:elementtype); begin if top=n
then begin witeln(?Stack full!?); halt end else begin top:=top+1; stack[top]:= x end end;
（5） 退栈
取得栈顶元素的值后，再把栈顶指针top减1。
procedure popstack(stack:arraytype;var top:integer;var x:elementtype); begin if top=0
then begin writeln(?Stack empty!?); halt end else begin x:=stack[top]; top:=top-1 end end;
4．栈的应用举例
处理表达式是高级语言的编绎中的一个基本问题。它的实现是栈的一个重要应用。通过对处理表达式的讨论，可以帮助我们进一步了解栈的性能。
【例5-1】为了便于处理表达式，常常将普通表达式（称为中缀表示）转换为后缀{运算符在后，如X/Y写为XY/}表达式。在这样的表示中可以不用括号即可确定求值的顺序，如：(P+Q)*(R－S) → PQ+RS－*。 后缀表达式的处理过程如下：扫描后缀表达式，凡遇操 作数则将之压进堆栈，遇运算符则从堆栈中弹出两个操作数进行该运算，将运算结果压栈，然后继续扫描，直到后缀表达式被扫描完毕为止，此时栈底元素即为该后缀表达式的值。 输入一个中缀表达式，编程输出其后缀表达式，要求输出的后缀表达式的运算次序与 输入的中缀表达式的运算次序相一致。为简单起见，假设输入的中缀表达式由＋（加）、－（减）、×（乘）、／（除）四个运算符号以及左右圆括号和大写英文字母组成，其中算术运算符遵守先乘除后加减的运算规则。假设输入的中缀表达式长度不超过80个字符，且都是正确的，即没有语法错误，并且凡出现括号其内部一定有表达式，即内部至少有一个运算符号。 以下是一个运行实例，下划线表示输入。 Input a expression:X＋A＊（Y－B）－ Z ／F XAYB－＊＋ZF／－
[算法设计]设置两个栈：操作数栈（ovs）和运算符栈（ops），用来分别存放表达式中的操作数和运算符。开始时操作数栈为空，运算符栈中放入一个特殊的标志运算符号#号，并在表达式的末尾加上一个#号，并规定#号的优先级最低，然后从左向右扫描表达式，凡遇操作数便一律进栈；若遇运算符，则判断其优先级是否大于运算符栈栈顶元素的优先级。若小，则栈顶运算符退栈，并从操作数栈中弹出两个操作数（操作数为后缀表达式）进行后缀变换处理，处理结果进操作数栈，重复刚才的比较，直到栈顶运算符的优先级
大于等于当前运算符的优先级，此时，若当前运算符的优先级大于栈顶运算符的优先级，则当前运算符进栈，继续扫描；若当前运算符的优先级等于栈顶运算符的优先级，则弹出栈顶运算符，继续扫描。扫描完该表达式后运算符栈为空，操作数栈中只有一个元素，该元素就是所要求的后缀表达式。标准程序中的数组f用来存放运算符之间的优先级关系，1表示前面的运算符优先于后面的运算符，-1表示后面的运算符优先于前面的运算符，0表示前面的运算符的优先级与后面的运算符相同，2表示这两个运算符如果在扫描中相遇的话，意味着该表达式是错误的。需要补充的是：左括号的优先级是最高的，而里层的左括号比外层的左括号更优先，右括号的优先级是除#号以外最低的，但左括号和右括号的优先级则是相等的，这样定义的目的是为了消去括号。上述算法还可用于求一个表达式的值和判断一个表达式是否有错等等。下图是对范例表达式的扫描示意图：
[程序清单]
program ex5_1(input,output); const max=100;
op_set:set of char=['+','-','*','/']; letter:set of char=['A'..'Z','a'..'z']; var
expression,result:string;
procedure scan(expression:string); var
i,top1,top2:integer;
ovs:array [1..max] of string[max]; ops:array [1..max] of char;
f:array['#'..'/','#'..'/'] of shortint; {f==first} begin
f['+','+']:=1; f['+','-']:=1; f['+','*']:=-1; f['+','/']:=-1; f['+','(']:=-1; f['+',')']:=1; f['+','#']:=1;
f['-','+']:=1; f['-','-']:=1; f['-','*']:=-1; f['-','/']:=-1; f['-','(']:=-1; f['-',')']:=1; f['-','#']:=1;
f['*','+']:=1; f['*','-']:=1; f['*','*']:=1; f['*','/']:=1; f['*','(']:=-1; f['*',')']:=1; f['*','#']:=1;
f['/','+']:=1; f['/','-']:=1; f['/','*']:=1; f['/','/']:=1; f['/','(']:=-1; f['/',')']:=1; f['/','#']:=1;
f['(','+']:=-1; f['(','-']:=-1; f['(','*']:=-1; f['(','/']:=-1; f['(','(']:=-1; f['(',')']:=0; f['(','#']:=2;
f[')','+']:=2; f[')','-']:=2; f[')','*']:=2; f[')','/']:=2; f[')','(']:=2; f[')',')']:=2; f[')','#']:=2;
f['#','+']:=-1; f['#','-']:=-1; f['#','*']:=-1; f['#','/']:=-1; f['#','(']:=-1; f['#',')']:=2; f['#','#']:=0; expression:=expression+'#'; ops[1]:='#'; top1:=0; top2:=1; for i:=1 to length(expression) do begin
if expression[i] in letter
then begin top1:=top1+1; ovs[top1]:=expression[i] end else begin
while f[ops[top2],expression[i]]=1 do begin
ovs[top1-1]:=ovs[top1-1]+ovs[top1]+ops[top2]; top1:=top1-1; top2:=top2-1 end;
if f[ops[top2],expression[i]]=0 then top2:=top2-1
else begin top2:=top2+1;ops[top2]:=expression[i] end; end end; result:=ovs[1] end; begin
write('Input a expression:'); readln(expression); scan(expression);
writeln('The result is: ',result) end.
二、队列 1、概述
队列(Queue)也是线性表的一种特殊情况，但它与栈不同，其所有的插入均限定在表的一端进行，而所有的删除则限定在表的另一端进行。允许插入的一端称队尾(Rear)，允许删除的一端称队头(Front)。队列的结构特点是先进队的元素先出队。假设有队列Q=（a1, a2，a3，…，an），则队列Q中的元素是按a1, a2，a3，…，an的次序进队，而第一个出队的应该是a1，第二个出队的应该是 a2，只有在ai-1出队以后，ai才可以出队（1≤i≤n）。因此，通常又把队列叫做先进先出（FIFI—First In First Out）表。 关于队列的运算主要包括以下几种：
进队（插入）把一个新元素添加在队列的末尾；
出队（删除）撤去队头元素； 查看（读队头）查看当前队头元素。 此外，还有建立队列和测试队列等。 2、队列的存储结构
同栈一样，在计算机中，可以用向量作为队列的存储结构，并且常借助于编程语言中的一维数组来实现。为了指示队头和队尾的位置，还要再设置两个指针变量：front和rear分别指向队列的头和尾。假设有一个队列，我们用一维数组QUEUE[1..n]来表示，n为队列的最大容量，并约定头指针front总是指在队列中实际头元素的前面一个位置上，而尾指针rear总是指向队尾元素。采用这样的约定后，只有当队列中没有元素即队空时，才会出现front=rear，因此front=rear被用作测试队空的条件。显然，队列的初始状态为front=rear=0。
3、对队列的几种运算的实现方法： （1）建队 数组说明
type arraytype=array[1..n] of elementtype; var Q:arraytype; front:=0; rear:=0; （2）测队空
若front=rear，则队空。 （3）读队头 x:=Q[front+1]; （4）进队
procedure addQ(var Q:arraytype;var rear:integer; n:integer; x:elementtype); begin if rear=n
then begin writeln(?Queue full!?); halt end else begin rear:=rear+1; Q[rear]:=x end end; （5）出队
procedure deleteQ((var Q:arraytype;var front;rear ,n:integer;var x:elementtype); begin if front=rear
then begin writeln(?Queue empty!?); halt end else begin front:=front+1; x:=Q[front]end end;
四、队列应用举例
【例5-2】一个旅行家想驾驶汽车以最少的费用从一个城市到另一个城市（假设出发时油箱是空的）。给定两个城市之间的距离D1、汽车油箱的容量C（以升为单位）、每升汽油能行驶的距离D2、出发点每升汽油价格P和沿途油站数N（N可以为零），油站i离出发点的距离Di、每升汽油价格Pi（i=1，2，……N）。 计算结果四舍五入至小数点后两位。 如果无法到达目的地，则输出“No Solution”。 样例：
