棧、隊列
- 一、棧
- 1.卡特蘭數
- 2.不合法的出棧序列
- 二、隊列
- 1.循環隊列
- 2.輸入輸出受限隊列（四個數1234）
- 三、算法
- 1.棧在括號匹配中的應用
- 2.中綴表達式求值（通過轉化為后綴表達式再后綴表達式求值）
- 3.中綴表達式轉化為后綴表達式
- 4.后綴表達式求值
一、棧
1.卡特蘭數
當n個不同元素依次入棧，一共有C(2n,n)/(n+1)種合法出棧序列。
（證明寫在后面的筆記上了，由于太費時間，就不再細寫電子版了）
2.不合法的出棧序列
- 三個數1，2，3：312序列
- 四個數：1開頭-1423，2開頭-2413，3開頭-3412、3142、3124，4開頭-4123、4132、4213、4231、4312
在此筆者提醒一句：請認真證明上述結論并且找到規律，將4位數不合法出棧序列熟練掌握（達到快速寫出的程度），這個出棧序列沒有遞推規律，但是依然有技巧——比如當某個數出棧時，前面的入棧序列是確定的，而曾經真題也考過類似題目
二、隊列
1.循環隊列
關于循環隊列，一個非常讓人模糊的點在于——尾指針rear和頭指針front初始化的值。你有時候發現rear=front,有時候發現rear=MaxSize-1,front=0。而且有兩年真題分別考察了這個區別。實際上，經過筆者研究，關于循環隊列，一共有兩種不同的入棧方式，進而導致了兩種方式的“初始化”、“隊長”、“隊滿”（默認犧牲一個存儲單元）操作都不相同
- rear先進位，再判滿，然后寫入：這種情況必然導致rear寫入完畢后指向隊尾元素，因此初始化rear在front前，隊長(rear+1-front+MaxSize)%MaxSize，隊滿rear先進位后有(rear+1)%MaxSIze==front
- rear先判滿，再寫入，然后進位：這種情況必然導致rear進位后指向隊尾元素的下一個元素，因此初始化rear=front，隊長(rear-front+MaxSize)%MaxSIze，隊滿有(rear+1)%MaxSize==front（不進位先判滿）
2.輸入輸出受限隊列（四個數1234）
- 不能由輸入受限的雙端隊列得到的序列為：4213,4231（2不能第二個輸出）
- 不能由輸出受限的雙端隊列得到的序列為：4132,4231（3不能夾在12中間）
請自行推導該序列并理解括號后面總結的規律，達到回憶便可推理出來的效果（不要死記硬背）。曾有一年考察了該知識點，且輸入序列為五個數（abcde），如果沒有四個數的二級結論的積累，考場上所耗費的時間可想而知，或者說，這道題就是為記住該二級結論的考生所出的。
三、算法
1.棧在括號匹配中的應用
2.中綴表達式求值（通過轉化為后綴表達式再后綴表達式求值）
3.中綴表達式轉化為后綴表達式
4.后綴表達式求值
此處不再給出具體代碼和推導過程，只給出二級結論以及復習重點（不包含數組和矩陣）。由于上述內容足足耗費了我兩天的精力，目前身心憔悴，最后再粘貼一下紙質版筆記，結束該階段的總結（我總結的筆記含有上述二級結論的真題，這也是為什么我特意強調該部分的原因）
)
