棧和隊列修改稿

1、棧和隊列 JSOI2010冬令營第4講1一、棧的概念和特性 回顧線性表的特性：除了首尾結(jié)點，所有的結(jié)點都有前驅(qū)和后繼；首結(jié)點只有后繼沒有前驅(qū)，尾結(jié)點只有前驅(qū)沒有后繼；線性表的任何位置都可以進行插入刪除等操作。 現(xiàn)在我們對線性表的操作做一點限制，規(guī)定所有的插入或刪除操作只能在線性表的一端進行，這樣的線性表稱為棧（stack）。 棧是一種特殊的線性表，對它的插入和刪除都限制在表的同一端進行。2一、棧的概念和特性 把可以操作的一端稱為棧頂，不允許操作的一端稱為棧底。在棧頂插入一個元素，稱為進棧，在棧頂刪除一個元素稱為出棧。 棧中元素的進出是按后進先出的原則進行，這是棧結(jié)構的重要特征。（LIFO:La

2、st In First Out） 用一個變量記錄棧頂?shù)奈恢茫ǔ７Q這個變量為棧指針。棧底棧頂a5進棧出棧3練習4.1 設棧S的初始狀態(tài)為空,現(xiàn)有5個元素組成的序列1,2,3,4,5,對該序列在S 棧上依次進行如下操作(從序列中的1開始,出棧后不再進棧):進棧,進棧,進棧,出棧,進棧,出棧,進棧,問：出棧的元素序列是:_,棧頂指針的值為_，棧頂元素為:_。解答：出棧序列為3，4，棧頂指針值為3，棧頂元素為5。12334454練習4.2設棧S初始狀態(tài)為空，元素e 1 ，e 2 ，e 3 ，e 4 ，e 5 ，e 6依次通過棧S，若出棧后的輸出順序為e 2 ，e 4 ，e 3 ，e 6 ，e 5 ，

3、e 1 ，則棧S的容量至少應該為（ ）。 A）2 B）3 C）4 D）5e 1e 2e 2e 3e 4e 4e 3e 5e 6e 6e 5e 15練習4.3 若已知一個棧的入棧順序是1，2，3，n，其輸出序列為P1，P2，P3，Pn，若P1是n，則Pi是( )。 A)i B)n-1 C)n-i+1 D)不確定【分析】1， 2， 3， nP1，P2，P3，Pn已知 p1=n，說明所有的元素進棧以后，才開始出棧。所以p2=n-1，pi=n-i+1。6二、棧的存儲結(jié)構順序棧 type arraytype= array1. n of datatype; var stack:arraytype; top

4、:integer;使用一維數(shù)組stack作為棧的存儲結(jié)構n是棧的容量，即棧中最多可存放的元素top是棧指針，top0，表示?？?，topn，表示棧滿；topn或者top0，則棧溢出top=4n7三、棧的主要運算在使用棧之前，首先需要將棧初始化；往棧頂加入一個新元素，稱進棧（壓棧）；刪除棧頂元素，稱出棧（退棧、彈出）；(4)在使用棧的過程中，還要不斷測試棧是否為空或已滿，稱為測試棧。8三、棧的主要運算（1）棧的初始化操作（棧置空）top：0（2）判斷?？蘸瘮?shù)function sempty(stack:arraytype):boolean;beginsempty:=(top=0);end;（3）判斷

5、棧滿函數(shù)function sfull(stack:arraytype):boolean;beginsfull:=(top=n);end;9三、棧的主要運算（4）進棧的操作過程（壓棧push）procedure push(x:integer); begin if sfull(stack) then writeln(Stack full!) else begin top:=top+1; stacktop:= x end end;10三、棧的主要運算（6）出棧操作過程（pop） function pop:integer; begin if sempty(stack) then begin write

6、ln(Stack empty!); end else begin pop:=stacktop; top:=top-1 end end;11四、棧的應用1、簡單應用：將十進制數(shù)N轉(zhuǎn)換成r進制的數(shù)。 其轉(zhuǎn)換方法利用輾轉(zhuǎn)相除法： 以M=3456，r=8為例轉(zhuǎn)換方法如下： M M / 8（整除） M % 8（求余） 3467 433 3 低 433 54 1 54 6 6 6 0 6 高所以：（3456）10 =（6563）812程序var s:array0.100 of integer; top,x,r,i:integer;begin readln(x,r); for i:=1 to 100 do

