數(shù)據(jù)結(jié)構(gòu)的重要部分，棧，棧是OI中常用的一種線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，請(qǐng)注意，本文主要講的是棧這種數(shù)據(jù)結(jié)構(gòu)，而非程序運(yùn)行時(shí)的系統(tǒng)棧/?？臻g，大家一定要弄清晰，別混淆了。

棧的定義和特點(diǎn)

棧（stack）是一個(gè)特殊的線(xiàn)性表，是限定僅在一端（通常是表尾）進(jìn)行插入和刪除操作的線(xiàn)性表。又稱(chēng)為后進(jìn)先出（Last In First Out）的線(xiàn)性表，簡(jiǎn)稱(chēng) LIFO 結(jié)構(gòu)。

棧的特點(diǎn)：后進(jìn)先出，先進(jìn)者后出，就像我們?cè)诜疟P(pán)子，使用的時(shí)候先用后放的，后使用先放的。從棧的操作特性上來(lái)看，棧是一種“操作受限”的線(xiàn)性表，只允許在一端插入和刪除數(shù)據(jù)。

棧的相關(guān)概念：棧是僅在表尾進(jìn)行插入、刪除操作的線(xiàn)性表。

表尾（即an端）稱(chēng)為棧頂 Top；表頭（即a1端）稱(chēng)為棧底 Base

例如：棧 s = (a1,a2,a3.....an-1,an)  a1被稱(chēng)為棧底元素，an被稱(chēng)為棧頂元素

插入元素到棧頂（即表尾）的操作，稱(chēng)為入棧。

從棧頂（即表尾）刪除最后一個(gè)元素的操作，稱(chēng)為出棧。

棧的示意圖：

操作示意圖-入棧：

操作示意圖-出棧：

當(dāng)某個(gè)數(shù)據(jù)集合只涉及在一端插入和刪除數(shù)據(jù)，并且滿(mǎn)足先進(jìn)后出、后進(jìn)先出的特性，應(yīng)該首選“?！边@種數(shù)據(jù)結(jié)構(gòu)。棧的操作包含兩個(gè)操作：入棧和出棧。

棧既可以用數(shù)組實(shí)現(xiàn)，也可以用鏈表來(lái)實(shí)現(xiàn)。用數(shù)組實(shí)現(xiàn)的棧叫順序棧，用鏈表實(shí)現(xiàn)的棧叫鏈?zhǔn)綏！?/p>

對(duì)于出棧操作，不會(huì)涉及到內(nèi)存的重新申請(qǐng)和數(shù)據(jù)的搬移，所以出棧的時(shí)間復(fù)雜度仍然是O(1)。對(duì)于入棧的操作，如果棧中有空閑空間時(shí)，入棧的操作時(shí)間復(fù)雜度是O(1)，當(dāng)空間不夠時(shí)，就需要重新申請(qǐng)內(nèi)存和數(shù)據(jù)搬移，所以時(shí)間復(fù)雜度就變成了O(n)。從上述可以看出，入棧的最好情況時(shí)間復(fù)雜度為O(1)，最壞情況時(shí)間復(fù)雜度為O(n)。

入棧的時(shí)間復(fù)雜度如下圖所示：

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

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

每進(jìn)入一個(gè)函數(shù)，就會(huì)將臨時(shí)變量作為一個(gè)棧幀入棧，當(dāng)被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個(gè)函數(shù)對(duì)應(yīng)的棧幀出棧。例如下面的這個(gè)例子：

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;
}

這個(gè)例子調(diào)用棧的分析如下圖所示：

我們平時(shí)使用的瀏覽器大家肯定不陌生，瀏覽器中的前進(jìn)和后退其實(shí)就是棧的使用，在訪(fǎng)問(wèn)一個(gè)網(wǎng)頁(yè)時(shí)可以理解為入棧操作，返回上一個(gè)頁(yè)面可以理解為出棧操作。