棧(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)]
#!/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#!/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] """
rrreee
後綴表達式求值
題目
計算一個表達式時，編譯器通常使用後綴表達式，這種表達式不需要括號：
編寫程式。
思路
建立一個棧來儲存待計算的操作數；
遍歷字串，遇到操作數則壓入棧中，遇到操作符號則出棧操作數(n次)，進行相應的計算，計算結果是新的操作數壓回棧中，等待計算
解決代碼
rrreee背包問題
題目
rrreee
背包問題🎜🎜題目🎜🎜rrreee🎜背包問題🎜🎜題目🎜🎜rrreee🎜背包問題🎜🎜題目🎜🎜有一個背包能裝10kg的物品，現在有6件物品分別為：🎜🎜🎜🎜🎜編寫找出所有能將背包裝滿的解，如物品1+物品5。 🎜🎜解決程式碼🎜rrreee🎜總結🎜🎜以上就是這篇文章的全部內容了，希望本文的內容對大家的學習或工作能帶來一定的幫助，如果有疑問大家可以留言交流。 🎜🎜更多Python演算法應用實戰之棧詳解相關文章請關注PHP中文網！ 🎜
