簡介
基本概念
從堆疊的操作特性來看，堆疊是一種操作受限的線性表，只允許在一端插入和洗掉資料，
事實上，從功能上來說，陣列和鏈表完全可以替代堆疊的使用，但是，從某種角度來說，陣列和鏈表暴露太多的操作介面，實作起來比較復雜，也很容易出錯，
因此，當資料集合只涉及在一端插入和洗掉資料，并且滿足先進后出、后進先出的特性，可以首選“堆疊”這種資料結構，
操作
堆疊是允許在同一端進行插入和洗掉操作的特殊線性表，
允許進行插入和洗掉操作的一端稱為堆疊頂，另一端為堆疊底；堆疊底固定，而堆疊頂浮動；堆疊中元素個數為零時稱為空堆疊，插入一般稱為進堆疊，洗掉則稱為出堆疊，
堆疊的實作
實際上，堆疊既可以用陣列實作，也可以用鏈表實作，使用陣列實作的堆疊被稱為順序堆疊，使用鏈表實作的堆疊被稱為鏈式堆疊，
順序堆疊
使用陣列作為堆疊存盤資料的物理存盤結構，需要先申請一個大小為 n 的陣列，
將陣列尾部作為堆疊頂，使用一個變數表示陣列存盤的元素個數，這樣入堆疊、出堆疊的操作都能達到 \(O(1)\) 的時間復雜度，
基于陣列實作的堆疊存在一個限制，即陣列在宣告之后是固定大小的，當堆疊滿的時候，則無法再次往陣列中添加資料，這樣就涉及到對陣列進行動態擴容，當陣列空間不夠的時候，需要重新申請一塊更大的記憶體，將原來陣列中資料統統拷貝過去，
事實上，支持動態擴容的順序堆疊，在實際開發中并不常見，一般使用到順序堆疊這種資料結構的情況，都是一些規模比較小的資料，有時候知道資料的最大規模時也可以避免爆堆疊，
鏈式堆疊
對于資料規模比較大的情況，使用鏈表實作堆疊則會更加方便，這時候，不需要提前申請記憶體空間，而是創建一個哨兵結點指向頭結點，
鏈式堆疊一般會使用頭插法創建鏈表，將頭結點作為堆疊頂，每次入堆疊都當作鏈表在頭結點插入元素，每次出堆疊都當作鏈表洗掉頭結點，這些操作都只需要處理好哨兵結點的指向即可，鏈式堆疊一般都能達到 \(O(1)\) 的時間復雜度，
基于鏈表實作的堆疊不需要像陣列一樣要動態擴容，鏈表是天生支持動態擴容的，
應用場景
堆疊作為一個比較基礎的資料結構，應用場景還是蠻多的，
函式呼叫堆疊
函式呼叫堆疊是一個非常經典的應用場景，
作業系統給每個執行緒分配了一塊獨立的記憶體空間，這塊記憶體被組織成“堆疊”這種結構，用來存盤函式呼叫時的臨時變數，每進入一個函式，就會將臨時變數作為一個堆疊幀入堆疊，當被呼叫函式執行完成，回傳到上層函式之后，再將這個函式對應的堆疊幀出堆疊，
直到函式堆疊為空，則表示最外層的函式已經執行完畢，
逆波蘭運算式
編譯器還會利用堆疊來實作運算式求值，這部分也有非常成熟的四則運算演算法——逆波蘭運算式，
通常的四則運算運算式寫成 (1 + 2) x (3 + 4)，加減乘除等運算子寫在中間，因此也被稱作“中綴運算式”；逆波蘭運算式的寫法是 1 2 + 3 4 + x，運算子被寫在后面，因而也被稱作“后綴運算式”；除此之外，還有波蘭運算式，其寫法是 x + 1 2 + 3 4，也被稱作“前綴運算式”，
如果將運算式畫出一棵語法樹，就能以樹的概念來直觀理解前綴、中綴、后綴的含義，前綴運算式對應樹的前序遍歷，中綴運算式對應樹的中序遍歷，后綴運算式對應樹的后序遍歷，如下圖所示：
首先，需要先將中綴運算式轉換成逆波蘭運算式，涉及到運算元堆疊和運算子堆疊：
-
從左向右遍歷中綴運算式；
-
若讀取的是運算元，將運算元存入到運算元堆疊中；
-
若讀取的是運算子，還需要根據運算子型別進一步判斷：
-
如果是
(運算子，則直接存入運算子堆疊中； -
如果是
)運算子，則輸出運算子堆疊中的運算子到運算元堆疊，直到遇到(運算子，在這里放棄(和)運算子； -
如果是非括號運算子，還需要與運算子堆疊堆疊頂的運算子比較優先級：
- 如果運算子堆疊堆疊頂的運算子是括號，則直接存入運算子堆疊中；
- 如果此運算子比運算子堆疊堆疊頂的運算子優先級更高時，則直接存入運算子堆疊中；
- 如果此運算子比運算子堆疊堆疊頂的運算子優先級更低或相等時，則輸出堆疊頂運算子到運算元堆疊，然后將當前運算子壓入運算子堆疊；
-
-
當運算式讀取完后，將運算子堆疊依次取出到運算元堆疊中，直到運算子堆疊為空，
然后對得到的逆波蘭運算式計算，得到運算式的結果：
- 從左向右遍歷逆波蘭運算式；
- 若讀取的是運算元，將運算元存入堆疊中；
- 若讀取的是運算子，則對堆疊頂的兩個運算元執行該運算，然后將運算結果存入堆疊中；
- 重復上述的步驟 1~3，最終堆疊中即為結果值，
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/423834.html
標籤：其他