首先慎陵，拋出一個問題，如何使用棧來完成瀏覽器的前進后退功能桃笙？难审？？
如何理解"棧"捌归？肛响？？
關于棧惜索，有一個非常貼切的例子特笋，那就是一摞疊在一起的盤子。我們平時放盤子的時候巾兆，是從下往上一個一個的放猎物，取的時候從上往下一個一個的取，不能從中間任何位置取或是放角塑。后進者先出蔫磨，先進者后出，這就是典型的"棧"的結構圃伶。(如下圖)
棧結構圖
從棧的操作特性上來看堤如，棧是一種操作受限的線性表蒲列，只允許在一端插入或刪除數據。
剛接觸的時候搀罢，相對于數組和鏈表來比蝗岖，感覺棧給我們帶來的只有限制，沒有什么優(yōu)勢榔至。
事實上抵赢，從功能上來說，數組和鏈表是可以代替棧的唧取，但是我們要知道铅鲤，特定的數據結構是對特定的場景的抽象，而數組和鏈表暴露的接口太多兵怯，操作上太靈活彩匕，所以很多時候不好控制，也就容易出現問題媒区。
當某個數據集合只涉及到在一端插入和刪除數據驼仪，并且滿足后進先出，先進后出的特性袜漩，我們就應該首選"棧"這種數據結構
如何實現棧呢绪爸？？宙攻？
在"棧"的定義里奠货，只包含兩個操作，入棧和出棧座掘，也就是從棧頂插入一個數據或從棧頂刪除一個數據递惋。接下來我們用代碼實現以下棧∫缗悖【用數組實現的棧叫順序棧萍虽，用鏈表實現的棧叫鏈式棧】
基于Java實現的順序棧，代碼如下：
// 基于數組實現的順序棧
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;
}
}
了解了棧的基本操作光酣，接下來我們分析一下，棧操作的時間復雜度和空間復雜的吧脉课。
無論是順序棧還是鏈式棧救军，我們存儲都只需要一個大小為n的數據就夠了改览。在入棧和出棧的過程中，只需要兩個臨時變量的存儲空間缤言，所以空間復雜度是O(1)。
注意：這里說到存儲數據需要一個大小為n的數組视事，并不是說空間復雜度就是O(n)胆萧。因為這個n是空間必須的，無法省掉的俐东。所以說跌穗，我們說空間復雜度的時候，是指除了原本數組存儲空間外虏辫，算法運行還需的額外的存儲空間蚌吸。
空間復雜度不難，時間復雜度也不難砌庄。無論是順序棧還是鏈式棧羹唠，棧的入棧和出棧操作都是只涉及棧頂的個別數據的操作，所以時間復雜的是O(1)娄昆。
支持動態(tài)擴容的順序棧
上面的那個是基于數組實現的棧佩微，也就是一個固定大小的棧，也就是說在棧初始化的時候就要指定棧的大小萌焰。當棧滿后哺眯，就無法存儲數據了。盡管是鏈式棧的大小不受限制扒俯，但是存儲next指針奶卓，內存消耗也是較多的。接下來我們學習一下基于數組實現一個支持動態(tài)擴容的棧撼玄。
先回顧一下夺姑，數組是如何動態(tài)擴容的。當數組空間不夠使互纯，就要申請一塊更大的內存空間瑟幕，然后將原來數組里的數組拷貝過去，這樣來完成擴容留潦。
所以只盹，我們要實現一個動態(tài)擴容的棧，只需要底層依賴一個可以動態(tài)擴容的數組即可兔院。當棧滿的時候殖卑，在進行申請一個更大的數組既可以了》宦埽可以參考下圖進行理解：
image.png
其實孵稽，支持動態(tài)擴容的順序棧许起，我們平時是用不到的。但是我們可以通過這個來練習一下復雜度分析菩鲜。
現在我們可以一起分析一下园细，支持動態(tài)擴容的順序棧的入棧出棧操作的復雜度分析。
對于出棧操作來講接校，不會涉及到內存的申請和數據搬移猛频，所以什么情況下的時間復雜度都是O(1)；
對于入棧來講蛛勉，如果棧中有空余空間時鹿寻，那么時間復雜度就是O(1)，如果棧中沒有空余空間時诽凌，需要申請內存空間毡熏，那么就涉及到內存的申請和數據搬移，這樣侣诵，時間復雜度就是O(n)痢法。
也就是說，入棧的最好情況時間復雜度是O(1)窝趣，最壞情況時間復雜度是O(n)疯暑。那平均時間復雜度是多少呢？這就需要用到我們之間文章里面提到過的攤還分析法了哑舒。
為了方便分析妇拯，我們先做一些假設和定義
- 假設棧空間不足的時候洗鸵，我們需要重新申請原來大小兩倍的數組大小
- 假設我們只考慮入棧不考慮出棧
- 定義不涉及到內存搬移的入棧操作為simple-push操作越锈，時間復雜度為O(1)
如果，當前棧的大小為k膘滨，并且已滿甘凭，當有新的數據需要入棧的時候，就需要申請兩倍大小的內存火邓，并且做k個數據的搬移操作丹弱，然后在入棧。但是接下來的k-1次入棧操作铲咨，就不需要在此申請內存和數據搬移了躲胳，所以這k-1次入參操作都只需要一個simple-push操作就可以完成。
可以根據下圖進行理解纤勒。
image.png
可以看出這k次入棧操作坯苹，涉及到了k個數據的搬移操作和k次simple-single操作。將k個數據搬移的操作平均分到k次simple-push操作上摇天，那沒個數據入棧只需要一次數據搬移和一次simple-push操作粹湃。以此類推恐仑，入棧操作的時間復雜度就是O(1)
通過這個例子的實戰(zhàn)分析,也印證了前面文章提到的,均攤時間復雜度-般都等 于最好情況時間復雜度。因為在大部分情況下,入棧操作的時間復雜度O都是O(1),只有在個別時刻才會退化為O(n) ,所以把耗時多的入棧操作的時間均攤到其他入棧操作上,平均情況下的耗時就接近O(1)
棧的實際應用
1.棧在函數調用中的應用
棧作為比較基礎的數據結構为鳄，應用場景還是很多的裳仆。比較經典的場景就是函數調用棧
我們知道，操作系統(tǒng)給每個線程分配了一塊獨立的內存空間孤钦，這塊內存被組織成"棧"的結構鉴逞，用來存儲調用時的臨時變量。每進入一個函數司训，就會將臨時變量作為一個棧幀入棧，當被調用函數執(zhí)行完成液南，返回之后壳猜，將這個函數對應的棧幀出棧。為了更好的理解滑凉，可以看一下下面的這段代碼：
int main() {
int a = 1;
int ret = 0;
int res = 0;
ret = add(3, 5);
res = a + ret;
printf("%d", res);
reuturn 0;
}
int add(int x, int y) {
int sum = 0;
sum = x + y;
return sum;
}
從代碼我們可以看出统扳，main()函數調用了add()函數，獲取計算結果畅姊，并與臨時變量a相加咒钟，最后打印res的值。為了更清晰的看出這個過程中函數棧里入棧若未、出棧的操作朱嘴，可以參考下圖，分析理解粗合。圖中顯示的是萍嬉，在執(zhí)行到add()函數時，函數調用棧的情況隙疚。
image.png
2.棧在表達式求值中的應用
我們一起了解一下壤追，編譯器如何用棧來實現表達式求值的。
我們簡單舉例學習供屉，就說一下最簡單的包含加減乘除的四則運算行冰，比如3+5*8-6。對于這個四則運算伶丐，我們是很快就會算出來了悼做，但是對于計算機來說，理解這個表達式就是很難得一件事情了撵割。
實際上贿堰，計算機就是通過兩個棧來實現的。一個操作數棧啡彬，一個運算符棧羹与。操作數棧就是用來存儲操作數的故硅，運算符棧就是用來存儲運算符的。
具體流程：
首先纵搁，我們從左到右遍歷表達式吃衅，遇到數字就壓入操作數棧，遇到運算符就與運算符棧頂元素進行比較腾誉。如果比運算符棧頂元素優(yōu)先級高徘层，就將當前運算符壓入棧中；如果比運算符棧頂元素優(yōu)先級低或者相同利职，從運算符棧中取出棧頂運算符趣效，從操作數棧的棧頂取兩個操作數，然后進行計算猪贪，然后再把計算后的結果壓入操作數棧中跷敬，繼續(xù)比較。
下面是例子中表達式的計算過程圖热押，可以參考西傀，便于理解
3.棧在括號匹配中的應用
除了用棧來實現表達式求值,我們還可以借助棧來檢查表達式中的括號是否匹配。
我們同樣簡化-下背景桶癣。我們假設表達式中只包含三種括號,圓括號0拥褂、方括號D和花括號}，并且它們可以任意嵌套牙寞。比如饺鹃，{[]]或[{0(D)]等都為臺法格式,而{D0]或[(0]為不合法的格式。那我現在給你一個包含三種括號的表達式字符串,如何檢查它是否臺法呢?
這里也可以用棧來解決间雀。我們用棧來保存未匹配的左括號,從左到右依次掃描字符串尤慰。當掃描到左括號時,則將其壓入棧中;當掃描到右括號時,從棧頂取出一個左括號。如果能夠匹配,比如“(”跟“”匹配雷蹂，"[”跟“”匹配伟端，”{”跟“”匹配，則繼續(xù)掃描剩下的字符串匪煌。如果掃描的過程中,遇到不能對的右括號,或者棧中沒有數據,則說明為非法格式责蝠。
當所有的括號都掃描完成之后,如果棧為空,則說明字符串為合法格式:否則,說明有未匹配的左括號,為非法格式。
解答文章開頭的問題
實現瀏覽器的前進后退功能萎庭，我們需要兩個棧霜医，例如X、Y兩個棧驳规。我們首次瀏覽的頁面依次壓到X棧中肴敛，在點擊后退的時候，在依次從X中出棧，然后依次壓入Y棧中医男。如果前進呢砸狞，就從Y棧中出棧，然后壓到X棧中镀梭。如果X棧中沒有數據時刀森，就說明沒有頁面可以后退了，同樣报账，如果Y棧中沒有數據了研底，就說明沒有頁面可以前進了。
如果我們依次點開a,b,c三個頁面透罢，那么依次壓入X棧中榜晦，如果后退，那么就將后退到c頁面羽圃，這時c將從X棧出棧芽隆，壓入Y棧中，在進行后退统屈，就是將b從X棧出棧，在壓入Y棧中牙躺。
如果在前進的話愁憔，就是b頁面從Y棧出棧，壓入X棧中孽拷。這時候吨掌，你通過b頁面直接跳到了d頁面，頁面c就無法通過前進脓恕、后退進行重復查看了膜宋，所以要清空Y棧。
思考：
JVM內存管理中炼幔，有個"堆棧"的概念秋茫。棧內存用來存儲局部變量和方法調用，堆內存用來存儲Java中的對象乃秀。那JVM中的棧和我們上文中的棧是一個么肛著？？跺讯？
解析：
內存中的堆棧和數據結構中的堆棧不是一個概念枢贿，可以說內存中的堆棧是真是存在的物理區(qū)，數據結構中的堆棧是抽象的數據存儲結構刀脏。
內存空間在邏輯上分為三部分：代碼區(qū)局荚，靜態(tài)數據區(qū)和動態(tài)數據區(qū)，動態(tài)數據區(qū)又分為棧區(qū)和堆區(qū)。
1.代碼區(qū)：存儲方法體的二進制代碼耀态。高級調度(作業(yè)調度)轮傍，中級調度(內存調度)，低級調度(進程調度)控制代碼區(qū)代碼的切換
2.靜態(tài)數據區(qū)：存儲全局變量茫陆、靜態(tài)變量金麸、常量，常量包括final修飾的常量和String常量簿盅。系統(tǒng)自動分配和回收挥下。
3.堆區(qū)：存儲運行方法的形參、局部變量桨醋、返回值棚瘟。有系統(tǒng)自動分配和回收。
4.棧區(qū)：new一個對象的引用或者地址存儲在棧區(qū)喜最，指向該對象存儲在堆區(qū)的真是數據偎蘸。
