// 基于數(shù)組實(shí)現(xiàn)的順序棧
public class ArrayStack {
  private String[] items;  // 數(shù)組
  private int count;       // 棧中元素個(gè)數(shù)
  private int n;           // 棧的大小

  // 初始化數(shù)組，申請(qǐng)一個(gè)大小為 n 的數(shù)組空間
  public ArrayStack(int n) {
    this.items = new String[n];
    this.n = n;
    this.count = 0;
  }

  // 入棧操作
  public boolean push(String item) {
    // 數(shù)組空間不夠了，直接返回 false，入棧失敗。
    if (count == n) return false;
    // 將 item 放到下標(biāo)為 count 的位置，并且 count 加一
    items[count] = item;
    ++count;
    return true;
  }
  
  // 出棧操作
  public String pop() {
    // 棧為空，則直接返回 null
    if (count == 0) return null;
    // 返回下標(biāo)為 count-1 的數(shù)組元素，并且棧中元素個(gè)數(shù) count 減一
    String tmp = items[count-1];
    --count;
    return tmp;
  }
}

了解了棧的基本操作，接下來(lái)我們分析一下，棧操作的時(shí)間復(fù)雜度和空間復(fù)雜的吧。

無(wú)論是順序棧還是鏈?zhǔn)綏?，我們存?chǔ)都只需要一個(gè)大小為n的數(shù)據(jù)就夠了。在入棧和出棧的過程中，只需要兩個(gè)臨時(shí)變量的存儲(chǔ)空間，所以空間復(fù)雜度是O(1)。

注意：這里說到存儲(chǔ)數(shù)據(jù)需要一個(gè)大小為n的數(shù)組，并不是說空間復(fù)雜度就是O(n)。因?yàn)檫@個(gè)n是空間必須的，無(wú)法省掉的。所以說，我們說空間復(fù)雜度的時(shí)候，是指除了原本數(shù)組存儲(chǔ)空間外，算法運(yùn)行還需的額外的存儲(chǔ)空間。

空間復(fù)雜度不難，時(shí)間復(fù)雜度也不難。無(wú)論是順序棧還是鏈?zhǔn)綏＃瑮５娜霔：统鰲２僮鞫际侵簧婕皸ｍ數(shù)膫€(gè)別數(shù)據(jù)的操作，所以時(shí)間復(fù)雜的是O(1)。

支持動(dòng)態(tài)擴(kuò)容的順序棧
上面的那個(gè)是基于數(shù)組實(shí)現(xiàn)的棧，也就是一個(gè)固定大小的棧，也就是說在棧初始化的時(shí)候就要指定棧的大小。當(dāng)棧滿后，就無(wú)法存儲(chǔ)數(shù)據(jù)了。盡管是鏈?zhǔn)綏５拇笮〔皇芟拗疲谴鎯?chǔ)next指針，內(nèi)存消耗也是較多的。接下來(lái)我們學(xué)習(xí)一下基于數(shù)組實(shí)現(xiàn)一個(gè)支持動(dòng)態(tài)擴(kuò)容的棧。

先回顧一下，數(shù)組是如何動(dòng)態(tài)擴(kuò)容的。當(dāng)數(shù)組空間不夠使，就要申請(qǐng)一塊更大的內(nèi)存空間，然后將原來(lái)數(shù)組里的數(shù)組拷貝過去，這樣來(lái)完成擴(kuò)容。

所以，我們要實(shí)現(xiàn)一個(gè)動(dòng)態(tài)擴(kuò)容的棧，只需要底層依賴一個(gè)可以動(dòng)態(tài)擴(kuò)容的數(shù)組即可。當(dāng)棧滿的時(shí)候，在進(jìn)行申請(qǐng)一個(gè)更大的數(shù)組既可以了?？梢詤⒖枷聢D進(jìn)行理解：

image.png

其實(shí)，支持動(dòng)態(tài)擴(kuò)容的順序棧，我們平時(shí)是用不到的。但是我們可以通過這個(gè)來(lái)練習(xí)一下復(fù)雜度分析。
現(xiàn)在我們可以一起分析一下，支持動(dòng)態(tài)擴(kuò)容的順序棧的入棧出棧操作的復(fù)雜度分析。
對(duì)于出棧操作來(lái)講，不會(huì)涉及到內(nèi)存的申請(qǐng)和數(shù)據(jù)搬移，所以什么情況下的時(shí)間復(fù)雜度都是O(1)；
對(duì)于入棧來(lái)講，如果棧中有空余空間時(shí)，那么時(shí)間復(fù)雜度就是O(1)，如果棧中沒有空余空間時(shí)，需要申請(qǐng)內(nèi)存空間，那么就涉及到內(nèi)存的申請(qǐng)和數(shù)據(jù)搬移，這樣，時(shí)間復(fù)雜度就是O(n)。
也就是說，入棧的最好情況時(shí)間復(fù)雜度是O(1)，最壞情況時(shí)間復(fù)雜度是O(n)。那平均時(shí)間復(fù)雜度是多少呢？這就需要用到我們之間文章里面提到過的攤還分析法了。

