棧：如何實現瀏覽器的前進和後退功能？
- 2019 年 10 月 3 日
- 筆記
棧是什麼？
想像是一摞疊在一起的盤子，在放盤子的時候，需要自下而上一個一個放，取盤子的時候需要自上而下一個一個取。
典型的棧結構：先進者後出，後進者先出，是一種操作受限的數據接口，只能在一端進行插入和刪除操作。
.jpg)
棧主要包含兩個操作，主要是入棧和出棧（插入和讀取並刪除）操作。
棧既可以用數組實現，也可以用鏈表實現，用數組實現的棧稱為順序棧，用鏈表實現的棧稱為鏈式棧。
順序棧代碼：
// 基於數組實現的順序棧
public class ArrayStack {
private String[] items; // 數組
private int count; // 棧中元素個數
private int n; // 棧的大小
// 初始化數組，申請一個大小為 n 的數組空間
public ArrayStack(int n) {
this.items = new String[n];
this.n = n;
this.count = 0;
}
// 入棧操作
public boolean push(String item) {
// 數組空間不夠了，直接返回 false，入棧失敗。
if (count == n) return false;
// 將 item 放到下標為 count 的位置，並且 count 加一
items[count] = item;
++count;
return true;
}
// 出棧操作
public String pop() {
// 棧為空，則直接返回 null
if (count == 0) return null;
// 返回下標為 count-1 的數組元素，並且棧中元素個數 count 減一
String tmp = items[count-1];
–count;
return tmp;
}
}
時間複雜度是O(1)
空間複雜度也是O(1)
支持動態擴容的順序棧：
之前我們實現順序棧使用的底層結構是數組，不支持動態擴容，事實上只要將數組替換成一個可以動態擴容的數組就可以了，比如java中的list
分析一下動態擴容順序棧的時間複雜度和空間複雜度：
出棧的時間複雜度依然是O(1)，因為不涉及到數組擴容與數據搬遷工作
入棧時間複雜度，最好的情況下是O(1)(空間足夠時)，最壞的情況是O(n)(空間不足時，複製和搬遷數據)。
使用攤還分析法來分析時間複雜度 ：
假設棧大小是k，在入棧過程中，當棧容量不足時，下一次入棧操作會觸發一次內存申請操作，以及k個數據的搬遷操作，在之後的k-1次入棧操作，都不需要再重新申請內存以及搬遷數據，將搬遷數據均攤到入棧操作，可以得出入棧操作整體的時間複雜度接近O(1).jpg)
棧在函數中的應用
典型場景—函數調用棧
操作系統給每個線程都分配了一塊獨立的內存空間，這種內存空間被組織成棧這樣的結構，用來存儲函數調用時的臨時變量。沒進入一個函數，就會將臨時變量作為一個棧幀入棧，調用函數完成，返回之後，將函數對應的棧幀出棧。
棧在表達式求值中的使用：
以一個簡單運算為例：3+5*8-6=？
編譯器通過兩個棧來實現，一個 存儲操作數的棧，另一個存儲運算符的棧。從左向右遍歷表達式，遇到數字壓入操作數棧，遇到運算符，與運算符棧的棧頂數據比較。
如過優先級高於運算符棧棧頂元素，就將運算符入棧，如果低於，就將棧頂元素取出，並且從操作數棧中取出兩個元素進行運算，將計算結果壓入操作數棧。
.jpg)
棧在括號匹配中的應用：
用棧保存為匹配的左括號，從左到右一次掃描字符串，當掃描到左括號時，則將其壓入棧中；當掃描到右括號時，從棧頂取出一個左括號，如果能匹配上，則繼續掃描剩下的字符串。如果掃描過程中，遇到不能配對的右括號，或者棧中沒有數據，則說明為非法格式。
如何實現瀏覽器的前進後退功能？
我們使用兩個棧X和Y，我們把首次瀏覽的頁面依次壓如棧X，當點擊後退按鈕時，再依次從棧X中出棧，並將出棧的數據一次放入Y棧。當點擊前進按鈕時，我們依次從棧Y中取出數據，放入棧X中。當棧X中沒有數據時，說明沒有頁面可以繼續後退瀏覽了。當Y棧沒有數據，那就說明沒有頁面可以點擊前進瀏覽了。
思考：
1.我們在講棧的應用時，講到用函數調用棧來保存臨時變量，為什麼函數調用要用“棧”來保存臨時變量呢？用其他數據結構不行嗎？
其實，我們不一定非要用棧來保存臨時變量，只不過如果這個函數調用符合後進先出的特性，用棧這種數據結構來實現，是最順理成章的選擇。
從調用函數進入被調用函數，對於數據來說，變化的是什麼呢？是作用域。所以根本上，只要能保證每進入一個新的函數，都是一個新的作用域就可以。而要實現這個，用棧就非常方便。在進入被調用函數的時候，分配一段棧空間給這個函數的變量，在函數結束的時候，將棧頂複位，正好回到調用函數的作用域內。
2.我們都知道，JVM 內存管理中有個“堆棧”的概念。棧內存用來存儲局部變量和方法調用，堆內存用來存儲 Java 中的對象。那 JVM 裏面的“棧”跟我們這裡說的“棧”是不是一回事呢？如果不是，那它為什麼又叫作“棧”呢？
內存中的堆棧和數據結構堆棧不是一個概念，可以說內存中的堆棧是真實存在的物理區，數據結構中的堆棧是抽象的數據存儲結構。
代碼區：存儲方法體的二進制代碼。高級調度（作業調度）、中級調度（內存調度）、低級調度（進程調度）控制代碼區執行代碼的切換。
靜態數據區：存儲全局變量、靜態變量、常量，常量包括final修飾的常量和String常量。系統自動分配和回收。
棧區：存儲運行方法的形參、局部變量、返回值。由系統自動分配和回收。
棧區：存儲運行方法的形參、局部變量、返回值。由系統自動分配和回收。
