Tauruser

線性結構之典型——堆棧

　　正如前面所說，同樣的邏輯結構，在上面賦予的操作不同，就是不同的數據結構。一個數據結構要同時包含這兩方面的內容。
　　作為線性結構的典型——堆棧，堆棧首先就是一個線性結構，但是對這個線性結構上進行的操作進行一定的限制，就成為了堆棧。堆棧只能在表的一端進行插入和刪除。摘下《The Art of Computer Progrmming》上對典型的三種線性結構的操作描述。

A stack is a linear list for which all insertions and deletions (and usually all accesses) are made at one end of the list.(堆棧）
A queue is a linear list for which all insertions are made at one end of the list; all deletions (and usually all accesses) are made at the other end.（隊列）
A deque ("double-ended queue") is a linear list for which all insertions and deletions (and usually all accesses) are made at the ends of the list.（這種在中文教材里沒看到，我暫且叫它為兩頭蛇 ^ ^）

　　堆棧的存儲結構實現和前面說的一樣，可以用數組方式，目錄表，或鏈表方式實現。具體的實現和操作的實現同樣會在實驗中提到，這里就不再重復。

　　再談一下，堆棧在實現應用當中的使用。
　　實例，對子程序的調用及返回的處理。調用子程序時，將其斷點依次壓入堆棧，返回時再依次彈出。如遞歸的調用。
　　另外一個實例就是實現“＋－×÷”四功能的計算器程序。

這里就先介紹兩個基本概念，以后再另行補上實現程序。

中綴表達式：運算符放在兩個運算對象之間，稱為中綴表達式。計算時先算括號內，再算括號外，多層括號從內層向外層算。無括號或同層括號內由左向右順序執行。
后綴表達式：不再引入括號，運算符放在兩個操作對象后面，稱為后綴表達式。計算時所有運算按運算符出現的順序，嚴格從左向右，每個運算符取其前面兩個操作數，運算后的結果仍為下次的操作數，這樣做與中綴表達式計算嚴格等價，即計算次序和結果完全相同。下面羅列幾個等價的中綴表達式和后綴表達式：
中綴表達式，后綴表達式
A                     A
A+B　　　　AB+
A+B*C           ABC*+
A*(B-C)+D    ABC-*D+
D+A/(B-C)     DABC-/+

That's all for today. THX.