7、si:=0; top:=0; while x0 do begin top:=top+1; stop:=x mod r; x:=x div r; end; while top0 do begin write(stop); toP:=top-1; end; readln;end.13begin Readln(m,r); top:=0; While m0 do Begin push(m mod r); m:=m div r; End; While(not sempty(stack) ) do write(pop); end.14四、棧的應用例4. 1：程序員輸入問題 程序員輸入程序，出現(xiàn)差錯時可以采

8、取以下的補救措施：敲錯了一個鍵時，可以補敲一個退格符“”，以表示前一個字符無效；發(fā)現(xiàn)當前一行有錯，可以敲入一個退行符“”，以表示“”與前一個換行符之間的字符全部無效。如：在終端上輸入了這樣兩行字符 PRKJOGRANMLX； VARCONSTN：10；則實際有效的是： PROGRAMLX； CONSTN10；15例4. 1：程序員輸入問題【分析】通過棧操作模擬程序員的輸入過程；逐行處理，處理完一行以后輸出結(jié)果，棧置空；逐字讀入數(shù)據(jù)，對每個讀入的字符進行如下操作：既不是退格符也不是退行符，則將該字符插入棧頂；是退格符，則從棧頂刪去一個字符；是退行符 ，就把字符棧清為空棧。PRKJOGRANMLX

9、；VARCONSTN：10；PROGRAMLX；CONSTN10；16例4. 1：程序員輸入問題【數(shù)據(jù)結(jié)構】type stack=array1.100 of char; var s:stack; top:0.100; ch:char; i:integer;棧棧指針17例4. 1：程序員輸入問題置棧為空procedure setnull(var s:stack); begin top:=0 end;出棧procedure pop(var s:stack); begin if top=0 then writeln(underflow) else top:=top -1; end;18例4. 1：程

10、序員輸入問題入棧procedure push(var s:stack;x:char); begin if top=100 then writeln(overflow) else begin top:=top+1; stop:=x; end; end;19 begin主程序while not eof do begin setnull(s); while not eoln do begin read(ch); case ch of #:pop(s); :setnull(s) else push(s,ch) end; end; for i:=1 to top do write(si); writel

11、n; readln; end ;end.eof函數(shù)，判斷文件是否結(jié)束eoln函數(shù)，判斷一行是否結(jié)束出棧置棧為空入棧輸出20例4.2后綴表達式計算【問題分析】為了便于用程序計算將中綴表達式轉(zhuǎn)換成后綴表達式:35+（6-8/4)7中綴表達式3 56 8 4 / -7+后綴表達式如何計算后綴表達式的值21請你試一試將下列中綴表達式轉(zhuǎn)換成后綴表達式：16-9*（4+3）2*(x+y)/(1-x) (25+8)*(4*(4+7)+7)16943+*-2xy+*1x-/258+447+*7+*22# -16 - 19* 2( 04+ 13+*-5+ 16 9 4 3 +*-5 +6-9*(4+3)+5#輸

12、出隊列運算符優(yōu)先級#-1（0（直接入棧）+ -1* /2）單獨處理23例4.3表達式計算后綴表達式計算【數(shù)據(jù)結(jié)構】 const n=20; type arr=array 1.n of char; arr1=array 1.n of real; var a:arr; s:arr1; i,j,k,top:integer; t,x:real; ch:char;存儲后綴表達式棧24procedure readdata(var a:arr); var i,k:integer; begin assign(input,count.in);reset(input); read(ch);i:=0; while

13、ch# do begin i:=i+1;ai:=ch;read(ch); end; i:=i+1; ai:=#;close(input); end;讀入后綴表達式25function comp(a:arr; var s:arr1):real; var i,k:integer; begin i:=1; top:=0; ch:=ai; while ch# do begin case ch of 0.9:begin x:=0; while (ch ) do begin x:=x*10+ord(ch)-ord(0); i:=i+1; ch:=ai; end; top:=top+1; end;將數(shù)字字符

