四、棧的實現及其典型應用

1、棧的定義與實現

棧的定義
?棧是一種特殊的線性表,僅能在線性表的一端進行操作
??棧頂(Top)：允許操作的一端
??棧底(Bottom)：不允許操作的一端
棧的性質:后進先出(LIFO)

棧的一些常用操作
?創建棧
?銷毀棧
?清空棧
?進棧
?出棧
?獲取棧頂元素
?獲取棧的大小
棧的存儲實現
順序存儲實現

鏈式存儲實現

小結
?棧是一種特殊的線性表
?棧只允許在線性表的一端進行操作
?棧通常有兩種實現方式
??順序結構實現，附件中01_SeqStatic文件夾
??鏈式結構實現，附件中02_ListStatic文件夾

2、棧的典型應用一[字符匹配]

?在C語言中有一些符號是成對匹配出現的，利用棧可以實現類似編譯器括號是否匹配的能力。
算法思路：

?從第一個字符開始掃描
?當遇見普通字符時忽略，當遇見左符號時壓入棧中
?當遇見右符號時從棧中彈出棧頂符號
?進行匹配
??匹配成功：繼續讀入下一個字符
??匹配失敗：立即停止，并報錯
?結束：
??成功：所有字符掃描完畢，且棧為空
??失敗：匹配失敗或所有字符掃描完畢但棧非空

算法框架

小結
?當需要檢測成對出現但又互不相鄰的事物時可以使用棧“后進先出”的特性
?棧非常適合于需要“就近匹配”的場合
?代碼實現，附件中02_ListStatic文件夾內

2、棧的典型應用二[小型計算器的實現]

?在數學計算中，人類習慣類似"9 + (3 - 1) * 5"這樣的中綴表達形式，即數字在運算符號的兩邊，而對于計算機而言，更適合處理算式是后綴表達式，即類似"9 3 1 – 5 * +"這樣的形式，因此必然有，從中綴表達式到后綴表達式的過程，并且計算機利用后綴表達式計算的過程，而這些都可以通過棧實現。
中綴表達式轉換為后綴表達式的思路

?遍歷中綴表達式中的數字和符號
??對于數字：直接輸出
??對于符號：
??左括號：進棧
??符號：與棧頂符號進行優先級比較
???棧頂符號優先級低：進棧
???棧頂符號優先級不低：將棧頂符號彈出并輸出，之后進棧
??右括號：將棧頂符號彈出并輸出，直到匹配左括號
?遍歷結束：將棧中的所有符號彈出并輸出

算法框架

后綴表達式計算的思路

?遍歷后綴表達式中的數字和符號
??對于數字：進棧
??對于符號：
???從棧中彈出右操作數
???從棧中彈出左操作數
???根據符號進行運算
???將運算結果壓入棧中
?遍歷結束：棧中的唯一數字為計算結果

算法框架

小結
?中綴表達式是人習慣的表達方式
?后綴表達式是計算機喜歡的表達方式
?通過棧可以方便的將中綴形式變換為后綴形式
?中綴表達式的計算過程類似程序編譯運行的過程
?代碼實現，附件中02_ListStatic文件夾內

算法的實現：附件