棧是限定僅在表尾進行插入和刪除操作的線性表。
隊列是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。

• 棧的定義

  • 棧的定義
    • 棧（stack）是限定僅在表尾進行插入和刪除操作的線性表。
    • 我們把允許插入和刪除的一端稱為棧頂，另一端稱為棧底，不含任何數(shù)據(jù)元素的棧稱為空棧。棧又稱為后進先出的線性表，簡稱LIFO結(jié)構(gòu)。
    • 棧的插入操作，叫作進棧，也稱壓棧、入棧。
    • 棧的刪除操作，叫作出棧，也有的叫做彈棧。
  • 進棧出棧變化形式
    3個元素，就有5種可能的出棧次序，如果元素數(shù)量多，其實出棧的變化將會更多的。

• 棧的抽象數(shù)據(jù)類型

圖片.png

• 棧的順序存儲結(jié)構(gòu)及實現(xiàn)

  • 棧的順序存儲結(jié)構(gòu)
    • 在棧存在一個元素時，棧長度top等于0，因此通常把空棧的判定條件定位top等于-1。
  • 棧的順序存儲結(jié)構(gòu)——進棧操作

圖片.png

• 棧的順序存儲結(jié)構(gòu)——出棧操作

圖片.png

• 兩棧共享空間

數(shù)組有兩個斷點，兩個棧有兩個棧底，分別占用兩個斷點，一個是top-1為空，一個是top為n為空
若棧2是空棧，棧1的top1等于n-1時，就是棧1滿了，若棧1為空棧時，top2等于0時，為棧2滿了，所以他們的關(guān)系top1+1=top2就是滿棧。

• 棧的數(shù)據(jù)插入

圖片.png

圖片.png

• 棧的刪除

圖片.png

• 棧的鏈式存儲結(jié)構(gòu)及實現(xiàn)

  • 棧的鏈式存儲結(jié)構(gòu)
    棧的鏈式存儲結(jié)構(gòu)，簡稱為鏈棧。

圖片.png

• 棧的鏈式存儲結(jié)構(gòu)——進棧操作

圖片.png

圖片.png

圖片.png

• 棧的鏈式存儲結(jié)構(gòu)——出棧操作

圖片.png

圖片.png

• 棧的應用——遞歸

  • 斐波那契數(shù)列實現(xiàn)

    
    
    圖片.png
  • 遞歸定義
    我們把一個直接調(diào)用自己或通過一系列的調(diào)用語句間接地調(diào)用自己的函數(shù)，稱作遞歸函數(shù)。
    迭代使用循環(huán)結(jié)構(gòu)，遞歸使用的是選擇結(jié)構(gòu)。遞歸能使程序的結(jié)構(gòu)更清晰、更簡潔、更容易讓人理解，從而減少讀懂代碼的時間。但是大量的遞歸調(diào)用會建立函數(shù)的副本，會耗費大量的時間和內(nèi)存，迭代則不需要反復調(diào)用函數(shù)和占用額外的內(nèi)存。
    遞歸很適合棧。

• 棧的應用——四則運算表達式求值

  • 后綴（逆波蘭）表示法定義
    一種不需要括號的后綴表達法，我們也把它稱為逆波蘭
    所有的符號都是在要運算數(shù)字后面出現(xiàn)。
  • 后綴表達式計算結(jié)果
    從左到右遍歷表達式的每個數(shù)字和符號遇到是數(shù)字就進棧，遇到是符號，就將處于棧頂兩個數(shù)字出棧，進行運算，運算結(jié)果進棧，一直到最終獲得結(jié)果。
  • 中綴表達式轉(zhuǎn)后綴表達式
    從左到右遍歷中綴表達式的每個數(shù)字和符號，若是數(shù)字就輸出，即成為后綴表達式的一部分；若是符號，則判斷其與棧頂符號的優(yōu)先級，是右括號或優(yōu)先級低于棧頂符號則棧頂元素一次出棧并輸出，并將當前符號進棧，一直到最終輸出后綴表達式為止。

• 隊列的定義

隊列是只允許在一端進行插入操作，而在另一端進行刪除操作的線性表。
隊列是一種先進先出的線性表，簡稱FIFO，允許插入的一端成為隊尾，允許刪除的一端稱為隊頭。

• 循環(huán)隊列

  • 隊列順序存儲的不足
    有很多不足，溢出和出列問題最明顯，如果出列后，其他元素都往前移動一位，那么就麻煩，如果直接出列讓頭往后移動，那么添加的時候會溢出，然而前面卻沒填滿，這種叫假溢出

• 循環(huán)隊列定義
• 所以解決溢出的辦法就是后面滿了，就再從頭開始，也就是頭尾相接的循環(huán)。我們把隊列的這種頭尾相接的順序存儲結(jié)構(gòu)稱為循環(huán)隊列。
• 那么問題又來了，空隊列的時候front=rear，現(xiàn)在隊列滿時，也是front等于rear，那么如何判斷此時的隊列是空還是滿呢？
• 我們通常是保留一個元素空間

• 設(shè)最大尺寸位QueueSize，那么隊列滿的條件是
  (rear+1)%QueueSize == front
  用取余的方式是為了，讓首位相連，最后一個前進一位最后結(jié)果是0.
• 計算隊列的長度的公式是(rear-front+QueueSize)%QueueSize

• 隊列的鏈式存儲結(jié)構(gòu)及實現(xiàn)

隊列的鏈式存儲結(jié)構(gòu)，其實就是線性表的單鏈表，只不過它之只能尾進頭出。我們把它建成為鏈隊列。

• 我們將隊頭指針指向隊列的頭結(jié)點，而隊尾指針指向終端結(jié)點。

  
  

• 空隊列時，front和rear都指向頭結(jié)點

• 隊列的鏈式存儲結(jié)構(gòu)——入隊操作

• 隊列的鏈式存儲結(jié)構(gòu)——出隊操作

圖片.png

• 在可以確定隊列長度最大值的情況下，建議用循環(huán)隊列，如果無法預估隊列的長度時，則用鏈隊列。