棧
棧是限定僅在表尾進(jìn)行插入和操作的線性表；允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧，棧又稱后進(jìn)先出的線性表(即LIFO結(jié)構(gòu))
- 棧是特殊的線性表(限制了這個(gè)線性表的插入和刪除位置)，有前驅(qū)和后繼關(guān)系，線性表的表尾是指棧頂，棧頂是固定的
- 棧的插入(push)操作叫進(jìn)棧(壓棧、入棧)，刪除(pop)操作叫出棧(彈棧)
順序棧(棧的順序存儲(chǔ)結(jié)構(gòu))
- 當(dāng)棧存在n個(gè)元素時(shí)top(代表?xiàng)ｍ斘恢?等于n-1，棧底為0，空棧的判定條件為top等于-1
- 進(jìn)棧：先檢查；棧頂指針+1；將e(要插入的元素)賦給棧頂空間
- 出棧：檢查；將棧頂元素賦值給e；棧頂指針-1；返回e值；進(jìn)出棧的時(shí)間復(fù)雜度都是O(1)
- 存在缺陷：必須事先確定數(shù)組的存儲(chǔ)空間大小
兩棧共享空間
這種數(shù)據(jù)結(jié)構(gòu)通常用在兩個(gè)棧的空間需求有相反關(guān)系的情況，即一個(gè)棧增長(zhǎng)時(shí)另一個(gè)棧在縮短，例如買賣股票；若兩個(gè)棧都增長(zhǎng)，就會(huì)因棧滿而溢出
思路：兩個(gè)相同類型的棧(棧A棧B)，它們是在數(shù)組(長(zhǎng)度為n)的兩端，向中間靠攏；
設(shè)t1和t2是兩個(gè)棧的棧頂指針，t1等于-1時(shí)棧A為空，t2等于n時(shí)棧B為空；
兩個(gè)指針之間相差1時(shí)，即t1+1==t2為棧滿
- push：檢查是否棧滿；加一個(gè)判斷棧號(hào)的參數(shù)，根據(jù)棧號(hào)對(duì)棧進(jìn)行棧頂指針+1或-1并賦值的操作
- pop： 判斷棧號(hào)；檢查；出棧
鏈棧(棧的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))
- 把棧頂放在單鏈表的頭部，頭指針相當(dāng)于棧頂指針，因此一般鏈棧不需要頭結(jié)點(diǎn)；棧頂指針等于NULL時(shí)為空棧
- push：新結(jié)點(diǎn)分配內(nèi)存；把當(dāng)前棧頂元素賦給新結(jié)點(diǎn)的直接后繼；再把棧頂指針指向新結(jié)點(diǎn)；計(jì)數(shù)+1
- pop： 把棧頂結(jié)點(diǎn)賦給臨時(shí)變量t；棧頂指針下移一位；釋放t；計(jì)數(shù)-1；進(jìn)出棧的時(shí)間復(fù)雜度也是O(1)
- 若元素變化不可預(yù)料，最好使用鏈棧；如果是可控的使用順序棧更好
遞歸
直接調(diào)用自己或通過(guò)一系列的調(diào)用語(yǔ)句間接地調(diào)用自己的函數(shù)叫遞歸函數(shù)
- 斐波那契數(shù)列定義：F(0)=0，F(xiàn)(1)=1, F(n)=F(n-1)+F(n-2)（n>=2，n∈N*）
- 每個(gè)遞歸定義必須有一個(gè)退出遞歸的條件，否則會(huì)無(wú)窮遞歸
- 迭代用的循環(huán)結(jié)構(gòu)，遞歸是選擇結(jié)構(gòu)；遞歸使程序更簡(jiǎn)潔，但大量遞歸會(huì)耗費(fèi)額外的時(shí)間和內(nèi)存，視情況選擇
- 編譯器使用棧實(shí)現(xiàn)遞歸，遞歸過(guò)程退回的順序是它前行順序的逆序
- 在前行階段，對(duì)于每一層遞歸，函數(shù)的局部變量、參數(shù)值以及返回地址都被壓入棧中；在退回階段，位于棧頂?shù)木植孔兞?、參?shù)值和返回地址被彈出，用于返回調(diào)用層次中執(zhí)行代碼的其余部分，也就是恢復(fù)了調(diào)用的狀態(tài)
四則運(yùn)算表達(dá)式求值
- 逆波蘭(RPN)表示法：一種不需要括號(hào)的后綴表達(dá)法，讓計(jì)算機(jī)不用括號(hào)就可以對(duì)優(yōu)先級(jí)的運(yùn)算關(guān)系進(jìn)行處理
- 后綴表達(dá)式：所有的符號(hào)都是在要運(yùn)算數(shù)字的后面出現(xiàn)，規(guī)則為：從左到右從遍歷表達(dá)式的每個(gè)數(shù)字和符號(hào)，遇到是數(shù)字就進(jìn)棧，遇到是符號(hào)就將處于棧頂?shù)?strong>兩個(gè)數(shù)字出棧后進(jìn)行運(yùn)算，把結(jié)果進(jìn)棧，直到棧為空
- 平日里所用的標(biāo)準(zhǔn)四則運(yùn)算表達(dá)式也叫做中綴表達(dá)式
- 中綴轉(zhuǎn)后綴：從左向右遍歷，若是數(shù)字就輸出(即成為后綴表達(dá)式的一部分)，若符號(hào)為右括號(hào)或優(yōu)先級(jí)不高于棧頂符號(hào)則棧頂元素依次出棧并輸出(如果優(yōu)先級(jí)高直接進(jìn)棧)，并將當(dāng)前符號(hào)進(jìn)棧，直到最終輸出后綴表達(dá)式為止
- 使計(jì)算機(jī)處理標(biāo)準(zhǔn)表達(dá)式要求：將中綴轉(zhuǎn)化為后綴；將后綴進(jìn)行運(yùn)算(兩者都是用棧來(lái)進(jìn)出運(yùn)算)
隊(duì)列
隊(duì)列是只允許在一端進(jìn)行插入操作，而在另一端進(jìn)行刪除操作的線性表，即先進(jìn)先出(FIFO結(jié)構(gòu))；允許插入的一端稱為隊(duì)尾，允許刪除的一端稱為隊(duì)頭
循環(huán)隊(duì)列(隊(duì)列的順序存儲(chǔ)結(jié)構(gòu))
隊(duì)列順序存儲(chǔ)存在不足：刪除操作的大O為O(n)，性能低；而且會(huì)出現(xiàn)假溢出現(xiàn)象；為了應(yīng)對(duì)假溢出，把隊(duì)列的頭尾相接形成循環(huán)，這種順序存儲(chǔ)結(jié)構(gòu)稱為循環(huán)隊(duì)列
- 隊(duì)列的空與滿的判斷：
- 使用一個(gè)標(biāo)識(shí)變量(布爾型)進(jìn)行識(shí)別
- 隊(duì)滿時(shí)：(rear+1)%len==front(len為隊(duì)列長(zhǎng)；由于rear，front均為所用空間的指針，循環(huán)只是邏輯上的循環(huán)，所以需要求余運(yùn)算)
- 計(jì)算隊(duì)列長(zhǎng)度公式：(尾-頭+表長(zhǎng)) % 表長(zhǎng)
鏈隊(duì)列(隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu))
將隊(duì)頭指針指向鏈隊(duì)列的頭結(jié)點(diǎn)，隊(duì)尾指針指向終端結(jié)點(diǎn)，空隊(duì)列時(shí)front和rear都指向頭結(jié)點(diǎn)
- 入隊(duì)：將新結(jié)點(diǎn)賦給原隊(duì)尾結(jié)點(diǎn)的后繼；隊(duì)尾指針指向新結(jié)點(diǎn)(新結(jié)點(diǎn)后繼為NULL)
- 出隊(duì)：把要?jiǎng)h除的隊(duì)頭結(jié)點(diǎn)的值賦給臨時(shí)變量；更新頭結(jié)點(diǎn)后繼；判斷對(duì)頭隊(duì)尾是否相等；釋放要?jiǎng)h除的結(jié)點(diǎn)
- 與循環(huán)隊(duì)列比較：
- 時(shí)間上：大O都是O(1)，不過(guò)當(dāng)出隊(duì)入隊(duì)頻繁時(shí)，鏈隊(duì)列會(huì)存在一些時(shí)間開(kāi)銷(細(xì)微的)
- 空間上：循環(huán)隊(duì)列必須固定長(zhǎng)度導(dǎo)致有存儲(chǔ)個(gè)數(shù)和空間浪費(fèi)的問(wèn)題；鏈隊(duì)列的指針域雖產(chǎn)生一些空間開(kāi)銷，但靈活
- 小結(jié)：在能確定隊(duì)列最大值的情況用循環(huán)隊(duì)列；無(wú)法預(yù)估時(shí)用鏈隊(duì)列
