pascal-第10講-棧及應(yīng)用

趣味棧及其應(yīng)用山東省濰坊第一中學(xué)高常華2009-8-51952年10月，在抗美援朝上甘嶺戰(zhàn)役中，戰(zhàn)士們正在向彈夾壓子彈雜技演員表演疊羅漢的時(shí)候，最后上去的人總是第一個(gè)下來

洗碗是我們常做的一件家務(wù)活，我們?cè)谙赐氲臅r(shí)候，一般情況下，最先洗干凈的碗總是放在下面，而后洗干凈的碗放在上面；取碗吃飯時(shí)，卻是從最頂上開始拿取。也就是說，后洗的碗先用。洗碗豎直擺放的圖書貨棧裝水的杯子我們喝水的時(shí)候，最先喝到的總是最上層的水，而它們是最后被倒進(jìn)去的。棧在計(jì)算機(jī)中的應(yīng)用棧在計(jì)算機(jī)中的應(yīng)用修改字體插入圖片輸入文本1插入1刪除2刪除1計(jì)算機(jī)操作命令撤消命令Fac(3)----→fac(2)--→fac(1)--→fac(0)=1↑3*fac(2)←2*fac(1)←1*fac(0)求函數(shù)值Fac(n)=n!=n*(n-1)!=n*fac(n-1)(n>0)其中fac(0)=1;例如Fac(3)=3*fac(2)Fac(2)=2*fac(1)Fac(1)=1*fac(0)Fac(0)=1Fac(0)Fac(1)Fac(2)Fac(3)“后進(jìn)先出”(LASTINFIRSTOUT，簡(jiǎn)稱LIFO)是它的特點(diǎn)，其實(shí)這是計(jì)算機(jī)程序設(shè)計(jì)中一個(gè)常見的數(shù)據(jù)結(jié)構(gòu)——棧（STACK），它是一種存儲(chǔ)數(shù)據(jù)的容器，就像裝水的杯子一樣。水杯里的水按照“后進(jìn)先出”的順序被倒進(jìn)倒出，存儲(chǔ)在棧中數(shù)據(jù)也是是按照“后進(jìn)先出”的方式被插入和刪除的。首先我們要搞清楚它本身的屬性和能夠?qū)崿F(xiàn)的基本操作。

棧的屬性？像裝水的杯子一樣的棧？首先應(yīng)該要有一個(gè)容量屬性吧，比如杯子的容量有200ML或500ML等棧有三個(gè)基本屬性：最大容量（最大高度），實(shí)際存儲(chǔ)量（實(shí)際高度），?？罩甘緲?biāo)志。存儲(chǔ)數(shù)據(jù)的容器，像裝水的杯子一樣。。。。。嗯！那它應(yīng)該可以插入和刪除數(shù)據(jù)。對(duì)了，棧用什么來裝這些數(shù)據(jù)啊

杯子滿了就不能再加了。對(duì)了，我們還要做一個(gè)判斷棧滿的操作

往里加水的時(shí)候要判斷棧滿，那往外倒水的時(shí)候就應(yīng)該判斷?？樟恕覀冞€要做一個(gè)判斷棧空的操作我們并不是一拿到杯子就要喝水，有些時(shí)候我們只是想看看杯子里面的水干不干凈，并不一定要往外倒水。這也可以看成是一個(gè)基本操作：獲取棧頂元素的值

棧的特點(diǎn)：后進(jìn)先出棧這種數(shù)據(jù)結(jié)構(gòu)就是有三個(gè)基本屬性和五個(gè)基本操作

三個(gè)基本屬性：最大容量（最大高度），實(shí)際存儲(chǔ)量（實(shí)際高度），?？罩甘緲?biāo)志五個(gè)基本操作:壓入、彈出、判斷棧滿、判斷?？铡@取棧頂元素的值對(duì)于一個(gè)棧，給定一個(gè)輸入項(xiàng)目a,b,c。如果輸入的順序規(guī)定為abc，試寫出全部可能的輸出序列

