栈是一种特殊的表这种表只在表头进行插入和删除操作。因此，表头对于栈来说具有特殊的意义，称为栈顶。相应地，表尾称为栈底。不含任何元素的栈称为空栈。 栈的逻辑结构：假设一个栈S中的元素为an,an-1,..,a1，则称a1为栈底元素，an为栈顶元 素。栈中的元素按a1 ,a2,..,an-1,an的次序进栈。在任何时候，出栈的元素都是栈顶元素。换句话说，栈的修改是按后进先出的原则进行的，如图1所示。因此，栈又称为后进先出(Last In First Out)表，简称为LIFO表。所以，只要问题满足LIFO原则，就可以使用栈。

栈的概念及运算(栈的运算)

栈的存储与实现(栈的数组实现 具体应用)

栈的应用(表达式的求值 源程序 背包问题 用Pascal实现的参考函数)

栈的概念及运算

栈的定义

栈的运算

为一种抽象数据类型，常用的栈运算有:

inistack(S) 使S成为一个空栈。

getTop(S) 这是一个函数，函数值为S中的栈顶元素。

Pop(S) 从栈S中删除栈顶元素，简称为抛栈。

Push(S,x) 在S的栈顶插入元素x，简称为将元素x入栈。

Empty(S) 这是一个函数。当S为空栈时，函数值为true，否则函数值为false。

栈的存储与实现

栈的数组实现

由于栈是一个特殊的表，我们可以用数组来实现栈。考虑到栈运算的特殊性，我们用一个数组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 * ( 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.

背包问题

　问题：假设有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-weight end;

{第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;