一、什么是棧？
1.后進者先出，先進者后出，這就是典型的“棧”結(jié)構(gòu)。
2.從棧的操作特性來看，是一種“操作受限”的線性表，只允許在端插入和刪除數(shù)據(jù)。
二、為什么需要棧？
1.棧是一種操作受限的數(shù)據(jù)結(jié)構(gòu)，其操作特性用數(shù)組和鏈表均可實現(xiàn)。
2.但，任何數(shù)據(jù)結(jié)構(gòu)都是對特定應用場景的抽象，數(shù)組和鏈表雖然使用起來更加靈活，但卻暴露了幾乎所有的操作，難免會引發(fā)錯誤操作的風險。
3.所以，當某個數(shù)據(jù)集合只涉及在某端插入和刪除數(shù)據(jù)，且滿足后進者先出，先進者后出的操作特性時，我們應該首選棧這種數(shù)據(jù)結(jié)構(gòu)。
三、如何實現(xiàn)棧？
"""
Stack based upon linked list
基于鏈表實現(xiàn)的棧
Author: Wenru
"""
from typing import Optional
class Node:
def __init__(self, data: int, next=None):
self._data = data
self._next = next
class LinkedStack:
"""A stack based upon singly-linked list.
"""
def __init__(self):
self._top: Node = None
def push(self, value: int):
new_top = Node(value)
new_top._next = self._top
self._top = new_top
def pop(self) -> Optional[int]:
if self._top:
value = self._top._data
self._top = self._top._next
return value
def __repr__(self) -> str:
current = self._top
nums = []
while current:
nums.append(current._data)
current = current._next
return " ".join(f"{num}]" for num in nums)
if __name__ == "__main__":
stack = LinkedStack()
for i in range(9):
stack.push(i)
print(stack)
for _ in range(3):
stack.pop()
print(stack)
四、棧的應用
1.棧在函數(shù)調(diào)用中的應用
操作系統(tǒng)給每個線程分配了一塊獨立的內(nèi)存空間，這塊內(nèi)存被組織成“?！边@種結(jié)構(gòu)，用來存儲函數(shù)調(diào)用時的臨時變量。每進入一個函數(shù)，就會將其中的臨時變量作為棧幀入棧，當被調(diào)用函數(shù)執(zhí)行完成，返回之后，將這個函數(shù)對應的棧幀出棧。
2.棧在表達式求值中的應用（比如：34+13*9+44-12/3）
利用兩個棧，其中一個用來保存操作數(shù)，另一個用來保存運算符。我們從左向右遍歷表達式，當遇到數(shù)字，我們就直接壓入操作數(shù)棧；當遇到運算符，就與運算符棧的棧頂元素進行比較，若比運算符棧頂元素優(yōu)先級高，就將當前運算符壓入棧，若比運算符棧頂元素的優(yōu)先級低或者相同，從運算符棧中取出棧頂運算符，從操作數(shù)棧頂取出2個操作數(shù)，然后進行計算，把計算完的結(jié)果壓入操作數(shù)棧，繼續(xù)比較。
3.棧在括號匹配中的應用（比如：{}{()}）
用棧保存為匹配的左括號，從左到右一次掃描字符串，當掃描到左括號時，則將其壓入棧中；當掃描到右括號時，從棧頂取出一個左括號，如果能匹配上，則繼續(xù)掃描剩下的字符串。如果掃描過程中，遇到不能配對的右括號，或者棧中沒有數(shù)據(jù)，則說明為非法格式。
當所有的括號都掃描完成之后，如果棧為空，則說明字符串為合法格式；否則，說明未匹配的左括號為非法格式。
4.如何實現(xiàn)瀏覽器的前進后退功能？
我們使用兩個棧X和Y，我們把首次瀏覽的頁面依次壓如棧X，當點擊后退按鈕時，再依次從棧X中出棧，并將出棧的數(shù)據(jù)一次放入Y棧。當點擊前進按鈕時，我們依次從棧Y中取出數(shù)據(jù)，放入棧X中。當棧X中沒有數(shù)據(jù)時，說明沒有頁面可以繼續(xù)后退瀏覽了。當Y棧沒有數(shù)據(jù)，那就說明沒有頁面可以點擊前進瀏覽了。
五、思考
- 我們在講棧的應用時，講到用函數(shù)調(diào)用棧來保存臨時變量，為什么函數(shù)調(diào)用要用“?！眮肀４媾R時變量呢？用其他數(shù)據(jù)結(jié)構(gòu)不行嗎？
答：因為函數(shù)調(diào)用的執(zhí)行順序符合后進者先出，先進者后出的特點。比如函數(shù)中的局部變量的生命周期的長短是先定義的生命周期長，后定義的生命周期短；還有函數(shù)中調(diào)用函數(shù)也是這樣，先開始執(zhí)行的函數(shù)只有等到內(nèi)部調(diào)用的其他函數(shù)執(zhí)行完畢，該函數(shù)才能執(zhí)行結(jié)束。
正是由于函數(shù)調(diào)用的這些特點，根據(jù)數(shù)據(jù)結(jié)構(gòu)是特定應用場景的抽象的原則，我們優(yōu)先考慮棧結(jié)構(gòu)。
2.我們都知道，JVM 內(nèi)存管理中有個“堆?！钡母拍?。棧內(nèi)存用來存儲局部變量和方法調(diào)用，堆內(nèi)存用來存儲 Java 中的對象。那 JVM 里面的“?！备覀冞@里說的“?！笔遣皇且换厥履?？如果不是，那它為什么又叫作“?！蹦?？
答：JVM里面的棧和我們這里說的是一回事，被稱為方法棧。和前面函數(shù)調(diào)用的作用是一致的，用來存儲方法中的局部變量。
