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

如下圖所示

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

棧的接口

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

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

Python中的棧接口使用實例：

# 創建一個棧

In[1]: s = []

# 往棧內添加一個元素

In[2]: s.append(1)

In[3]: s

Out[3]: [1]

# 刪除棧內的一個元素

In[4]: s.pop()

Out[4]: 1

In[5]: s

Out[5]: []

# 判斷棧是否為空

In[6]: nots

Out[6]: True

In[7]: s.append(1)

In[8]: nots

Out[8]: False

# 獲取棧內元素的數量

In[9]: len(s)

Out[9]: 1

In[10]: s.append(2)

In[11]: s.append(3)

# 取棧頂的元素

In[12]: s[-1]

Out[12]: 3

一大波實例

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

括號匹配

題目

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

正確的格式

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

錯誤的格式

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

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

思路

創建一個空棧，用來存儲尚未找到的左括號；

便利字符串，遇到左括號則壓棧，遇到右括號則出棧一個左括號進行匹配；

在第二步驟過程中，如果空棧情況下遇到右括號，說明缺少左括號，不匹配；

在第二步驟遍歷結束時，棧不為空，說明缺少右括號，不匹配；

解決代碼

建議在pycharm中打斷點，以便于更好的理解

#!/use/bin/env python

# _*_ coding:utf-8 _*_

LEFT = {'(','[','{'}# 左括號

RIGHT = {')',']','}'}# 右括號

defmatch(expr):

"""

:param expr:傳過來的字符串

:return:返回是否是正確的

"""

stack = []# 創建一個棧

forbrackets inexpr:# 迭代傳過來的所有字符串

ifbrackets inLEFT:# 如果當前字符在左括號內

stack.append(brackets)# 把當前左括號入棧

elifbrackets inRIGHT:# 如果是右括號

ifnotstack ornot1 <= ord(brackets) - ord(stack[-1]) <= 2:

# 如果當前棧為空，()]

# 如果右括號減去左括號的值不是小于等于2大于等于1

returnFalse# 返回False

stack.pop()# 刪除左括號

returnnotstack# 如果棧內沒有值則返回True，否則返回False

result = match('[(){()}]')

print(result)

迷宮問題

題目

用一個二維數組表示一個簡單的迷宮，用0表示通路，用1表示阻斷，老鼠在每個點上可以移動相鄰的東南西北四個點，設計一個算法，模擬老鼠走迷宮，找到從入口到出口的一條路徑。

如圖所示

出去的正確線路如圖中的紅線所示

思路

用一個棧來記錄老鼠從入口到出口的路徑

走到某點后，將該點左邊壓棧，并把該點值置為1，表示走過了；

從臨近的四個點中可到達的點中任意選取一個，走到該點；

如果在到達某點后臨近的4個點都不走，說明已經走入死胡同，此時退棧，退回一步嘗試其他點；

反復執行第二、三、四步驟直到找到出口；

解決代碼

#!/use/bin/env python

# _*_ coding:utf-8 _*_

definitMaze():

"""

:return: 初始化迷宮

"""

maze = [[0] * 7for_inrange(5 + 2)]# 用列表解析創建一個7*7的二維數組，為了確保迷宮四周都是墻

walls = [# 記錄了墻的位置

(1,3),

(2,1),(2,5),

(3,3),(3,4),

(4,2),# (4, 3),# 如果把(4, 3)點也設置為墻，那么整個迷宮是走不出去的，所以會返回一個空列表

(5,4)

]

foriinrange(7):# 把迷宮的四周設置成墻

maze[i][0] = maze[i][-1] = 1

maze[0][i] = maze[-1][i] = 1

fori,jinwalls:# 把所有墻的點設置為1

maze[i][j] = 1

returnmaze

"""

[1, 1, 1, 1, 1, 1, 1]

[1, 0, 0, 1, 0, 0, 1]

[1, 1, 0, 0, 0, 1, 1]

[1, 0, 0, 1, 1, 0, 1]

[1, 0, 1, 0, 0, 0, 1]

[1, 0, 0, 0, 1, 0, 1]

[1, 1, 1, 1, 1, 1, 1]

"""

defpath(maze,start,end):

