該文章為清華大學(xué)數(shù)據(jù)結(jié)構(gòu)與算法設(shè)計(jì)MOOC課程讀書筆記.
1. 棧
1.1 接口
棧接口
LIFO后進(jìn)先出
1.2 棧實(shí)現(xiàn)
-
基于向量
向量實(shí)現(xiàn)stack 基于列表
思路：維持棧頂?shù)闹羔?/p>
1.3 應(yīng)用
stack典型應(yīng)用
1）conversion -> 進(jìn)制轉(zhuǎn)換
問題：給一個(gè)十進(jìn)制非負(fù)整數(shù)勾习，將其轉(zhuǎn)化為??進(jìn)制表示
-
思路：n對(duì)??反復(fù)取模(即求余數(shù))蛤肌，整除弄砍。最終各取模結(jié)構(gòu)逆序輸出則為結(jié)果。
進(jìn)制轉(zhuǎn)換算法 -
實(shí)現(xiàn)
進(jìn)制轉(zhuǎn)換實(shí)現(xiàn)
2）遞歸嵌套 -> 括號(hào)匹配
-
思路
左括號(hào)入棧态坦，右括號(hào)如果棧不為空，出棧棒拂，若為空伞梯，則適配玫氢。
括號(hào)匹配算法
- 若括號(hào)同類型，則可以用計(jì)數(shù)器（本質(zhì)上就是在統(tǒng)計(jì)棧中的元素個(gè)數(shù)）
計(jì)數(shù)器算法- 若括號(hào)不同類型谜诫，則計(jì)數(shù)器算法失效漾峡，棧算法依然有效。
- 擴(kuò)展
- 不一定是括號(hào)喻旷，只要是能夠構(gòu)成匹配對(duì)的符號(hào)都可以使用生逸，比如xml，html的tag*
3) 遞歸嵌套 -> 椙以ぃ混洗stack permutation
- 棽郯溃混洗中：每個(gè)元素被push一次也被pop一次
- 括號(hào)匹配中：左括號(hào)對(duì)應(yīng)了一次push與右括號(hào)對(duì)應(yīng)一次pop
結(jié)論：n個(gè)數(shù)棧混洗與n對(duì)括號(hào)的有效排列是一一對(duì)應(yīng)的
椃嫘常混洗與括號(hào)匹配
4）延遲緩沖 -> 中綴(infix)表達(dá)式計(jì)算
-
思想
關(guān)鍵：對(duì)前綴進(jìn)行緩沖
中綴表達(dá)式計(jì)算思想
關(guān)鍵：當(dāng)遇到的運(yùn)算符比棧頂運(yùn)算符優(yōu)先級(jí)低遍尺，說明棧定的運(yùn)算符可以進(jìn)行計(jì)算了。
這也說明了涮拗，棧中的操作符乾戏，優(yōu)先級(jí)高的排在上，優(yōu)先級(jí)低的排在下多搀。
中綴表達(dá)式Stack實(shí)現(xiàn)思想 實(shí)現(xiàn)
關(guān)鍵：兩個(gè)stack歧蕉，一個(gè)存operator，另一個(gè)存operand
5) 逆波蘭表達(dá)式Reversed Polish Notation
-
特點(diǎn)
通過后綴(postfix)表達(dá)式來避免了括號(hào)康铭，讓運(yùn)算符出現(xiàn)的順序代表運(yùn)算的順序惯退。
RPN -
思路
- 讀到數(shù)入棧
- 讀到運(yùn)算符，數(shù)出棧參運(yùn)算从藤，并將結(jié)果再次入棧
RPN求值
中綴表達(dá)式轉(zhuǎn)換 -> RPN
-
思路
在中綴表達(dá)式算法中略作修改：- 遇到數(shù)字：直接續(xù)接到RPN尾部
- 遇到運(yùn)算符：
- 若比棧頂運(yùn)算符優(yōu)先級(jí)高催跪，將該運(yùn)算符直接連接到RPN尾部
- 若比棧頂運(yùn)算符優(yōu)先級(jí)低，將棧頂運(yùn)算符連接到RPN尾部
RPN轉(zhuǎn)換
2. 隊(duì)列
2.1 隊(duì)列接口
隊(duì)列接口
FIFO
2.2 隊(duì)列實(shí)現(xiàn)
關(guān)鍵：維持頭夷野，尾兩個(gè)指針