就是a先入棧，b再入棧，c最后入棧Abc的全排列應(yīng)當(dāng)有6個(gè)，其中cab不合要求CbaBcaBacAcbAbc對(duì)于一個(gè)棧，給定一個(gè)輸入項(xiàng)目a,b,c。如果輸入的順序規(guī)定為abc，試寫出全部可能的輸出序列

就是a先入棧，b再入棧，c最后入棧按照a先入棧，b再入棧，c最后入棧的規(guī)定：CBA彈出-------輸出1--CBABAAa先入棧B再入棧c最后入棧A對(duì)于一個(gè)棧，給定一個(gè)輸入項(xiàng)目a,b,c。如果輸入的順序規(guī)定為abc，試寫出全部可能的輸出序列

就是a先入棧，b再入棧，c最后入棧按照a先入棧，b再入棧，c最后入棧的規(guī)定：CA彈出-------輸出2--bcABAAa入棧B入棧c入棧B出棧AC出棧A對(duì)于一個(gè)棧，給定一個(gè)輸入項(xiàng)目a,b,c。如果輸入的順序規(guī)定為abc，試寫出全部可能的輸出序列

就是a先入棧，b再入棧，c最后入棧按照a先入棧，b再入棧，c最后入棧的規(guī)定：C彈出-------輸出3--bacBAAa入棧B入棧c入棧B出棧

C出棧

A出棧B對(duì)于一個(gè)棧，給定一個(gè)輸入項(xiàng)目a,b,c。如果輸入的順序規(guī)定為abc，試寫出全部可能的輸出序列

就是a先入棧，b再入棧，c最后入棧按照a先入棧，b再入棧，c最后入棧的規(guī)定：彈出-------輸出4--AcbBAa入棧B入棧C出棧AA出棧CBC入棧

B出棧B對(duì)于一個(gè)棧，給定一個(gè)輸入項(xiàng)目a,b,c。如果輸入的順序規(guī)定為abc，試寫出全部可能的輸出序列

就是a先入棧，b再入棧，c最后入棧按照a先入棧，b再入棧，c最后入棧的規(guī)定：

彈出-------輸出5--Abc

Aa入棧A出棧B出棧B入棧CC入棧

C出棧CBA

彈出-------不能輸出6--cabBAAa入棧B入棧出棧C入棧

出棧

