数据结构中栈的介绍
1.栈的概念
栈（Stack）是一种特殊的表，这种表只在表的一端进行插入和删除操作。允许插入和删除数据元素的这一端称为栈顶；而另一固定的一端称为栈底。不含任何元素的栈称为空栈。
栈的修改是按后进先出的原则进行的。栈又称为后进先出(Last In First Out)表，简称为LIFO 表。
如图1所示：假设一个栈S中的元素为a,a,..,a，则称a为栈底元素，a为栈顶元nn1n-11素。
t
1
图 2 图1
2.栈的存储与操作（称为栈顶指针）由于栈是一个特殊的表，可以用一维数组来实现栈。同时设立指针t 来指示栈顶元素的当前位置。为最早入s[1]将栈底固定在数组的底部，我们用一个
数组s[1..m]来表示一个栈时，即时，表示这个栈为一个空栈。t=0(下标增大的方向)扩展。当
栈的元素，并让栈向数组上方时，表示这个栈已满。当t=m 可以用下列方式定义栈：const
; m=栈表目数的上限type
} stack=array[1..m] of stype; {栈的数据类型var
s:stack;
}
t:integer; {栈顶指针进栈、出栈操作的过程和函数（假设栈元素的数据类型为整型）：）
(1)进栈过程（push时，则给出溢出信息，作出错处理（进栈前首先检查栈是否已满，满则溢≥
①若tm 出；不满则作②）；；（栈指针加１，指向进栈地址）②置t=t+1 为新进栈的元素）；xt)=x ③S(，结束（procedure push(var s:stack; x:integer;var t:integer);
begin
if t=m then writeln('overflow')
else
begin
t:=t+1;s[t]:=x;
end
end;
(2)退栈函数（pop）空则下溢；≤0，则给出下溢信息，作出错处理(退栈前先检查是否已为空栈，①若t 不空则作②)； x）；②x=s(t)，（退栈后的元素赋给 t=t-1，结束（栈指针减１，
指向栈顶）。③function pop(var s:stack;var t:integer):integer;
begin
if t=0 then writeln('underflow')
else
begin
pop:=s[t];t:=t-1;
end
end;
读栈顶元素函数（top）(3)function top(var s:stack; t:integer):integer;
begin
if t=0 then writeln('underflow')
else
top:=s[t];
end;
3栈的应用举例依次入栈，以下出栈序列不可能出现的初始状态为空，元素a,b,c,d,e,f,g【例10-4】.设栈S ）。的是（
C.a,e,d,c,b,f,g B.b,c,a,f,e,g,d A.a,b,c,e,d,f,g
E.g,e,f,d,c,b,a
D.d,c,f,e,b,a,g
，每个元素依次A题解：此题可以采用模拟的方法，依次判断各个选项是否能出现。如出栈，a 进栈，然后b出栈，c进栈后出栈，进栈然后出栈，即得到此序列。再来看B，a,b不能进栈后出栈，gd出栈，可以满足。依此类推，发现只有E，e，f进栈，f，e出栈，d 满足，答案为E。共五个车厢。其中有一个无穷大的的栈S,在栈的右边排列着1,2,3,4,5.如下图,】10-5【例3也可以进入栈S让后面的车厢通过。现已知第一个到达出口的是每个车厢可以向左行走, 号车厢，请
写出所有可能的到达出口的车厢排列总数。 5 4 3 2 1 ←出口←↓S
，4，出栈，此时栈中有元素进栈，然后，题解：首先必是12，3312，未进栈元素有 4我们可以讨论，如下：5的出栈顺序，之前出栈，一定在由于。5我们可以分情况讨论，21四个数字的一个54(1)4先出栈：此时相当于，不经过栈直接到出口。相当于42，，，514 5排在前，1排在排列，24/4=6前，共有种数（种）。4的出栈顺序必连续，有以下三种排列：5和4先出栈：此时(2)5．
5 4 2 1；2 5 4 1；2 1 5 4。
综上所述，总的排列数是9种。
【例1】计算后缀表达式
题目描述
数学上使用的是中缀表达式，在中缀表达式中需要使用括号来改变运算的优先级。
事实上我们可以用后缀表达式或前缀表达式，这两种表达式里就可以完全避免使用括号。
后缀表达式：运算符放在两个运算对象之后。所有计算按运算符出现的顺序，由左而右进行。例如：3*(5-2)+7 对应的后缀表达式为3.5.2.- *7.+@
现有一后缀表达式，让你求表达式的值，已知运算符仅限于??????屜尯四种运算。输入@表示表达式结束，'.'为操作数的结束符。如：后缀表达式3.5.2.- *7.+@的值为16。
输入
一个后缀表达式，无需判错，“/”作为整除运算。
输出
后缀表达式的值，一个整数。
参考程序：
program ex10_6;
const
n=30;
type
stack=array[1..n] of integer;
var
s:stack;
a:string;
t,i,j,k,q:integer;
procedure push(var s:stack; x:integer;var top:integer);
begin
if top=n then writeln('overflow')
else
begin
top:=top+1;s[top]:=x;
end
