信息學(xué)競賽數(shù)據(jù)結(jié)構(gòu)專項培訓(xùn)教程03棧和隊列

出（bottom 入出…………棧棧和線性表類似，棧也有兩種結(jié)構(gòu)（1．所以，可以采用兩個棧共享空間的方法：假設(shè)在程序中需設(shè)兩個棧，并共維數(shù)組棧1 棧1 棧2 棧2（2．采用鏈 （dispos（pii+1從第i行數(shù)據(jù)計算并存放第i+1行數(shù)據(jù)輸出：O表示老隊員，Y[問題描述有三個分別裝有a水、b水和c水的量筒（c>b>a>0，且ba）,c筒裝滿水，a與b均為空筒，三個筒相互倒水且把水倒往三個筒之外，一個往另一個倒出容量為d[輸入格式 [輸出格式 c（）37109000030707303734333404606431092085§3.3§3.3.1運算優(yōu)先級比加號高，所有a+bb*c。而后綴表達式是運算符在兩個操作數(shù)之后，如ab*A+B*B*(D-C)+40.+(10.-8.)*2.-16./ABC*+40.10.8.-2.*+16.8./ 321B*D-CBDC-E中，E的末尾再加‘#’作為結(jié)束符，將轉(zhuǎn)成后綴表達式，存于字符串A中。(’或欲進棧的運算符優(yōu)先級大于棧頂運算符的優(yōu)先級，則將算符入棧，否則從棧中退出算符送至AB*B**B(*B*B**B(*BD*(-*(C*)++A+#B*(D-CA轉(zhuǎn)換成BDC-*A+3_1所示。 E,A,S:array E中為中綴式，A中為后綴式，S為棧}i,j,t:integer; E[i]<>’#’do E[i]of‘a(chǎn)’..‘z’,‘A’..‘Z’ A[j]:=E[i ‘(’ S[t]:=‘)’ s[t]<>‘(’ A[j]:=s[t ‘+’,‘-’ (t<>0)and(s[t]<>‘(’) dobeginA[j]:=S[t]; s[t]:=E[i‘*’,‘/’ while(t<>0)and(S[t]=‘*’or S[t]=‘/’)dobeginA[j]:=S[t]; end; S[t]:=E[i t< A[j]:=S[t A[j]:=輸入格式：（輸入文件bds.in）輸出格式：（輸入文件bds.out）第二行：該表達式的值輸入：輸出：B*(D-C)+BDC-*AC^A §3.3.2地圖問于四色對地圖，使相鄰的行政區(qū)域不重色。應(yīng)用3色、401的區(qū)域開始逐一進行染色，對每1，2，3，4依次進行試探，并盡可能14色均與相鄰的某區(qū)域發(fā)生重

圖Rji1234567101111102100001031001100410101Rji123456710111110210000103100110041010110510110106110110070000000S1:n)，棧的下標(biāo)值表S63表示063。 mapcolor(varr:adjr; vars:ads);s[ {011色 {i為區(qū)域號，j為染色號} (j<=4)and(i<n) {k指示已染域號 (k<i)and(s[k]*R[i,k]<>j {判斷相鄰區(qū)是否已染色ifk<i {用j+1色繼續(xù)試探} s[i]:=

{與相鄰區(qū)不重色，染色結(jié)果進棧，繼續(xù)對下1色進行試探} j.> i:=i- j:=s[i {變更棧頂區(qū)域的染數(shù)432213422143221342213212321423213423211342321 2 Ri6j＝1234數(shù)“4也不存在除4以外的可染數(shù)則需繼續(xù)退棧變更S[4]:=4，由此S[5]:=3， §3.4.1遞歸形式一般有兩種——直接遞歸和間接遞歸，而棧是實現(xiàn)遞歸的重要2】fac(nn

n×fac(n- fac(n)functionfac(n:integer):integer;ifn=0thenelsefac:=n*fac(n-

fac

fac fac facfac63×fac 2×fac 1×fac fac(0)=這個條件語句就是遞歸邊界。例如，fac函數(shù)體中的“if fac:=1(二)AB，子程序B又調(diào)用子程序AB1．BA的局部對象procedureA;procedureB;A…

{B… {A…2．AB例：procedureB(形式參數(shù)表):forward; {B的完整說明在后}procedurdeA;…B(實參表 {在A中調(diào)用procedureB; {B的首部縮寫，形式參數(shù)表不再列出}… {B…38×8S Si]i8行配置也是合理時，就找到一個解。因此，top=93itop)（S[topi）1top-1iS[j]≠i，1≤j≤top-itop)的兩條對角線上不能有“皇后|S[j-i||j-top|，1≤j≤top-programqueen;total s:array[1..8]of1..8; proceduresearch(top:integer);i,j:p:boolean; ifthenbegin wrin(total,'step:fori:=1to8dowrite(s[i],'');elsebeginfori:=1to8dobegin 1iftop>1then while(j<top)andpdobeginif(s[j]=i)or(abs(s[j]-i)=abs(j-top))thenp:=false;ifpthenbegin top+1 0} 如斐波那契數(shù)列的定義：fnfn-1+fn-2f0=1；f1=2 fib(n:integer)