出棧不能實(shí)現(xiàn)的情況題目：輸入一個(gè)正整數(shù)n，試分離并輸出其各位數(shù)字。例如，輸入n=1234，則輸出1，2，3，4。（保證n不超出integer的范圍）分離并輸出其各位數(shù)字{代碼1：}{輸入一個(gè)正整數(shù)n，試分離并輸出其各位數(shù)字}PROGRAMSeparate(INPUT,OUTPUT);VARv,n:integer;BEGIN{MAIN}writeln('Inputn:');readln(n);whilen<>0dobeginv:=nmod10;{分離出n的個(gè)位數(shù)字}write(v:2);n:=ndiv10;{去除n的個(gè)位數(shù)字}end;{while}END.輸出順序顛倒!!!{代碼2：}{先判斷出n是個(gè)幾位數(shù)，再?gòu)母呶婚_始分離數(shù)字并輸出}PROGRAMSeparate(INPUT,OUTPUT);VARv,n,h:integer;FUNCTIONHighest(n:integer):integer;{判斷n是個(gè)幾位數(shù)，最大為32767}beginend;{Highest見下一片}BEGIN{MAIN}writeln('Inputn:');readln(n);h:=Highest(n);{判斷n是個(gè)幾位數(shù)}whileh<>0do{分離數(shù)字并將其入棧}beginv:=ndivh;{分離出n的最高位數(shù)字}write(v:2);n:=nmodh;{去除n的最高位數(shù)字}h:=hdiv10;{n位數(shù)降1}end;{while}END.1836Div1000=11836mod1000=8361000div10=100FUNCTIONHighest(n:integer):integer;{判斷n是個(gè)幾位數(shù)，最大為32767}Beginifn>10000thenHighest:=10000elseifn>1000thenHighest:=1000elseifn>100thenHighest:=100elseifn>10thenHighest:=10elseHighest:=1;end;{Highest}{遞歸方法}{輸入一個(gè)正整數(shù)n，試分離并輸出其各位數(shù)字}Procedurefen(n:integer);VARv:integer;BEGINv:=nmod10;{分離出n的個(gè)位數(shù)字}n:=ndiv10;{去除n的個(gè)位數(shù)字}ifn<>0thenfen(n);write(v:1);END;PROGRAMSeparate(INPUT,OUTPUT);VARn:integer;BEGIN{MAIN}readln(n);fen(n);writeln;End.{代碼3：}{利用棧解決分離數(shù)字問題：輸入一個(gè)正整數(shù)n，試分離并輸出其各位數(shù)字}PROGRAMSeparate(INPUT,OUTPUT);CONSTMAXCAPACITY=100;{棧的最大容量}BOTTOM=0;{棧底標(biāo)志}TYPEElemType=integer;{棧內(nèi)元素?cái)?shù)據(jù)類型}Stack=array[1..MAXCAPACITY]ofElemType;{用數(shù)組表示的棧}VARs:Stack;{定義s為棧}top:integer;{棧頂標(biāo)志}v,n:integer;{代碼3：}FUNCTIONStackEmpty(s:Stack;top:integer):boolean;{判斷是否?？諁begin

StackEmpty:=(top=BOTTOM);end;{StackEmpty}

FUNCTIONStackFull(s:Stack;top:integer):boolean;{判斷是否棧滿}begin

StackFull:=(top=MAXCAPACITY);end;{StackFull}{代碼3：}FUNCTIONGetTop(s:Stack;top:integer)

:ElemType;{獲取棧頂元素的值}begin

ifStackEmpty(s,top)then

writeln('underflow')

else

GetTop:=s[top];end;{GetTop}{代碼3：}PROCEDUREPush(vars:Stack;vartop:integer;data:ElemType);{入棧}begin

ifStackFull(s,top)then

writeln('overflow')

else

begin

inc(top);

s[top]:=data;

end;{if}end;{Push}{代碼3：}PROCEDUREPop(vars:Stack;vartop:integer);{出棧}begin

ifStackEmpty(s,top)then

writeln('underflow')

else

dec(top);end;{Pop}BEGIN{MAIN}top:=0;{棧頂初始化}readln(n);whilen<>0do{分離數(shù)字并將其入棧}beginv:=nmod10;{分離出n的個(gè)位數(shù)字}Push(s,top,v);{個(gè)位數(shù)字入棧}n:=ndiv10;{去除n的個(gè)位數(shù)字}end;{while}whilenotStackEmpty(s,top)do{輸出數(shù)字并出棧}beginwrite(GetTop(s,top):2);Pop(s,top);end;{while}END.{判斷字符串中的括號(hào)是否匹配}（（（{[]}）））（（[（]）））{判斷字符串中的括號(hào)是否匹配}PROGRAMTheBracketMatch(INPUT,OUTPUT);CONSTMAXCAPACITY=255;{棧的最大容量}BOTTOM=0;{棧底標(biāo)志}TYPEElemType=char;{棧內(nèi)元素?cái)?shù)據(jù)類型}Stack=array[1..MAXCAPACITY]ofElemType;{用數(shù)組表示的棧}VARcode:string;s:Stack;{定義s為棧}top:integer;{棧頂標(biāo)志}。。。。。。{此處為棧的基本操作函數(shù)，不再重復(fù)列出}FUNCTIONBracketMatch(code:string):BOOLEAN;var

i,len:integer;

flag

:boolean;begin

len:=length(code);{code代碼長(zhǎng)度}

fori:=1tolendo

begin………見后面幻燈片……………end;{for}

BracketMatch:=true;end;{BracketMatch}{判斷字符串中的括號(hào)是否匹配}fori:=1tolendobeginflag:=false;{左右括號(hào)匹配}casecode[i]of'(','[','{','<':Push(s,top,code[i]);{左括號(hào)入棧}')':ifGetTop(s,top)='('then{右括號(hào)出?；驁?bào)錯(cuò)}Pop(s,top)elseflag:=true;{左右括號(hào)不匹配}']':ifGetTop(s,top)='['thenPop(s,top)elseflag:=true;

