关栈
1 栈的概念及运算
栈的定义：栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。
栈的逻辑结构：假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元 素。栈中的元素按a1 ,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。
栈的运算：为一种抽象数据类型，常用的栈运算有:
运算 含义
inistack(S) 使S成为一个空栈。
getTop(S) 这是一个函数，函数值为S中的栈顶元素。
Pop(S) 从栈S中删除栈顶元素，简称为抛栈。
Push(S,x) 在S的栈顶插入元素x，简称为将元素x入栈。
Empty(S) 这是一个函数。当S为空栈时，函数值为true，否则函数值为false。
2 栈的存储与实现
栈的数组实现：由于栈是一个特殊的表，我们可以用数组来实现栈。考虑到栈运算的特殊性，我们用一个数组elements[1..maxlength]来表示一个栈时，将栈底固定在数组的底部，即elements[1]为最早入栈的元素，并让栈向数组上方(下标增大的方向)扩展。同时，我们用一个游标top来指示当前栈顶元素所在的单元。当top=0时，表示这个栈为一个空栈。在一般情况下，elements中的元素序列elements[top],elements[top-1],..,elements[1]就构成了一个栈。这种结构如图2所示。
图 2
利用上述结构，我们可以形式地定义栈类型TStack如下：
Type
TStack=Record
top:integer;
element:array[1..maxlength] of TElement;
End;
在这种表示法下，栈的5种基本运算可实现如下。
procedure inistack(Var S:TStack);
begin
S.top:=0;
end;
function Empty(var S:Stack):Boolean;
begin
return(S.top=0);
end;
finction Top(var S:TStack):TElement;
begin
if Empty(S) then Error('The stack is empty.')
else return(S.element[S.top]);
end;
procedure Pop(var S:TStack);
begin
if Empty(S) then Error('The stack is empty.')
else dec(S.top); {S.top减1}
end;
procedure Push(var S:TStack；x:TElement;);
begin
if S.top=maxlength then Error('The stack is full.')
else begin
inc(S.top); {S.top增1}
S.elements[S.top]:=x;
end;
end;
以上每种操作的复杂性为O(1)。
在一些问题中，可能需要同时使用多个同类型的栈。为了使每个栈在算法运行过程中不会溢出， 要为每个栈顶置一个较大的栈空间。这样做往往造成空间的浪费。实际上，在算法运行的过程中，各个栈一般不会同时满，很可能有的满而有的空。因此，如果我们让多个栈共享同一个数组，动态地互相调剂，将会提高空间的利用率，并减少发生栈上溢的可能性。 假设我们让程序中的两个栈共享一个数组S[1..n]。利用栈底位置不变的特性，我们可以将两个栈的栈底分别设在数组S的两端，然后各自向中间伸展，如图3所示。这两个S栈的栈顶初值分别为0和n+1。只有当两个栈的栈顶相遇时才可能发生上溢。由于两个栈之间可以余缺互补，因此每个栈实际可用的最大空间往往大于n/2。
3 栈的应用
1.表达式的求值
问题:能否设计算法，编制一个程序，让计算机扫描如下表达式，并将其值打印出来。
# 3 * ( 4 + 8 ) / 2 -5 #
注：给表达式设置#，标志扫描的开始和结束。
提示算法：设两个栈，一个是操作数栈，用来存放操作数，如3、4、8等，另一个是运算符栈，用来存放运算符。
首先将标志“#”进运算符栈的栈底。
然后依次扫描，按照栈的后进先出原则进行：
（1）遇到操作数，进操作数栈；
（2）遇到运算符时，则需将此运算符的优先级与栈顶运算符的优先级比较，
若若高于栈顶元素则进栈，继续扫描下一符号，
否则，将运算符栈的栈顶元素退栈，形成一个操作码Q，同时操作数栈的栈顶元素两次退栈，形成两个操作数a、b，让计算机对操作数与操作码完成一次运算操作，即aQb，并将其运算结果存放在操作数栈中……
模拟计算机处理算术表达式过程。从键盘上输入算术表达式串（只含＋、－、×、÷运算符，充许含括号），输出算术表达式的值。设输入的表达式串是合法的。
附源程序：
program exsj_1;
const
max=100;
var
number:array[0..max] of integer;
symbol:array[1..max] of char;
s,t:string;
i,p,j,code:integer;
procedure push;{算符入栈运算}
begin
inc(p);symbol[p]:=s;
end;
procedure pop;{运算符栈顶元素出栈,并取出操作数栈元素完成相应的运算}
begin
dec(p);
case symbol[p+1] of
'+':inc(number[p],number[p+1]);
'-':dec(number[p],number[p+1]);
'*':number[p]:=number[p]*number[p+1];
'/':number[p]:=number[p] div number[p+1];
end;
end;
function can:boolean;{判断运算符的优先级别,建立标志函数}
begin
can:=true;
if (sin ['+','-']) and (symbol[p]<>'(') then exit;
if (sin ['*','/']) and (symbol[p] in ['*','/']) then exit;
can:=false;
end;
begin
write('String : '); readln(s); s:='('+s+')'; i:=1; p:=0;
while i<=length(s) do
begin
while s='(' do {左括号处理]
begin
push; inc(i);
end;
j:=i;
repeat {取数入操作数栈}
inc(i);
until (s<'0') or (s>'9');
t:=copy(s,j,i-j); val(t,number[p],code);
repeat
if s=')' then {右括号处理}
begin
while symbol[p]<>'(' do pop;
dec(p); number[p]:=number[p+1];
end
else
begin {根据标志函数值作运算符入栈或出栈运算处理}
while can do pop;
push;
end;
inc(i);
until (i>length(s)) or (s[i-1]<>')');
end;
write('Result=',number[0]);
readln;
end.
2.背包问题
问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。
算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。
若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。
具体实现：设用数组weight[1..N]，stack[1,N]分别存放物品重量和已经装入背包（栈）的物品序号，MaxW表示背包的最大装载量。每进栈一个物品，就从MaxW中减去该物品的质量,设i为待选物品序号,若MaxW-weight>=0，则该物品可选；若MaxW-weight< 0，则该物品不可选,且若i>n，则需退栈，若此时栈空，则说明无解。
用Pascal实现的参考函数：
Function knapstack(n,MaxW,weight);
begin
top:=0; i:=1; {i为待选物品序号}
while (MaxW>0) and ( i < = n ) do
begin
if (MaxW-weight>=0) and ( i < = n ) then
begin top:=top+1; stack[top]:=i;MaxW=MaxW-weightend;
{第i件物品装入背包}
if MaxW=0 then return(true)
else begin
if (i=n) and (top>0) then {背包内有不合适物品}
begin {取栈顶物品，恢复MaxW的值}
i:=stack[top]; top:=top-1;MaxW=MaxW+weight;
if top>0 then begin
i:=stack[top]; top:=top-1;MaxW=MaxW+weight;
end;
end;
i:=i+1;
end;
end;
return(false) {问题无解}
end;