為了方便分析，我們先做一些假設(shè)和定義

• 假設(shè)?？臻g不足的時(shí)候，我們需要重新申請(qǐng)?jiān)瓉?lái)大小兩倍的數(shù)組大小
• 假設(shè)我們只考慮入棧不考慮出棧
• 定義不涉及到內(nèi)存搬移的入棧操作為simple-push操作，時(shí)間復(fù)雜度為O(1)

如果，當(dāng)前棧的大小為k，并且已滿，當(dāng)有新的數(shù)據(jù)需要入棧的時(shí)候，就需要申請(qǐng)兩倍大小的內(nèi)存，并且做k個(gè)數(shù)據(jù)的搬移操作，然后在入棧。但是接下來(lái)的k-1次入棧操作，就不需要在此申請(qǐng)內(nèi)存和數(shù)據(jù)搬移了，所以這k-1次入?yún)⒉僮鞫贾恍枰粋€(gè)simple-push操作就可以完成。
可以根據(jù)下圖進(jìn)行理解。

image.png

可以看出這k次入棧操作，涉及到了k個(gè)數(shù)據(jù)的搬移操作和k次simple-single操作。將k個(gè)數(shù)據(jù)搬移的操作平均分到k次simple-push操作上，那沒個(gè)數(shù)據(jù)入棧只需要一次數(shù)據(jù)搬移和一次simple-push操作。以此類推，入棧操作的時(shí)間復(fù)雜度就是O(1)

通過這個(gè)例子的實(shí)戰(zhàn)分析,也印證了前面文章提到的,均攤時(shí)間復(fù)雜度-般都等 于最好情況時(shí)間復(fù)雜度。因?yàn)樵诖蟛糠智闆r下,入棧操作的時(shí)間復(fù)雜度O都是O(1),只有在個(gè)別時(shí)刻才會(huì)退化為O(n) ,所以把耗時(shí)多的入棧操作的時(shí)間均攤到其他入棧操作上,平均情況下的耗時(shí)就接近O(1)

棧的實(shí)際應(yīng)用

1.棧在函數(shù)調(diào)用中的應(yīng)用

棧作為比較基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)，應(yīng)用場(chǎng)景還是很多的。比較經(jīng)典的場(chǎng)景就是函數(shù)調(diào)用棧

我們知道，操作系統(tǒng)給每個(gè)線程分配了一塊獨(dú)立的內(nèi)存空間，這塊內(nèi)存被組織成"棧"的結(jié)構(gòu)，用來(lái)存儲(chǔ)調(diào)用時(shí)的臨時(shí)變量。每進(jìn)入一個(gè)函數(shù)，就會(huì)將臨時(shí)變量作為一個(gè)棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個(gè)函數(shù)對(duì)應(yīng)的棧幀出棧。為了更好的理解，可以看一下下面的這段代碼：

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()函數(shù)調(diào)用了add()函數(shù)，獲取計(jì)算結(jié)果，并與臨時(shí)變量a相加，最后打印res的值。為了更清晰的看出這個(gè)過程中函數(shù)棧里入棧、出棧的操作，可以參考下圖，分析理解。圖中顯示的是，在執(zhí)行到add()函數(shù)時(shí)，函數(shù)調(diào)用棧的情況。

image.png

2.棧在表達(dá)式求值中的應(yīng)用

我們一起了解一下，編譯器如何用棧來(lái)實(shí)現(xiàn)表達(dá)式求值的。

我們簡(jiǎn)單舉例學(xué)習(xí)，就說一下最簡(jiǎn)單的包含加減乘除的四則運(yùn)算，比如3+5*8-6。對(duì)于這個(gè)四則運(yùn)算，我們是很快就會(huì)算出來(lái)了，但是對(duì)于計(jì)算機(jī)來(lái)說，理解這個(gè)表達(dá)式就是很難得一件事情了。

實(shí)際上，計(jì)算機(jī)就是通過兩個(gè)棧來(lái)實(shí)現(xiàn)的。一個(gè)操作數(shù)棧，一個(gè)運(yùn)算符棧。操作數(shù)棧就是用來(lái)存儲(chǔ)操作數(shù)的，運(yùn)算符棧就是用來(lái)存儲(chǔ)運(yùn)算符的。

具體流程：
首先，我們從左到右遍歷表達(dá)式，遇到數(shù)字就壓入操作數(shù)棧，遇到運(yùn)算符就與運(yùn)算符棧頂元素進(jìn)行比較。如果比運(yùn)算符棧頂元素優(yōu)先級(jí)高，就將當(dāng)前運(yùn)算符壓入棧中；如果比運(yùn)算符棧頂元素優(yōu)先級(jí)低或者相同，從運(yùn)算符棧中取出棧頂運(yùn)算符，從操作數(shù)棧的棧頂取兩個(gè)操作數(shù)，然后進(jìn)行計(jì)算，然后再把計(jì)算后的結(jié)果壓入操作數(shù)棧中，繼續(xù)比較。
下面是例子中表達(dá)式的計(jì)算過程圖，可以參考，便于理解

