堆疊，一種操作受限的線性表，只允許在一端實作插入和洗掉
注:形狀和操作，非常類似我們一疊累起來的盤子
1.為什么要使用堆疊呢，這種操作受限的線性表，直接使用陣列和鏈表不就行了，操作多而且更靈活？
答:使用功能上，確實能用陣列和鏈表代替堆疊，但是特定的資料結構是對特定的場景的抽象，而且陣列鏈表暴露了太多操作介面，操作上靈活了，使用上就不可控，自然更容易出錯
注:存在有意義，術業有專攻，更加高效低錯，也說明了堆疊是繼承抽象的具體使用，陣列和鏈表是抽象
2.使用場景和實作堆疊
答:只在某資料集合，只在某一端插入洗掉資料，且具有后進先出(逆序)特性，可用堆疊實作，陣列結構的堆疊叫順序堆疊，鏈表結構的堆疊叫鏈式堆疊
3.動態擴容的順序堆疊
答:原理直接來自動態擴容陣列，空間不夠時，申請更大空間，然后copy資料過去，由此可知，入堆疊時間復雜度最好o(1)，最差o(n)因為是要擴容搬遷，但平均是o(1)，可用均攤法論證(大多數情況o(1)極少情況o(n))
注:設滿堆疊k，申請新空間2k，入堆疊操作k+k，平攤o(1)
4.堆疊的操作出堆疊入堆疊
只支持入堆疊出堆疊操作，而且可由陣列鏈表實作，故確實是一個操作受限的線性表結構，最大特點后進先出
注:top指標一直是虛指向，故
arr[top++]=x;
arr[--top]=x;
5.堆疊的經典使用
a.堆疊在函式呼叫中應用
執行按照先輸入后執行，先執行的函式只有等到內部呼叫的其他函式都執行后才能執行(jvm記憶體管理中有堆疊概念，方法堆疊就用來存區域方法和方法中的區域變數)，遞回實作也是，被呼叫函式的區域變數的作用域也是(區域方法呼叫時，被呼叫函式中變數建立，被呼叫函式結束時，復位給呼叫函式)，遞回
b.堆疊在運算式求值中應用
運算子有優先次序，需要逆序，雙堆疊實作
入堆疊規則:資料堆疊直接入堆疊，運算堆疊僅優先級越高才進(可保證優先輸出)
出堆疊規則:僅當運算堆疊不能進入(運算子入堆疊低于等于堆疊內運算子)時，彈出運算堆疊，直到能進入為止；此時數字堆疊兩個一彈出，執行后數字存入數字堆疊
括號處理:可以把右括號看成是優先級最高
c.堆疊在括號匹配中應用
右左入堆疊，右出堆疊，判空
6.瀏覽器前進后退操作實作原理
你要實作在一系列進堆疊出堆疊操作中，一直保存這幾個頁面，就需要對入堆疊x存，出堆疊y存，故需要雙堆疊實作，堆疊x負責后退彈出，堆疊y負責前進彈出
注:
負責頁面前進操作逆序，退出操作逆序，需雙堆疊
堆疊x負責用戶查看入堆疊，退后操作出堆疊；
堆疊y負責x出堆疊的資料入堆疊，前進操作出堆疊
雙向鏈表也可以實作同樣功能
uj5u.com熱心網友回復：
要是貼點理解下代碼就好 了 嘿嘿嘿uj5u.com熱心網友回復：
要是貼點理解下代碼就好 了 嘿嘿嘿轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/31035.html
標籤：語言基礎/算法/系統設計
下一篇：axure rp8