數(shù)據(jù)結構中棧的介紹

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

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

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

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

5、以完全避免使用括號。后綴表達式：運算符放在兩個運算對象之后。所有計算按運算符出現(xiàn)的順序，由左而右進行。例如：3(52)7對應的后綴表達式為3.5.2.7.@現(xiàn)有一后綴表達式，讓你求表達式的值，已知運算符僅限于““““““““四種運算。輸入@表示表達式結束，’.’為操作數(shù)的結束符。如：后綴表達式3.5.2.7.@的值為16。輸入一個后綴表達式，無需判錯，“”作為整除運算。輸出后綴表達式的值，一個整數(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)