14、串轉(zhuǎn)換為實數(shù)26 +:begin x:=stop-1+stop;dec(top); end; -:begin x:=stop-1-stop; dec(top); end; *:begin x:=stop-1*stop; dec(top); end; /:begin if stop0 then begin x:=stop-1/stop;dec(top); end else begin writeln(error); close(output); halt; end; end; end ; case stop:=x;i:=i+1;ch:=ai; end ;while comp:=trunc(sto

15、p*1000+0.5)/1000;end;function27begin assign(output,count.out); rewrite(output); for i:=1 to n do si:=0; readdata(a); t:=comp(a,s); writeln(t=,t:0:2); close(output); end.主程序28隊列的基礎知識 到醫(yī)院看病排隊掛號排隊在學校食堂就餐排隊買飯到銀行辦理存款或取款業(yè)務排隊共同的特征嚴格遵守先來后到原則不存在插隊現(xiàn)象 進隊出隊A3 A4 A5 A6 A7 A8 A1A2A10A9隊列 291.1 隊列的概念隊列是限定在表的一端進行插入

16、，在表的另一端進行刪除的線性表。隊尾(rear)：可以插入的一端隊首(front)：可以刪除的一端進隊出隊F（隊首）R（隊尾）A1 A2A3 A4 Ai “先進先出”（FIFOfirst in first out）線性表。 301.2 隊列的基本術語隊首指針f：指向隊首元素初始狀態(tài)：f=0隊尾指針r：指向隊尾元素初始狀態(tài)：r=0出隊：從隊列頭部刪除一個元素進隊：將一個元素插入隊列尾部abcdef12345ii+1FR311.3 隊列的存儲結(jié)構順序存儲 Const m=隊列元素的上限；Type queue=array1.m of elemtype； 隊列的類型定義Var q：queue； 隊列

17、f, r: integer ; 隊尾指針和隊首指針322隊列的基本操作運算（1）初始化隊列 Qini (Q) （2）判斷隊列是否為空 qempty(Q)（3）判斷隊列是否為滿qfull(Q) （4）入隊 QADD(Q,X) （5）出隊 QDel(Q,X)332.1初始化操作過程設定隊列為空procedure Qini (var Q:queue);beginf:=0;r:=0;end;f=r=0342.2 判斷隊列是否為空的函數(shù)若隊列Q為空，則返回值true，否則返回值false。function qempty(Q:queue):Boolean;begin qempty:=(r=f)end;35

18、2.3 判斷隊列是否為滿的函數(shù)若隊列滿，則返回值true，否則返回值false。function qfull(Q:queue):Boolean;beginQfull:=（rm);end;362.4元素進隊過程若隊列Q不滿時，把元素X插入到隊列Q的隊尾，否則返回信息“Overflow”。procedure QADD(var q:queue;x:elemtype); begin if qfull(Q) 上溢then writeln (overflow) else begin r:=r+1； qr:=x； end；end；將元素插入隊尾372.5 元素出隊過程若隊列Q不空，則把隊頭元素刪除并返回值給

19、X，否則輸出信息“Underflow”。procedure Qdel(var q:queue;var x:elemtype); begin if qempty(Q) 下溢 then writeln(Underflow) else begin f:=f+1; x:=qf; end； end;從隊首刪除一個元素38例題4.4 周末舞會假設在周末舞會上，男士們和女士們進入舞廳時，各自排成一隊。跳舞開始時，依次從男隊和女隊的隊頭上各出一人配成舞伴。規(guī)定每個舞曲能有一對跳舞者。若兩隊初始人數(shù)不相同，則較長的那一隊中未配對者等待下一輪舞曲?，F(xiàn)要求寫一個程序，模擬上述舞伴配對問題。39例題4.4 周末舞會輸

20、入3個整數(shù)m，n，k，分別表示男士人數(shù)、女士人數(shù)、幾輪舞曲。例如：24 6輸出各輪舞曲的配對方案。例如：123412240例題4.4 周末舞會設計兩個隊列分別存放男士和女士。每對跳舞的人一旦跳完后就回到隊尾等待下次被選。 m=3 n=2 k=6AB123121122311241例題4.4 周末舞會const max=1000;var a,b:array1.max of integer; m,n,k,i,f1,r1,f2,r2:integer;數(shù)據(jù)結(jié)構a、b分別為兩個隊列f1,r1,f2,r2分別為兩個隊列的首尾指針42例題4.4 周末舞會readln(m，n，k);for i:=1 to m

