简介

栈的应用

简介

进栈：多用于计算机，与其相对应的是出栈；进栈、出栈多是按照一定顺序的。

例如：有一个数列（23，45，3，7，3，945）

我们先对其进行进栈操作，则进栈顺序为：23，45，3，7，3，945

我们在对其进行出栈操作，则出栈顺序为：945，3，7，3，45，23

为了方便，我们通常做到：出栈后不再进栈。

进栈出栈就像只有一个口的长筒，先把数据一个个放入筒内，而拿出的时候只有先拿走上边的，才能拿走下边的。

栈的应用

栈的典型应用有算术表达式的检查和背包问题等，实际上，凡属符合后进先出原则的问题，都可以用栈来处理。

1、算术表达式中括号作用域合法性的检查

括号作用域的检查是栈的典型实例。检查一个算术表达式中使用的括号是否正确，应从下面两个方面考虑：

（1）左右括号的数目应该相等；

（2）每一个左括号都一定有一个右括号与之匹配。

算法思想：括号作用域检查的原则是，对表达式从左到右扫描。当遇到左括号时，左括号入栈；当遇到右括号时，首先将栈顶元素弹出栈，再比较弹出元素是否与右括号匹配，若匹配，则操作继续；否则，查出错误，并停止操作。当表达式全部扫描完毕，若栈为空，说明括号作用域嵌套正确，反之，说明表达式有错误。

2、背包问题

问题：假设有n件质量分配为w1，w2，...，wn的物品和一个最多能装载总质量为T的背包，能否从这n件物品中选择若干件物品装入背包，使得被选物品的总质量恰好等于背包所能装载的最大质量，即wi1+wi2+...+wik=T。若能，则背包问题有解，否则无解。

算法思想：首先将n件物品排成一列，依次选取；若装入某件物品后，背包内物品的总质量不超过背包最大装载质量时，则装入（进栈）；否则放弃这件物品的选择，选择下一件物品试探，直至装入的物品总和正好是背包的最大转载质量为止。这时我们称背包装满。

若装入若干物品的背包没有满，而且又无其他物品可以选入背包，说明已装入背包的物品中有不合格者，需从背包中取出最后装入的物品（退栈），然后在未装入的物品中挑选，重复此过程，直至装满背包（有解），或无物品可选（无解）为止。

具体实现：设用数组weight[1..N]，stack[1,N]分别存放物品重量和已经装入背包（栈）的物品序号，MaxW表示背包的最大装载量。每进栈一个物品，就从MaxW中减去该物品的质量,设i为待选物品序号,若MaxW-weight[i]>=0，则该物品可选；若MaxW-weight[i] < 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[i]>=0) and ( i < = n ) then

begin top:=top+1; stack[top]:=i;MaxW=MaxW-weight[i] 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[i];

if top>0 then begin

i:=stack[top]; top:=top-1;MaxW=MaxW+weight[i];

end;

end;

i:=i+1;

end;

end;

return(false) {问题无解}

end;