1.線性表的概念
1.1 什么是線性表
線性表也被稱為順序表，是一個線性序列結(jié)構(gòu)，它是一個含有n≥0個結(jié)點的有限序列，對于其中的結(jié)點，有且僅有一個開始結(jié)點沒有前驅(qū)但有一個后繼結(jié)點，有且僅有一個終端結(jié)點沒有后繼但有一個前驅(qū)結(jié)點，其它的結(jié)點都有且僅有一個前驅(qū)和一個后繼結(jié)點。
1.2 線性表和數(shù)組的關(guān)系
- 1）是兩種不同的數(shù)據(jù)結(jié)構(gòu)，數(shù)組有維度的概念，線性表沒有；而線性表有前驅(qū)節(jié)點和后繼節(jié)點的概念，線性表的數(shù)據(jù)是相互有關(guān)聯(lián)的，而數(shù)組沒有這些。
- 2）線性表可以使用數(shù)組，通常是一維數(shù)組來作為其數(shù)據(jù)的存儲結(jié)構(gòu)。
2.棧的概念
棧是一種特殊的線性表，限定只能在表的一端進(jìn)行插入和刪除操作，俗稱“后進(jìn)先出”（FILO）。
操作數(shù)據(jù)的這端就是表頭，稱為棧頂；相應(yīng)地，表尾稱為棧底。不含任何元素的棧稱為空棧。
3.棧的基本操作
- push：壓?；蛉霔２僮?/li>
- pop：彈棧或出棧操作
- peek：查看棧頂數(shù)據(jù)，而不彈出數(shù)據(jù)，也就是不做出棧操作
4.棧的基本實現(xiàn)
5.棧的應(yīng)用實例
5.1 字符串倒序
5.2 括號（小、中、大）匹配
5.3 計算算術(shù)表達(dá)式
6.后綴表達(dá)式
6.1 什么是后綴表達(dá)式
后綴表達(dá)式，也稱波蘭逆序表達(dá)式，由波蘭數(shù)學(xué)家盧卡西維奇發(fā)明的一種表示表達(dá)式的方法。這種表示方式把運算符寫在運算對象的后面，例如，把a(bǔ)+b寫成ab+，所以也稱為后綴表達(dá)式。
這種表示法的優(yōu)點是根據(jù)運算對象和運算符的出現(xiàn)次序進(jìn)行計算，不需要使用括號，也便于用程序來實現(xiàn)求值。
6.2 如何把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式
PostInfix.java
說明：把中綴表達(dá)式轉(zhuǎn)換成后綴表達(dá)式不用做算術(shù)運算，只是把操作符和操作數(shù)重新按照后綴表達(dá)式的方式進(jìn)行排列而已。
這里有一個核心本質(zhì)——遞歸：
總是這樣遞歸，當(dāng)壓入操作符時，操作符的左操作數(shù)已經(jīng)找到，后面需要找右操作數(shù)。當(dāng)左右操作數(shù)都齊全時，操作符就要從棧中彈出！
所以本質(zhì)在于：找操作符的右操作數(shù)，這個跟找匹配括號問題本質(zhì)是一樣的！
- step1.從左到右順序讀取表達(dá)式中的字符。
- step2.是操作數(shù)，復(fù)制到后綴表達(dá)式字符串。
- step3.是左括號，把字符壓入棧中。
- step4.是右括號，從棧中彈出符號到后綴表達(dá)式，直到遇到左括號，然后把左括號彈出。
- step5.是操作符，如果此時棧頂操作符優(yōu)先級大于或等于此操作符，彈出棧頂操作符到后綴表達(dá)式，直到發(fā)現(xiàn)優(yōu)先級更低的元素位置，把操作符壓入。
- step6.讀到輸入的末尾，將棧元素彈出直到該棧變成空棧，將符號寫到后綴表達(dá)式中。
6.3 計算后綴表達(dá)式求值
- step1.從左到右順序讀取表達(dá)式中的字符
- step2.是操作數(shù)，就壓入棧中
- step3.是操作符，就從棧中取出兩個數(shù)據(jù)進(jìn)行計算，然后把結(jié)果壓入棧中
- step4.直到表達(dá)式計算結(jié)束
