Python算法實戰系列：棧
作者：佚名
棧(stack)又稱之為堆棧是一個特殊的有序表，其插入和刪除操作都在棧頂進行操作，并且按照先進后出，后進先出的規則進行運作。
棧(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<n
- 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開發者
