知識星球
學Python最簡單的方法是什麼？推薦閱讀：Python開發工程師成長魔法
棧(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]: not s
Out[6]: True
In [7]: s.append(1)
In [8]: not s
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 = {‘)’, ‘]’, ‘}’} # 右括號
def match(expr):
“””
:param expr: 傳過來的字串
:return: 傳回是否是正確的
“””
stack = [] # 建立一個棧
for brackets in expr: # 迭代傳過來的所有字串
if brackets in LEFT: # 如果當前字元在左括號內
stack.append(brackets) # 把當前左括號入棧
elif brackets in RIGHT: # 如果是右括號
if not stack or not 1 <= ord(brackets) – ord(stack[–1]) <= 2:
# 如果當前棧為空，()]
# 如果右括號減去左括號的值不是小於等於2大於等於1
return False # 傳回False
stack.pop() # 刪除左括號
return not stack # 如果棧內沒有值則傳回True，否則傳回False
result = match(‘[(){()}]’)
print(result)
迷宮問題
題目
用一個二維陣列表示一個簡單的迷宮，用0表示通路，用1表示阻斷，老鼠在每個點上可以移動相鄰的東南西北四個點，設計一個演演算法，模擬老鼠走迷宮，找到從入口到出口的一條路徑。
如圖所示
出去的正確線路如圖中的紅線所示
思路
-
用一個棧來記錄老鼠從入口到出口的路徑
-
走到某點後，將該點左邊壓棧，並把該點值置為1，表示走過了；
-
從臨近的四個點中可到達的點中任意選取一個，走到該點；
-
如果在到達某點後臨近的4個點都不走，說明已經走入死衚衕，此時退棧，退回一步嘗試其他點；
-
反覆執行第二、三、四步驟直到找到出口；
解決程式碼
#!/use/bin/env python
# _*_ coding:utf-8 _*_
def initMaze():
“””
:return: 初始化迷宮
“””
maze = [[0] * 7 for _ in range(5 + 2)] # 用串列解析建立一個7*7的二維陣列，為了確保迷宮四周都是牆
walls = [ # 記錄了牆的位置
(1, 3),
(2, 1), (2, 5),
(3, 3), (3, 4),
(4, 2), # (4, 3), # 如果把(4, 3)點也設定為牆，那麼整個迷宮是走不出去的，所以會傳回一個空串列
(5, 4)
]
for i in range(7): # 把迷宮的四周設定成牆
maze[i][0] = maze[i][–1] = 1
maze[0][i] = maze[–1][i] = 1
for i, j in walls: # 把所有牆的點設定為1
maze[i][j] = 1
return maze
“””
[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]
“””
def path(maze, start, end):
“””
:param maze: 迷宮
:param start: 起始點
:param end: 結束點
:return: 行走的每個點
“””
i, j = start # 分解起始點的坐標
ei, ej = end # 分解結束點的左邊
stack = [(i, j)] # 建立一個棧，並讓老鼠站到起始點的位置
maze[i][j] = 1 # 走過的路置為1
while stack: # 棧不為空的時候繼續走，否則退出
i, j = stack[–1] # 獲取當前老鼠所站的位置點
if (i, j) == (ei, ej): break # 如果老鼠找到了出口
for di, dj in [(0, –1), (0, 1), (–1, 0), (1, 0)]: # 左右上下
if maze[i + di][j + dj] == 0: # 如果當前點可走
maze[i + di][j + dj] = 1 # 把當前點置為1
stack.append((i + di, j + dj)) # 把當前的位置新增到棧裡面
break
else: # 如果所有的點都不可走
stack.pop() # 退回上一步
return stack # 如果迷宮不能走則傳回空棧
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 = { # 運運算元操作表
‘+’: lambda op1, op2: op1 + op2,
‘-‘: lambda op1, op2: op1 – op2,
‘*’: lambda op1, op2: op1 * op2,
‘/’: lambda op1, op2: op1 / op2,
}
def evalPostfix(e):
“””
:param e: 字尾運算式
:return: 正常情況下棧內的第一個元素就是計算好之後的值
“””
tokens = e.split() # 把傳過來的字尾運算式切分成串列
stack = []
for token in tokens: # 迭代串列中的元素
if token.isdigit(): # 如果當前元素是數字
stack.append(int(token)) # 就追加到棧裡邊
elif token in operators.keys(): # 如果當前元素是運運算元
f = operators[token] # 獲取運運算元操作表中對應的lambda運算式
op2 = stack.pop() # 根據先進後出的原則，先讓第二個元素出棧
op1 = stack.pop() # 在讓第一個元素出棧
stack.append(f(op1, op2)) # 把計算的結果在放入到棧內
return stack.pop() # 傳回棧內的第一個元素
result = evalPostfix(‘2 3 4 * +’)
print(result)
# 14
揹包問題
題目
有一個揹包能裝10kg的物品，現在有6件物品分別為：
編寫找出所有能將揹包裝滿的解，如物品1+物品5。
解決程式碼
#!/use/bin/env python
# _*_ coding:utf-8 _*_
def knapsack(t, w):
“””
:param t: 揹包總容量
:param w: 物品重量串列
:return:
“””
n = len(w) # 可選的物品數量
stack = [] # 建立一個棧
k = 0 # 當前所選擇的物品遊標
while stack or k < n: # 棧不為空或者k
while t > 0 and k < n: # 還有剩餘空間並且有物品可裝
if t >= w[k]: # 剩餘空間大於等於當前物品重量
stack.append(k) # 把物品裝備揹包
t -= w[k] # 揹包空間減少
k += 1 # 繼續向後找
if t == 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]
“””
來源：安生
————近期開班————
《馬哥教育Python自動化開發全能實戰班》是馬哥教育聯合阿裡、豆瓣、大眾點評等一線Python工程師，根據目前企業需求的Python開發人才進行了深度定製，加入大量一線網際網路公司：大眾點評、餓了麼、騰訊等生產環境真是專案，課程由淺入深，從Python基礎到Python高階，讓你融匯貫通Python基礎理論到日誌分析、todolist任務管理系統、類Flask框架多人部落格、CMDB資產管理、任務排程系統、運維流程系統六大專案實戰，手把手教學讓你從0開始蛻變成Hold住年薪30萬的Python自動化開發人才。
10期面授班：2018年03月05號（北京）
11期網路班：2018年03月17號（網路）
更多Python好文請點選【閱讀原文】哦
↓↓↓