"""

:param maze: 迷宮

:param start: 起始點

:param end: 結束點

:return: 行走的每個點

"""

i,j = start# 分解起始點的坐標

ei,ej = end# 分解結束點的左邊

stack = [(i,j)]# 創建一個棧，并讓老鼠站到起始點的位置

maze[i][j] = 1# 走過的路置為1

whilestack:# 棧不為空的時候繼續走，否則退出

i,j = stack[-1]# 獲取當前老鼠所站的位置點

if(i,j) == (ei,ej): break# 如果老鼠找到了出口

fordi,dj in[(0, -1),(0,1),(-1,0),(1,0)]:# 左右上下

ifmaze[i + di][j + dj] == 0:# 如果當前點可走

maze[i + di][j + dj] = 1# 把當前點置為1

stack.append((i + di,j + dj))# 把當前的位置添加到棧里面

break

else:# 如果所有的點都不可走

stack.pop()# 退回上一步

returnstack# 如果迷宮不能走則返回空棧

Maze = initMaze()# 初始化迷宮

result = path(maze=Maze,start=(1,1),end=(5,5))# 老鼠開始走迷宮

print(result)

# [(1, 1), (1, 2), (2, 2), (3, 2), (3, 1), (4, 1), (5, 1), (5, 2), (5, 3), (4, 3), (4, 4), (4, 5), (5, 5)]

后綴表達式求值

題目

計算一個表達式時，編譯器通常使用后綴表達式，這種表達式不需要括號：

編寫程序實現后綴表達式求值函數。

思路

建立一個棧來存儲待計算的操作數；

遍歷字符串，遇到操作數則壓入棧中，遇到操作符號則出棧操作數(n次)，進行相應的計算，計算結果是新的操作數壓回棧中，等待計算

按上述過程，遍歷完整個表達式，棧中只剩下最終結果；

解決代碼

#!/use/bin/env python

# _*_ coding:utf-8 _*_

operators = {# 運算符操作表

'+': lambdaop1,op2: op1 + op2,

'-': lambdaop1,op2: op1 - op2,

'*': lambdaop1,op2: op1 * op2,

'/': lambdaop1,op2: op1 / op2,

}

defevalPostfix(e):

"""

:param e: 后綴表達式

:return: 正常情況下棧內的第一個元素就是計算好之后的值

"""

tokens = e.split()# 把傳過來的后綴表達式切分成列表

stack = []

fortokenintokens:# 迭代列表中的元素

iftoken.isdigit():# 如果當前元素是數字

stack.append(int(token))# 就追加到棧里邊

eliftokeninoperators.keys():# 如果當前元素是操作符

f = operators[token]# 獲取運算符操作表中對應的lambda表達式

op2 = stack.pop()# 根據先進后出的原則，先讓第二個元素出棧

op1 = stack.pop()# 在讓第一個元素出棧

stack.append(f(op1,op2))# 把計算的結果在放入到棧內

returnstack.pop()# 返回棧內的第一個元素

result = evalPostfix('2 3 4 * +')

print(result)

# 14

背包問題

題目

有一個背包能裝10kg的物品，現在有6件物品分別為：

編寫找出所有能將背包裝滿的解，如物品1+物品5。

解決代碼

#!/use/bin/env python

# _*_ coding:utf-8 _*_

defknapsack(t,w):

"""

:param t: 背包總容量

:param w: 物品重量列表

:return:

"""

n = len(w)# 可選的物品數量

stack = []# 創建一個棧

k = 0# 當前所選擇的物品游標

whilestack ork < n:??# 棧不為空或者k

whilet > 0andk < n:??# 還有剩余空間并且有物品可裝

ift >= w[k]:# 剩余空間大于等于當前物品重量

stack.append(k)# 把物品裝備背包

t -= w[k]# 背包空間減少

k += 1# 繼續向后找

ift == 0:# 找到了解

print(stack)

# 回退過程

k = stack.pop()# 把最后一個物品拿出來

t += w[k]# 背包總容量加上w[k]

k += 1# 裝入下一個物品

knapsack(10,[1,8,4,3,5,2])

"""

[0, 2, 3, 5]

[0, 2, 4]

[1, 5]

[3, 4, 5]

"""