數(shù)據(jù)結(jié)構(gòu)中棧的介紹

1、數(shù)據(jù)結(jié)構(gòu)中數(shù)據(jù)結(jié)構(gòu)中棧的介紹棧的介紹1.棧的概念棧（Stack）是一種特殊的表，這種表只在表的一端進(jìn)行插入和刪除操作。允許插入和刪除數(shù)據(jù)元素的這一端稱為棧頂；而另一固定的一端稱為棧底。不含任何元素的棧稱為空棧。棧的修改是按后進(jìn)先出的原則進(jìn)行的。棧又稱為后進(jìn)先出(LastInFirstOut)表，簡(jiǎn)稱為L(zhǎng)IFO表。如圖1所示：假設(shè)一個(gè)棧S中的元素為anan1..a1，則稱a1為棧底元素，an為棧頂元素。圖1圖22.2.棧的存儲(chǔ)與操作由于棧

2、是一個(gè)特殊的表，可以用一維數(shù)組來實(shí)現(xiàn)棧。同時(shí)設(shè)立指針t（稱為棧頂指針）來指示棧頂元素的當(dāng)前位置。我們用一個(gè)數(shù)組s[1..m]來表示一個(gè)棧時(shí)，將棧底固定在數(shù)組的底部，即s[1]為最早入棧的元素，并讓棧向數(shù)組上方(下標(biāo)增大的方向)擴(kuò)展。當(dāng)t=0時(shí)，表示這個(gè)棧為一個(gè)空棧。當(dāng)t=m時(shí)，表示這個(gè)棧已滿?？梢杂孟铝蟹绞蕉x棧：constm=棧表目數(shù)的上限typestack=array[1..m]ofstype棧的數(shù)據(jù)類型vars:stackt:in

3、teger棧頂指針進(jìn)棧、出棧操作的過程和函數(shù)（假設(shè)棧元素的數(shù)據(jù)類型為整型）：(1)進(jìn)棧過程（push）①若t≥m時(shí)，則給出溢出信息，作出錯(cuò)處理（進(jìn)棧前首先檢查棧是否已滿，滿則溢出；不滿則作②）；②置t=t1（棧指針加１，指向進(jìn)棧地址）；③S(t)=x，結(jié)束（x為新進(jìn)棧的元素）；procedurepush(vars:stackx:integervart:integer)beginift=mthenwriteln(overflow)else

4、1t(1)4先出棧：此時(shí)相當(dāng)于4，5不經(jīng)過棧直接到出口。相當(dāng)于1，2，4，5四個(gè)數(shù)字的一個(gè)排列，2排在1前，4排在5前，共有種數(shù)4=6（種）。44A(2)5先出棧：此時(shí)4和5的出棧順序必連續(xù)，有以下三種排列：5421；2541；2154。綜上所述，總的排列數(shù)是9種?！纠?】計(jì)算后綴表達(dá)式計(jì)算后綴表達(dá)式題目描述數(shù)學(xué)上使用的是中綴表達(dá)式，在中綴表達(dá)式中需要使用括號(hào)來改變運(yùn)算的優(yōu)先級(jí)。事實(shí)上我們可以用后綴表達(dá)式或前綴表達(dá)式，這兩種表達(dá)式里就可

5、以完全避免使用括號(hào)。后綴表達(dá)式：運(yùn)算符放在兩個(gè)運(yùn)算對(duì)象之后。所有計(jì)算按運(yùn)算符出現(xiàn)的順序，由左而右進(jìn)行。例如：3(52)7對(duì)應(yīng)的后綴表達(dá)式為3.5.2.7.@現(xiàn)有一后綴表達(dá)式，讓你求表達(dá)式的值，已知運(yùn)算符僅限于““““““““四種運(yùn)算。輸入@表示表達(dá)式結(jié)束，’.’為操作數(shù)的結(jié)束符。如：后綴表達(dá)式3.5.2.7.@的值為16。輸入一個(gè)后綴表達(dá)式，無需判錯(cuò)，“”作為整除運(yùn)算。輸出后綴表達(dá)式的值，一個(gè)整數(shù)。參考程序：programex10_6c

6、onstn=30typestack=array[1..n]ofintegervars:stacka:stringtijkq:integerprocedurepush(vars:stackx:integervartop:integer)beginiftop=nthenwriteln(overflow)elsebegintop:=top1s[top]:=xendendfunctionpop(vars:stackvartop:integer)