什么是棧
棧是一種操作受限的線性表.基本特性是先進后出,后進先出.
棧的實現(xiàn)
椛θ罚可以用數(shù)組來實現(xiàn)叫做順序棧,也可以用鏈表來實現(xiàn)叫做鏈式棧.
棧的復(fù)雜度
出棧和入棧的時間復(fù)雜度為O(1).
棧的空間復(fù)雜度為O(1),棧的空間復(fù)雜度不是指它所需要的存儲空間,而是除了必須存儲空間之外,算法運行所需要的存儲空間.
棧在函數(shù)中的應(yīng)用
操作系統(tǒng)給每個線程分配一塊獨立的內(nèi)存空間,這塊內(nèi)存被組織成棧的結(jié)構(gòu),用來存儲函數(shù)調(diào)用時的臨時變量.每進入一個函數(shù),就會將臨時變量作為一個棧幀入棧,當被調(diào)用函數(shù)執(zhí)行完成,返回之后,將這個函數(shù)對應(yīng)的棧幀出棧.
棧在表達式求值中的應(yīng)用
表達式求值,編譯器是通過兩個棧來實現(xiàn)的。其中一個保存操作數(shù)的棧策菜，另一個是保存運算符的棧婿奔。我們從左向右遍歷表達式，當遇到數(shù)字，我們就直接壓入操作數(shù)棧碗暗；當遇到運算符，就與運算符棧的棧頂元素進行比較梢夯。如果比運算符棧頂元素的優(yōu)先級高言疗，就將當前運算符壓入棧；如果比運算符棧頂元素的優(yōu)先級低或者相同厨疙，從運算符棧中取棧頂運算符洲守，從操作數(shù)棧的棧頂取 2 個操作數(shù)，然后進行計算沾凄，再把計算完的結(jié)果壓入操作數(shù)棧梗醇，繼續(xù)比較。
例:3+6×8-9=?
1. 申請兩個名字為啊a 和 b的棧,a負責存儲數(shù)組,b負責存儲運算符.
2. 3是數(shù)組放入a中
3. +是運算符放入b中
4. 6是數(shù)字放入a中
5. ×是運算符并且優(yōu)先級高于+,所以放入b中
6. 8是數(shù)字放入a中
7. -是運算符且優(yōu)先級低于,所以取出b中的棧頂運算符,取出a中的兩個棧頂數(shù)字8和6,進行運算 8*6=48,將48放入a中
8. 然后繼續(xù)比較-和b中棧頂?shù)膬?yōu)先級,此時b的棧頂運算符為+,和-是平級運算符所以取出b中的棧頂運算符+,取出a中的兩個棧頂數(shù)字48和3,進行運算 48+3=51,將51放入a中.
9. 這時-放入b中
10. 9放入a中
11. 表達式進行最后的運算,51-9=42.
練習:有效括號