3.棧在括號(hào)匹配中的應(yīng)用

除了用棧來(lái)實(shí)現(xiàn)表達(dá)式求值,我們還可以借助棧來(lái)檢查表達(dá)式中的括號(hào)是否匹配。

我們同樣簡(jiǎn)化-下背景。我們假設(shè)表達(dá)式中只包含三種括號(hào),圓括號(hào)0、方括號(hào)D和花括號(hào)}，并且它們可以任意嵌套。比如，{[]]或[{0(D)]等都為臺(tái)法格式,而{D0]或[(0]為不合法的格式。那我現(xiàn)在給你一個(gè)包含三種括號(hào)的表達(dá)式字符串,如何檢查它是否臺(tái)法呢?

這里也可以用棧來(lái)解決。我們用棧來(lái)保存未匹配的左括號(hào),從左到右依次掃描字符串。當(dāng)掃描到左括號(hào)時(shí),則將其壓入棧中;當(dāng)掃描到右括號(hào)時(shí),從棧頂取出一個(gè)左括號(hào)。如果能夠匹配,比如“(”跟“”匹配，"[”跟“”匹配，”{”跟“”匹配，則繼續(xù)掃描剩下的字符串。如果掃描的過程中,遇到不能對(duì)的右括號(hào),或者棧中沒有數(shù)據(jù),則說明為非法格式。

當(dāng)所有的括號(hào)都掃描完成之后,如果棧為空,則說明字符串為合法格式:否則,說明有未匹配的左括號(hào),為非法格式。

解答文章開頭的問題
實(shí)現(xiàn)瀏覽器的前進(jìn)后退功能，我們需要兩個(gè)棧，例如X、Y兩個(gè)棧。我們首次瀏覽的頁(yè)面依次壓到X棧中，在點(diǎn)擊后退的時(shí)候，在依次從X中出棧，然后依次壓入Y棧中。如果前進(jìn)呢，就從Y棧中出棧，然后壓到X棧中。如果X棧中沒有數(shù)據(jù)時(shí)，就說明沒有頁(yè)面可以后退了，同樣，如果Y棧中沒有數(shù)據(jù)了，就說明沒有頁(yè)面可以前進(jìn)了。

如果我們依次點(diǎn)開a,b,c三個(gè)頁(yè)面，那么依次壓入X棧中，如果后退，那么就將后退到c頁(yè)面，這時(shí)c將從X棧出棧，壓入Y棧中，在進(jìn)行后退，就是將b從X棧出棧，在壓入Y棧中。
如果在前進(jìn)的話，就是b頁(yè)面從Y棧出棧，壓入X棧中。這時(shí)候，你通過b頁(yè)面直接跳到了d頁(yè)面，頁(yè)面c就無(wú)法通過前進(jìn)、后退進(jìn)行重復(fù)查看了，所以要清空Y棧。

思考：
JVM內(nèi)存管理中，有個(gè)"堆棧"的概念。棧內(nèi)存用來(lái)存儲(chǔ)局部變量和方法調(diào)用，堆內(nèi)存用來(lái)存儲(chǔ)Java中的對(duì)象。那JVM中的棧和我們上文中的棧是一個(gè)么？？？

解析：
內(nèi)存中的堆棧和數(shù)據(jù)結(jié)構(gòu)中的堆棧不是一個(gè)概念，可以說內(nèi)存中的堆棧是真是存在的物理區(qū)，數(shù)據(jù)結(jié)構(gòu)中的堆棧是抽象的數(shù)據(jù)存儲(chǔ)結(jié)構(gòu)。
內(nèi)存空間在邏輯上分為三部分：代碼區(qū)，靜態(tài)數(shù)據(jù)區(qū)和動(dòng)態(tài)數(shù)據(jù)區(qū)，動(dòng)態(tài)數(shù)據(jù)區(qū)又分為棧區(qū)和堆區(qū)。
1.代碼區(qū)：存儲(chǔ)方法體的二進(jìn)制代碼。高級(jí)調(diào)度(作業(yè)調(diào)度)，中級(jí)調(diào)度(內(nèi)存調(diào)度)，低級(jí)調(diào)度(進(jìn)程調(diào)度)控制代碼區(qū)代碼的切換
2.靜態(tài)數(shù)據(jù)區(qū)：存儲(chǔ)全局變量、靜態(tài)變量、常量，常量包括final修飾的常量和String常量。系統(tǒng)自動(dòng)分配和回收。
3.堆區(qū)：存儲(chǔ)運(yùn)行方法的形參、局部變量、返回值。有系統(tǒng)自動(dòng)分配和回收。
4.棧區(qū)：new一個(gè)對(duì)象的引用或者地址存儲(chǔ)在棧區(qū)，指向該對(duì)象存儲(chǔ)在堆區(qū)的真是數(shù)據(jù)。