關棧

關棧是一個詞語,注音是guan zhan,是稅關所設定用來供未經通關的貨物積存的倉庫,簡單易懂。

棧的概念及運算

棧的定義

棧的運算

為一種抽象數據類型,常用的棧運算有:
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;

相關詞條

相關搜尋

熱門詞條

聯絡我們