棧(stack)

棧又稱之為堆棧是一個特殊的有序表，其插入和刪除操作都在棧頂進行操作，并且按照先進后出，后進先出的規則進行運作。

如下圖所示

例如槍的彈匣，第一顆放進彈匣的子彈反而在發射出去的時候是最后一個，而最后放入彈匣的一顆子彈在打出去的時候是第一顆發射出去的。

棧的接口

如果你創建了一個棧，那么那么應該具有以下接口來進行對棧的操作

知道棧需要上述的接口后，那么在Python中，列表就類似是一個棧，提供接口如下：

Python中的棧接口使用實例：

# 創建一個棧In [1]: s = []# 往棧內添加一個元素In [2]: s.append(1)In [3]: sOut[3]: [1]# 刪除棧內的一個元素In [4]: s.pop()Out[4]: 1In [5]: sOut[5]: []# 判斷棧是否為空In [6]: not sOut[6]: TrueIn [7]: s.append(1)In [8]: not sOut[8]: False# 獲取棧內元素的數量In [9]: len(s)Out[9]: 1In [10]: s.append(2)In [11]: s.append(3)# 取棧頂的元素In [12]: s[-1]Out[12]: 3

一大波實例

在了解棧的基本概念之后，讓我們再來看幾個實例，以便于理解棧。

括號匹配

題目

假如表達式中允許包含三中括號()、[]、{}，其嵌套順序是任意的，例如：

正確的格式

{()[()]},[{({})}]

錯誤的格式

[(]),[()),(()}

編寫一個函數，判斷一個表達式字符串，括號匹配是否正確

思路

創建一個空棧，用來存儲尚未找到的左括號； 便利字符串，遇到左括號則壓棧，遇到右括號則出棧一個左括號進行匹配； 在第二步驟過程中，如果空棧情況下遇到右括號，說明缺少左括號，不匹配； 在第二步驟遍歷結束時，棧不為空，說明缺少右括號，不匹配；