Tauruser

線性結(jié)構(gòu)之典型——堆棧

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

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.（隊(duì)列）
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.（這種在中文教材里沒看到，我暫且叫它為兩頭蛇 ^ ^）

　　堆棧的存儲結(jié)構(gòu)實(shí)現(xiàn)和前面說的一樣，可以用數(shù)組方式，目錄表，或鏈表方式實(shí)現(xiàn)。具體的實(shí)現(xiàn)和操作的實(shí)現(xiàn)同樣會在實(shí)驗(yàn)中提到，這里就不再重復(fù)。

　　再談一下，堆棧在實(shí)現(xiàn)應(yīng)用當(dāng)中的使用。
　　實(shí)例，對子程序的調(diào)用及返回的處理。調(diào)用子程序時(shí)，將其斷點(diǎn)依次壓入堆棧，返回時(shí)再依次彈出。如遞歸的調(diào)用。
　　另外一個(gè)實(shí)例就是實(shí)現(xiàn)“＋－×÷”四功能的計(jì)算器程序。

這里就先介紹兩個(gè)基本概念，以后再另行補(bǔ)上實(shí)現(xiàn)程序。

中綴表達(dá)式：運(yùn)算符放在兩個(gè)運(yùn)算對象之間，稱為中綴表達(dá)式。計(jì)算時(shí)先算括號內(nèi)，再算括號外，多層括號從內(nèi)層向外層算。無括號或同層括號內(nèi)由左向右順序執(zhí)行。
后綴表達(dá)式：不再引入括號，運(yùn)算符放在兩個(gè)操作對象后面，稱為后綴表達(dá)式。計(jì)算時(shí)所有運(yùn)算按運(yùn)算符出現(xiàn)的順序，嚴(yán)格從左向右，每個(gè)運(yùn)算符取其前面兩個(gè)操作數(shù)，運(yùn)算后的結(jié)果仍為下次的操作數(shù)，這樣做與中綴表達(dá)式計(jì)算嚴(yán)格等價(jià)，即計(jì)算次序和結(jié)果完全相同。下面羅列幾個(gè)等價(jià)的中綴表達(dá)式和后綴表達(dá)式：
中綴表達(dá)式，后綴表達(dá)式
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.