什么是棧营密？
棧是一種受限的線性表械媒，只允許在一端進行元素的插入和刪除操作，進棧和出棧遵循先進后出 和后進先出的規(guī)則。
為什么要用這種受限的數(shù)據(jù)結(jié)構(gòu)纷捞，用數(shù)組和鏈表難道不好嗎痢虹？受限的數(shù)據(jù)結(jié)構(gòu)是用在特定的場景中，數(shù)組和鏈表的操作是很靈活主儡，但是很容易出錯奖唯。
當(dāng)然，數(shù)組和鏈表都可以實現(xiàn)棧這種數(shù)據(jù)結(jié)構(gòu)糜值，用數(shù)組實現(xiàn)的稱為順序棧丰捷，用鏈表實現(xiàn)的稱為鏈?zhǔn)綏?/strong>。相較于數(shù)組寂汇，鏈表的每個元素需要多存儲指針域數(shù)據(jù)瓢阴，對內(nèi)存的消耗更大。
下面說一下進棧和出棧的具體實現(xiàn)過程健无。首先用構(gòu)造一個大小為 4 的棧，依次將 a液斜、b累贤、c、d 壓入棧中少漆，過程如圖所示臼膏。
在元素出棧時，依次將棧頂元素取出示损，即 d渗磅、c、b检访、a 依次出棧始鱼。
棧的時間、空間復(fù)雜度
看一下棧的空間復(fù)雜度脆贵，一個棧需要 n 個存儲單元（固定不變的）医清，每次只操作棧頂一個元素，所以空間復(fù)雜度是 O(1)卖氨。
看一下棧的時間復(fù)雜度会烙，出棧時，不論棧滿還是棧未滿筒捺，不涉及內(nèi)存的申請柏腻，時間復(fù)雜度都為 O(1)，對于出棧系吭，分為兩種情況：
- 棧未滿是元素進棧五嫂。
- 棧滿時元素進棧。
第一種情況村斟，可以直接將元素壓入棧中贫导，時間復(fù)雜度是 O(1) 抛猫。第二種情況略微復(fù)雜一些，需要再申請一塊更大的內(nèi)存空間孩灯，將棧中 n 個元素拷貝到新的內(nèi)存空間中闺金，再進行入棧操作。這樣峰档，時間復(fù)雜度就變成了 O(n)败匹。所以，對于入棧操作讥巡，最好時間復(fù)雜度是 O(1)掀亩，最壞時間復(fù)雜度是 O(n)。
然后再計算一下平均時間復(fù)雜度欢顷，利用之前學(xué)習(xí)的攤還分析法來分析槽棍，下面先做幾個假設(shè)：
- 棧滿時，重新申請一個大小為原來兩倍的內(nèi)存空間抬驴。
- 只有入棧炼七，沒有出棧操作。
- 定義不涉及內(nèi)存搬移的操作為 simple-push 操作布持，時間復(fù)雜度為 O(1)
將 n 個數(shù)據(jù)搬移到新的內(nèi)存空間中豌拙，需要 n 次操作，接下來的 n 次進棧操作不再需要數(shù)據(jù)的遷移题暖，是需要一次 simple-push 操作按傅。將 n 次數(shù)據(jù)搬移操作均攤到接下來的 n 次進棧操作中，相當(dāng)于每次進棧操作有一次數(shù)據(jù)搬移操作和一次 simple-push 操作胧卤，所以平均時間復(fù)雜為 O(1)唯绍。
棧的應(yīng)用
函數(shù)的調(diào)用
在函數(shù)調(diào)用時，第一個進棧的是主函數(shù)中函數(shù)調(diào)用后的下一條指令（函數(shù)調(diào)用語句的下一條可執(zhí)行語句）的地址灌侣，然后是函數(shù)的各個參數(shù)推捐，在大多數(shù)的C編譯器中，參數(shù)是由右往左入棧的侧啼，然后是函數(shù)中的局部變量牛柒。注意靜態(tài)變量是不入棧的。
當(dāng)本次函數(shù)調(diào)用結(jié)束后痊乾，局部變量先出棧皮壁，然后是參數(shù)，最后棧頂指針指向最開始存的地址哪审，也就是主函數(shù)中的下一條指令蛾魄，程序由該點繼續(xù)運行。（轉(zhuǎn)自https://blog.csdn.net/wangyezi19930928/article/details/16921927?utm_source=copy）
括號的匹配
例如 '{ [ ] }'中的括號匹配，將 ‘{’ 壓入棧中滴须，‘[’ 和棧中元素匹配舌狗，發(fā)現(xiàn)匹配不成功，'[' 也壓入棧中扔水，']' 發(fā)現(xiàn)棧中有能匹配的括號 '['痛侍，'[' 出棧，同理魔市，'}' 發(fā)現(xiàn)棧中有能匹配的括號 '{'主届，此時，沒有要匹配的括號元素待德，且棧為空君丁，則說明沒有不能配對的括號。
瀏覽器頁面的前進和后退
瀏覽器一般都有前進和后退瀏覽網(wǎng)頁的功能将宪，這個功能可以用兩個棧來實現(xiàn)绘闷。
現(xiàn)在有兩個棧，分別為棧 A 和棧 B较坛，沒瀏覽一個新的網(wǎng)頁簸喂，就將網(wǎng)頁壓入 A 中，現(xiàn)在 A 中存儲了 a燎潮、b、c扼倘、d 四個網(wǎng)頁确封，當(dāng)點擊后退按鈕時，d 從 A 出棧再菊，并且壓入 B 中爪喘，再點擊一次后退按鈕，c 從 A 出棧纠拔，并且壓入 B 中秉剑，直到 a 從 A 出棧，壓入 B 中稠诲，棧 A 為空侦鹏，就無法后退，具體操作如圖所示臀叙。
點擊前進按鈕略水，a 從 B 中出棧，壓入 A 中劝萤，操作與后退是進出棧相同渊涝。
小結(jié)
棧的操作比較簡單，一般用在特定的情況下，棧的應(yīng)用也比較廣泛跨释，很多應(yīng)用沒有一一列出來胸私，函數(shù)調(diào)用為什么要用棧這種數(shù)據(jù)結(jié)構(gòu)，還需要再研究一下鳖谈。