21、do ai:=i; for i:=1 to n do bi:=i;f1:=0;r1:=m;f2:=0;r2:=n;初始化讀入數(shù)據(jù)建立兩個初始隊列43例題4.4 周末舞會模擬舞會 配對for i:=1 to k do begin f1:=f1+1; f2:=f2+1; writeln(af1:3, ,bf1:3); r1:=r1+1;ar1:=af1; r2:=r2+1;br2:=bf2; end；44const max=10000;var a,b:array1.max of integer; m,n,k,i,f1,r1,f2,r2:integer;beginreadln(m，n，k);for

22、i:=1 to m do ai:=i; for i:=1 to n do bi:=i;f1:=0;r1:=m;f2:=0;r2:=n; for i:=1 to k do begin f1:=f1+1; f2:=f2+1; writeln(af1:3, ,bf1:3); r1:=r1+1;ar1:=af1; r2:=r2+1;br2:=bf2; end；end.452.6隊列的“假溢出”現(xiàn)象當尾指針指向數(shù)組的最后一個元素時，即r=m，下一個元素就不能進隊了。但是數(shù)組的前部因元素出隊空出很多位置閑置無用，這種現(xiàn)象稱為“假溢出”。將m+1的元素放入1，指針繞數(shù)組移動。r:=r+1if rm then

23、 r:=r mod mr:=(r mod m)+1462.7 循環(huán)隊列初始化：f=r=0隊空：f=r隊滿：f=(r+1) mod m進隊：r=(r+1) mod m出隊：f=(f+1) mod m元素個數(shù)：(r-f+m) mod m47圓盤找數(shù)，如圖所示：找出4個相鄰的數(shù)，使其相加之和最大和最小的是哪4個數(shù),給出它們的起始位置。s=ai+a(i+1)mod 20+a(i+2)mod 20) +a(i+3)mod 20)48給你一個長度為N的數(shù)組，一個長為K的滑動的窗體從最左移至最右端，你只能見到窗口的K個數(shù)，每次窗體向右移動一位，你的任務是找出窗口在各位置時的最小數(shù)49輸入格式： 第1行n,k

24、,第2行為長度為n的數(shù)組 輸出格式： 1行，每個位置的最小數(shù)樣例： window.in 8 3 1 3 -1 -3 5 3 6 7 window.out -1 -3 -3 -3 3 3 數(shù)據(jù)范圍： 20%： n=500; 50%: n=100000; 100%: n=1000000; 50例題4.5 迷宮問題編一個程序，找出一條通過迷宮的路徑。這里有蘭色方塊的區(qū)域表示走不通，將一只老鼠從入口處經(jīng)過迷宮到出口處的最短的一條通路打印出來。入口 出口51例題4.5 迷宮問題【問題分析】（1）用二維數(shù)組表示迷宮，1代表不能走入的區(qū)域，0表示可以走通。01110111101010100100111101

25、110011100110000110011052例題4.5 迷宮問題（2）老鼠在迷宮中怎樣探索路徑？有幾個方向可以探索呢？（a）有三個方向可以試探。（b）有五個方向可以試探。（c）有八個方向可以試探。abc53例題4.5 迷宮問題1111111111101110111111010101011010011111101110011111001100011011001101111111111154（x-1,y+1）（x,y）（x-1,y）（x+1,y）（x,y+1）（x+1,y+1）（x-1,y-1）（x,y-1）0111011110101010010011110111001110011000011

26、00110（x+1,y-1）Dx Dy0 11 11 01 -10 -1-1 -1-1 0-1 155例題4.5 迷宮問題（3）用一個隊列記錄探索的路徑。x：當前位置的所在行y：當前位置的所在列pre：前一個位置的記錄在隊列中的序號56隊列操作的一般過程（1）初始化： 指針賦初值，f:=0;r:=1; 第一個結(jié)點進隊，q1.1:=1;q2.1:=1;q3,1:=0;（2）出隊操作，f:=f+1; x:=q1,f;y:=q2,f;（3）依次探索八個方向，如果能走通，則進隊， r:=r+1; q1.r:=x;q2.r:=y;q3,r:=f; （4）重復(2)(3)步，直到目標狀態(tài)出現(xiàn)，輸出結(jié)果，結(jié)

