基本介紹
- 中文名：關棧
- 性質：棧的定義
- 類型：一種抽象數據類型
- 運算：inistack(S) 使S成為一個空棧
基本概念,數組實現,具體套用,
基本概念
棧的定義
棧的運算
為一種抽象數據類型，常用的棧運算有:
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 #
註：給表達式設定#，標誌掃描的開始和結束。
首先將標誌“#”進運算符棧的棧底。
然後依次掃描，按照棧的後進先出原則進行：
（1）遇到運算元，進運算元棧；
（2）遇到運算符時，則需將此運算符的優先權與棧頂運算符的優先權比較，
若若高於棧頂元素則進棧，繼續掃描下一符號，
源程式
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;
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;