'}':ifGetTop(s,top)='{'thenPop(s,top)elseflag:=true;'>':ifGetTop(s,top)='<'thenPop(s,top)elseflag:=true;end;{case}

ifflagthen{左右括號(hào)不匹配}beginBracketMatch:=false;exit;end;{if}end;{for}注：此處調(diào)用有關(guān)棧的基本操作調(diào)用了代碼3中的子函數(shù)，不再重復(fù)列出，主函數(shù)如下：BEGIN{MAIN}

top:=0;{棧頂初始化}

writeln('Inputcode:');

readln(code);

ifBracketMatch(code)then

writeln('match!')

else

writeln('mismatch!');END.1、若已知一個(gè)棧的入棧順序是1，2，3，…，n，其輸出序列為P1，P2，P3，…，Pn，若P1是n，則Pi是(C)。

A)iB)n-1C)n-i+1D)不確定練習(xí)題654321數(shù)據(jù)序號(hào)i入棧如圖所示出棧順序是：N=6I=4P1=6Pi=p4=3=6-4+1=n-I+1p1=6I→1234562、以下哪一個(gè)不是棧的基本運(yùn)算(B)。

A)刪除棧頂元素B)刪除棧底的元素

C)判斷棧是否為空D)將棧置為空棧3、設(shè)棧S的初始狀態(tài)為空,現(xiàn)有5個(gè)元素組成的序列{1,2,3,4,5},對(duì)該序列在S棧上依次進(jìn)行如下操作(從序列中的1開始,出棧后不再進(jìn)棧):進(jìn)棧,進(jìn)棧,進(jìn)棧,出棧,進(jìn)棧,出棧,進(jìn)棧,問出棧的元素序列是:_________,棧頂指針的值為______，棧頂元素為:______。

進(jìn)棧進(jìn)棧進(jìn)棧出棧進(jìn)棧出棧進(jìn)棧12132121輸出（出棧序列）34棧頂指針值為3棧頂元素為5。42121521數(shù)制轉(zhuǎn)換十進(jìn)制數(shù)N和其他d進(jìn)制數(shù)的轉(zhuǎn)換是計(jì)算機(jī)實(shí)現(xiàn)計(jì)算的基本問題，其解決方法很多，其中一個(gè)簡(jiǎn)單算法基于下列原理：

N=(Ndivd)×d+Nmodd(其中：div為整除運(yùn)算，mod為求余運(yùn)算)例如：(1348)10=(2504)8，其運(yùn)算過程如動(dòng)畫演示所示：

假設(shè)現(xiàn)要編制一個(gè)滿足下列要求的程序：對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)，打印輸出與其等值的八進(jìn)制數(shù)。算法數(shù)據(jù)N=1348余數(shù)R=nmod8計(jì)算n=ndiv8判斷n=0?否，返回計(jì)算余數(shù)是，倒序輸出余數(shù)r數(shù)制轉(zhuǎn)換方法1：Varn,k:integer;Beginn:=1384;k:=nmod8;write(k:1);n:=ndiv8;untiln=0;Writeln;End順序反了數(shù)制轉(zhuǎn)換方法2：遞歸Proceduretran(n:integer);Vark:integer;Begink:=nmod8;n:=ndiv8;ifn<>0thentran(n);write(k:1);End;Varm:integer;Beginreadln(m);tran(m);End.算法3Programp1(input,output);typestack=recorddata：array[1..100]ofinteger;top：0..100;end;varn:integer;e:integer;s:stack;

{對(duì)于輸入的任意一個(gè)非負(fù)十進(jìn)制整數(shù)打印輸出與其等值的八進(jìn)制數(shù)}beginS.top:=0;{構(gòu)造空棧}Readln(n);{輸入一個(gè)十進(jìn)制數(shù)}while(n>0)beginPush(s,nmod8);{"余數(shù)"入棧}n:=ndiv8;{非零"商"繼續(xù)運(yùn)算}end;while(s.top<>0)){和"求余"所得相逆的順序輸出八進(jìn)制的各位數(shù)}beginPop(S,e);write(e);end;end.后綴表達(dá)式求值