27、束。（5）如果目標狀態(tài)一直不出現(xiàn)，則隊空循環(huán)結(jié)束，無解。57例題4.5 迷宮問題【數(shù)據(jù)結(jié)構】const dx=array1.8 of integer=(0,1,1,1,0,-1,-1,-1); dy=array1.8 of integer=(1,1,0,-1,-1,-1,0,1); max=10;type sqtype=array1.3,1.max*max of integer;var mg:array0.max+1;0.max+1 of integer; sq:sqtype; f,r,i,j,n,m:integer;58Procedure mglj(var sq:sqtype);Begin

28、f:=0;r:=1;sq1,1:=1;sq2,1:=1;sq3,1:=0; While f7 c10:=c10+c7-7;c7:=7;c10+c70) and (c73 c10:=c10+c3-3;c3:=3;c10+c30) and (c33 c7:=c7+c3-3;c3:=3;c7+c30c7c10: c10:=c10+c7;c7:=0;（4）(c70) and (c33)63例題4.6 分油問題【數(shù)據(jù)結(jié)構】Var q:array 1.4,1.100 of integer; f,r,p:integer; c10,c7,c3:integer; 64beginf:=0;r:=1;q1,1:=1

29、0;q2,1:=0;q3,1:=0; q4,1:=0;While fr do Begin inc(f); c10:=q1,f;c7:=q2,f; c3:=q3,f; for p:=1 to 6 do begincase p of 1:f1(c10,c7,c3); 2:f2(c10,c7,c3); 3:f3(c10,c7,c3); 4:f4(c10,c7,c3); 5:f5(c10,c7,c3); 6:f6(c10,c7,c3); End; end;主程序 if f0) and (w77 then begin w10:=w10+w7-7;w7:=7;end else begin w7:=w10+

30、w7;w10:=0;end;if flag(w10,w7,w3) then begininc(r);q1,r:=w10;q2,r:=w7;q3,r:=w3;q4,r:=f; end;if (w10=5) and (w7=5) then print;end;66function flag(w10,w7,w3):boolean;var i:integer; beginflag:=true;for i:=1 to r do if (q1,i=w10) and (q2.i=w7) and (q3.i=w3) then flag:=false; end;67上機練習1begin for i:=1 to

31、100 do si:=0; top:=0; repeat read(x); if x0 then begin top:=top+1; stop:=x; end; until x=0; while top0 do begin write(stop:4); top:=top-1; end; readln; end.1. 讀入若干個整數(shù)，把它們逐個地壓棧，讀入1個0表示結(jié)束（0不要壓棧），再逐個出棧。program zh1; var s:array1.100of integer; top,x,i:integer;68上機練習2.進制轉(zhuǎn)換work1輸入n進制的數(shù)m與要轉(zhuǎn)換成的數(shù)的進制p 。如：輸入一個

32、數(shù)m : ABC.CBA 輸入此數(shù)的進制n : 16 輸入要轉(zhuǎn)換成的數(shù)的進制p : 2 輸出：ABC.ABC(16)=1.11001011101(2)【輸入】 輸入僅三行，第一行為n進制的數(shù)m，第二行為m的進制n，第三行是要轉(zhuǎn)換成的數(shù)的進制p。（小數(shù)部分精度要求5位小數(shù)）【輸出】 n進制的數(shù)m的p進制結(jié)果?！緲永枯斎耄╳ork1.in）ABC.CBA162輸出（work1.out）ABC.ABC(16)=1.11001011101(2)693.括弧匹配檢驗work2假設表達式中允許包含兩種括號：圓括號和方括號，其嵌套的順序隨意，如（ （）或（ ）等為正確的匹配，（）或（ （ ）或 （）均為錯誤的匹配?，F(xiàn)在的問題是，要求檢驗一個給定表達式中的括弧是否正確匹配？輸入一個只包含圓括號和方括號的字符串，判斷字符串中的括號是否匹配，匹配就輸出 “OK” ，不匹配就輸出“Wrong”。輸入一個字符串：（）輸出：OK【輸入】 輸入僅一行字符（字符個數(shù)小于255）【輸出】 匹配就輸出 “OK” ，不匹配就輸出“Wrong”。 【樣例】輸入（work2.in）（）輸出（work2.out）Wrong70上機練習4 家庭問題4、有n個人，編號為1,2,n，另外還知道存在K個關系。一個關系的表達為二