后綴式的運(yùn)算規(guī)則為：運(yùn)算符出現(xiàn)的順序即為表達(dá)式的運(yùn)算順序；每個(gè)運(yùn)算符和在它之前出現(xiàn)且緊靠它的兩個(gè)操作數(shù)構(gòu)成一個(gè)最小表達(dá)式；如：3.5.2.-*7.+@’@’為表達(dá)式的結(jié)束符號(hào)?！?’為操作數(shù)的結(jié)束符號(hào)。運(yùn)算符號(hào)：+、-、*、/【輸入：】后綴表達(dá)式（長(zhǎng)度不超過100）。【輸出：】表達(dá)式的值。【樣例輸入：】3.5.2.-*7.+@【樣例輸出：】16如何按后綴式進(jìn)行運(yùn)算？

可以用兩句話來歸納它的求值規(guī)則："先找運(yùn)算符，后找操作數(shù)。"算法分析： 棧S用來存放原始數(shù)據(jù)、中間結(jié)果和最終結(jié)果。將后綴表達(dá)式以@結(jié)束存入字符數(shù)組，且每個(gè)數(shù)據(jù)后面加一個(gè)空格。掃描中，數(shù)據(jù)入棧，遇到運(yùn)算符，就依次彈出兩個(gè)操作數(shù)進(jìn)行運(yùn)算，運(yùn)算結(jié)果入棧。遇到字符@結(jié)束，棧頂?shù)闹稻褪撬闶降慕Y(jié)果。我們來看個(gè)例子?。總€(gè)數(shù)據(jù)都是個(gè)位數(shù)）programp1(input,output);typestack=recorddata:array[1..100]ofreal;{存放實(shí)型數(shù)}top:0..100;end;vars:stack;ch:char;i:integer;x:real;a:array[1..30]ofchar;functionpop(vars:stack):real;{出棧}beginpop:=s.data[s.top];s.top:=s.top-1;end;procedurepush(vars:stack;x:real);{入棧}begins.top:=s.top+1;s.data[s.top]:=x;end;begin{主程序}i:=0;repeati:=i+1;read(a[i]);{將表達(dá)式存入數(shù)組a}untila[i]='@';s.top:=0;{清空棧}i:=1;{i為a數(shù)組的下標(biāo)}ch:=a[i];whilech<>'@'dobegincasechof'0'..'9':begin{產(chǎn)生完整的數(shù)}x:=0;whilech<>‘.'dobeginx:=x*10+ord(ch)-ord('0');i:=i+1;ch:=a[i];end;end;'+':x:=pop(s)+pop(s);'-':beginx:=pop(s);x:=pop(s)-x;end;'*':x:=pop(s)*pop(s);'/':beginx:=pop(s);x:=pop(s)/x;end;end;push(s,x);{結(jié)果入棧}i:=i+1;ch:=a[i];{繼續(xù)掃描}end;writeln(pop(s));end.八皇后問題解題方法研究1ProcedureTry(I:integer)；{搜索第I行皇后的位置}Varj:integer;beginifI=n+1then輸出方案；forj:=1tondoif皇后能放在第I行第J列的位置thenbegin放置第I個(gè)皇后；對(duì)放置皇后的位置進(jìn)行標(biāo)記；Try（I+1）對(duì)放置皇后的位置釋放標(biāo)記；end;end;遞歸programbahuanghou;vara:array[1..8]ofinteger;b,c,d:array[-7..16]ofinteger;t,i,j,k:integer;beginfork:=-7to16dobeginb[k]:=0;c[k]:=0;d[k]:=0;end;try(1);end.八皇后問題解題方法研究2遞歸procedureprint;begint:=t+1;write(t,'');fork:=1to8dowrite(a[k]);writeln;end;proceduretry(i:integer);varj:integer;beginfo