自拍偷在线精品自拍偷,亚洲欧美中文日韩v在线观看不卡

Python算法實(shí)戰(zhàn)系列：棧

作者：佚名
開發(fā) 后端 算法
棧(stack)又稱之為堆棧是一個(gè)特殊的有序表，其插入和刪除操作都在棧頂進(jìn)行操作，并且按照先進(jìn)后出，后進(jìn)先出的規(guī)則進(jìn)行運(yùn)作。

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

如下圖所示

 

 

例如槍的彈匣，第一顆放進(jìn)彈匣的子彈反而在發(fā)射出去的時(shí)候是最后一個(gè)，而最后放入彈匣的一顆子彈在打出去的時(shí)候是第一顆發(fā)射出去的。

棧的接口

如果你創(chuàng)建了一個(gè)棧，那么那么應(yīng)該具有以下接口來(lái)進(jìn)行對(duì)棧的操作 

 

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

 

Python中的棧接口使用實(shí)例：

  1. # 創(chuàng)建一個(gè)棧 
  2.  
  3. In [1]: s = [] 
  4.  
  5. # 往棧內(nèi)添加一個(gè)元素 
  6.  
  7. In [2]: s.append(1) 
  8.  
  9. In [3]: s 
  10.  
  11. Out[3]: [1] 
  12.  
  13. # 刪除棧內(nèi)的一個(gè)元素 
  14.  
  15. In [4]: s.pop() 
  16.  
  17. Out[4]: 1 
  18.  
  19. In [5]: s 
  20.  
  21. Out[5]: [] 
  22.  
  23. # 判斷棧是否為空 
  24.  
  25. In [6]: not s 
  26.  
  27. Out[6]: True 
  28.  
  29. In [7]: s.append(1) 
  30.  
  31. In [8]: not s 
  32.  
  33. Out[8]: False 
  34.  
  35. # 獲取棧內(nèi)元素的數(shù)量 
  36.  
  37. In [9]: len(s) 
  38.  
  39. Out[9]: 1 
  40.  
  41. In [10]: s.append(2) 
  42.  
  43. In [11]: s.append(3) 
  44.  
  45. # 取棧頂?shù)脑?nbsp;
  46.  
  47. In [12]: s[-1] 
  48.  
  49. Out[12]: 3  

一大波實(shí)例

在了解棧的基本概念之后，讓我們?cè)賮?lái)看幾個(gè)實(shí)例，以便于理解棧。

括號(hào)匹配

題目

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

正確的格式

  1. {()[()]},[{({})}] 

錯(cuò)誤的格式

  1. [(]),[()),(()} 

編寫一個(gè)函數(shù)，判斷一個(gè)表達(dá)式字符串，括號(hào)匹配是否正確

思路

  1. 創(chuàng)建一個(gè)空棧，用來(lái)存儲(chǔ)尚未找到的左括號(hào);
  2. 便利字符串，遇到左括號(hào)則壓棧，遇到右括號(hào)則出棧一個(gè)左括號(hào)進(jìn)行匹配;
  3. 在第二步驟過(guò)程中，如果空棧情況下遇到右括號(hào)，說(shuō)明缺少左括號(hào)，不匹配;
  4. 在第二步驟遍歷結(jié)束時(shí)，棧不為空，說(shuō)明缺少右括號(hào)，不匹配;

解決代碼

建議在pycharm中打斷點(diǎn)，以便于更好的理解

  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. LEFT = {'(', '[', '{'}  # 左括號(hào) 
  6.  
  7. RIGHT = {')', ']', '}'}  # 右括號(hào) 
  8.  
  9. def match(expr): 
  10.  
  11.     """ 
  12.  
  13.     :param expr:  傳過(guò)來(lái)的字符串 
  14.  
  15.     :return:  返回是否是正確的 
  16.  
  17.     """ 
  18.  
  19.     stack = []  # 創(chuàng)建一個(gè)棧 
  20.  
  21.     for brackets in expr:  # 迭代傳過(guò)來(lái)的所有字符串 
  22.  
  23.         if brackets in LEFT:  # 如果當(dāng)前字符在左括號(hào)內(nèi) 
  24.  
  25.             stack.append(brackets)  # 把當(dāng)前左括號(hào)入棧 
  26.  
  27.         elif brackets in RIGHT:  # 如果是右括號(hào) 
  28.  
  29.             if not stack or not 1 <= ord(brackets) - ord(stack[-1]) <= 2: 
  30.  
  31.                 # 如果當(dāng)前棧為空，()] 
  32.  
  33.                 # 如果右括號(hào)減去左括號(hào)的值不是小于等于2大于等于1 
  34.  
  35.                 return False  # 返回False 
  36.  
  37.             stack.pop()  # 刪除左括號(hào) 
  38.  
  39.     return not stack  # 如果棧內(nèi)沒(méi)有值則返回True，否則返回False 
  40.  
  41. result = match('[(){()}]') 
  42.  
  43. print(result)  

迷宮問(wèn)題

題目

用一個(gè)二維數(shù)組表示一個(gè)簡(jiǎn)單的迷宮，用0表示通路，用1表示阻斷，老鼠在每個(gè)點(diǎn)上可以移動(dòng)相鄰的東南西北四個(gè)點(diǎn)，設(shè)計(jì)一個(gè)算法，模擬老鼠走迷宮，找到從入口到出口的一條路徑。

如圖所示

 

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

思路

  1. 用一個(gè)棧來(lái)記錄老鼠從入口到出口的路徑
  2. 走到某點(diǎn)后，將該點(diǎn)左邊壓棧，并把該點(diǎn)值置為1，表示走過(guò)了;
  3. 從臨近的四個(gè)點(diǎn)中可到達(dá)的點(diǎn)中任意選取一個(gè)，走到該點(diǎn);
  4. 如果在到達(dá)某點(diǎn)后臨近的4個(gè)點(diǎn)都不走，說(shuō)明已經(jīng)走入死胡同，此時(shí)退棧，退回一步嘗試其他點(diǎn);
  5. 反復(fù)執(zhí)行第二、三、四步驟直到找到出口;

解決代碼

  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. def initMaze(): 
  6.  
  7.     """ 
  8.  
  9.     :return: 初始化迷宮 
  10.  
  11.     """ 
  12.  
  13.     maze = [[0] * 7 for _ in range(5 + 2)]  # 用列表解析創(chuàng)建一個(gè)7*7的二維數(shù)組，為了確保迷宮四周都是墻 
  14.  
  15.     walls = [  # 記錄了墻的位置 
  16.  
  17.         (1, 3), 
  18.  
  19.         (2, 1), (2, 5), 
  20.  
  21.         (3, 3), (3, 4), 
  22.  
  23.         (4, 2),  # (4, 3),  # 如果把(4, 3)點(diǎn)也設(shè)置為墻，那么整個(gè)迷宮是走不出去的，所以會(huì)返回一個(gè)空列表 
  24.  
  25.         (5, 4) 
  26.  
  27.     ] 
  28.  
  29.     for i in range(7):  # 把迷宮的四周設(shè)置成墻 
  30.  
  31.         maze[i][0] = maze[i][-1] = 1 
  32.  
  33.         maze[0][i] = maze[-1][i] = 1 
  34.  
  35.     for i, j in walls:  # 把所有墻的點(diǎn)設(shè)置為1 
  36.  
  37.         maze[i][j] = 1 
  38.  
  39.     return maze 
  40.  
  41. """ 
  42.  
  43. [1, 1, 1, 1, 1, 1, 1] 
  44.  
  45. [1, 0, 0, 1, 0, 0, 1] 
  46.  
  47. [1, 1, 0, 0, 0, 1, 1] 
  48.  
  49. [1, 0, 0, 1, 1, 0, 1] 
  50.  
  51. [1, 0, 1, 0, 0, 0, 1] 
  52.  
  53. [1, 0, 0, 0, 1, 0, 1] 
  54.  
  55. [1, 1, 1, 1, 1, 1, 1] 
  56.  
  57. """ 
  58.  
  59. def path(maze, start, end): 
  60.  
  61.     """ 
  62.  
  63.     :param maze: 迷宮 
  64.  
  65.     :param start: 起始點(diǎn) 
  66.  
  67.     :param end: 結(jié)束點(diǎn) 
  68.  
  69.     :return: 行走的每個(gè)點(diǎn) 
  70.  
  71.     """ 
  72.  
  73.     i, j = start  # 分解起始點(diǎn)的坐標(biāo) 
  74.  
  75.     ei, ej = end  # 分解結(jié)束點(diǎn)的左邊 
  76.  
  77.     stack = [(i, j)]  # 創(chuàng)建一個(gè)棧，并讓老鼠站到起始點(diǎn)的位置 
  78.  
  79.     maze[i][j] = 1  # 走過(guò)的路置為1 
  80.  
  81.     while stack:  # 棧不為空的時(shí)候繼續(xù)走，否則退出 
  82.  
  83.         i, j = stack[-1]  # 獲取當(dāng)前老鼠所站的位置點(diǎn) 
  84.  
  85.         if (i, j) == (ei, ej): break  # 如果老鼠找到了出口 
  86.  
  87.         for di, dj in [(0, -1), (0, 1), (-1, 0), (1, 0)]:  # 左右上下 
  88.  
  89.             if maze[i + di][j + dj] == 0:  # 如果當(dāng)前點(diǎn)可走 
  90.  
  91.                 maze[i + di][j + dj] = 1  # 把當(dāng)前點(diǎn)置為1 
  92.  
  93.                 stack.append((i + di, j + dj))  # 把當(dāng)前的位置添加到棧里面 
  94.  
  95.                 break 
  96.  
  97.         else:  # 如果所有的點(diǎn)都不可走 
  98.  
  99.             stack.pop()  # 退回上一步 
  100.  
  101.     return stack  # 如果迷宮不能走則返回空棧 
  102.  
  103. Maze = initMaze()  # 初始化迷宮 
  104.  
  105. result = path(maze=Maze, start=(1, 1), end=(5, 5))  # 老鼠開始走迷宮 
  106.  
  107. print(result) 
  108.  
  109. # [(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)]  

后綴表達(dá)式求值

題目

計(jì)算一個(gè)表達(dá)式時(shí)，編譯器通常使用后綴表達(dá)式，這種表達(dá)式不需要括號(hào)：   

 

編寫程序?qū)崿F(xiàn)后綴表達(dá)式求值函數(shù)。

思路

  1. 建立一個(gè)棧來(lái)存儲(chǔ)待計(jì)算的操作數(shù);
  2. 遍歷字符串，遇到操作數(shù)則壓入棧中，遇到操作符號(hào)則出棧操作數(shù)(n次)，進(jìn)行相應(yīng)的計(jì)算，計(jì)算結(jié)果是新的操作數(shù)壓回棧中，等待計(jì)算
  3. 按上述過(guò)程，遍歷完整個(gè)表達(dá)式，棧中只剩下最終結(jié)果;

解決代碼

  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. operators = {  # 運(yùn)算符操作表 
  6.  
  7.     '+': lambda op1, op2: op1 + op2, 
  8.  
  9.     '-': lambda op1, op2: op1 - op2, 
  10.  
  11.     '*': lambda op1, op2: op1 * op2, 
  12.  
  13.     '/': lambda op1, op2: op1 / op2, 
  14.  
  15. } 
  16.  
  17. def evalPostfix(e): 
  18.  
  19.     """ 
  20.  
  21.     :param e: 后綴表達(dá)式 
  22.  
  23.     :return: 正常情況下棧內(nèi)的第一個(gè)元素就是計(jì)算好之后的值 
  24.  
  25.     """ 
  26.  
  27.     tokens = e.split()  # 把傳過(guò)來(lái)的后綴表達(dá)式切分成列表 
  28.  
  29.     stack = [] 
  30.  
  31.     for token in tokens:  # 迭代列表中的元素 
  32.  
  33.         if token.isdigit():  # 如果當(dāng)前元素是數(shù)字 
  34.  
  35.             stack.append(int(token))  # 就追加到棧里邊 
  36.  
  37.         elif token in operators.keys():  # 如果當(dāng)前元素是操作符 
  38.  
  39.             f = operators[token]  # 獲取運(yùn)算符操作表中對(duì)應(yīng)的lambda表達(dá)式 
  40.  
  41.             op2 = stack.pop()  # 根據(jù)先進(jìn)后出的原則，先讓第二個(gè)元素出棧 
  42.  
  43.             op1 = stack.pop()  # 在讓第一個(gè)元素出棧 
  44.  
  45.             stack.append(f(op1, op2))  # 把計(jì)算的結(jié)果在放入到棧內(nèi) 
  46.  
  47.     return stack.pop()  # 返回棧內(nèi)的第一個(gè)元素 
  48.  
  49. result = evalPostfix('2 3 4 * +') 
  50.  
  51. print(result) 
  52.  
  53. # 14  

背包問(wèn)題

題目

有一個(gè)背包能裝10kg的物品，現(xiàn)在有6件物品分別為： 

 

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

解決代碼

  1. #!/use/bin/env python 
  2.  
  3. # _*_ coding:utf-8 _*_ 
  4.  
  5. def knapsack(t, w): 
  6.  
  7.     """ 
  8.  
  9.     :param t: 背包總?cè)萘?nbsp;
  10.  
  11.     :param w: 物品重量列表 
  12.  
  13.     :return: 
  14.  
  15.     """ 
  16.  
  17.     n = len(w)  # 可選的物品數(shù)量 
  18.  
  19.     stack = []  # 創(chuàng)建一個(gè)棧 
  20.  
  21.     k = 0  # 當(dāng)前所選擇的物品游標(biāo) 
  22.  
  23.     while stack or k < n:  # 棧不為空或者k<n 
  24.  
  25.         while t > 0 and k < n:  # 還有剩余空間并且有物品可裝 
  26.  
  27.             if t >= w[k]:  # 剩余空間大于等于當(dāng)前物品重量 
  28.  
  29.                 stack.append(k)  # 把物品裝備背包 
  30.  
  31.                 t -= w[k]  # 背包空間減少 
  32.  
  33.             k += 1  # 繼續(xù)向后找 
  34.  
  35.         if t == 0:  # 找到了解 
  36.  
  37.             print(stack) 
  38.  
  39.         # 回退過(guò)程 
  40.  
  41.         k = stack.pop()  # 把最后一個(gè)物品拿出來(lái) 
  42.  
  43.         t += w[k]  # 背包總?cè)萘考由蟱[k] 
  44.  
  45.         k += 1  # 裝入下一個(gè)物品 
  46.  
  47. knapsack(10, [1, 8, 4, 3, 5, 2]) 
  48.  
  49. """ 
  50.  
  51. [0, 2, 3, 5] 
  52.  
  53. [0, 2, 4] 
  54.  
  55. [1, 5] 
  56.  
  57. [3, 4, 5] 
  58.  
  59. """  
責(zé)任編輯：龐桂玉 來(lái)源： Python開發(fā)者
Python算法棧
相關(guān)推薦

2020-09-16 12:23:37

TypeScript

2023-09-25 12:23:18

棧Python

2024-05-29 11:06:10

2021-01-29 08:32:21

數(shù)據(jù)結(jié)構(gòu)數(shù)組

2011-09-07 09:21:04

2021-07-09 08:55:23

LinuxTCPIP

2017-04-24 16:24:23

JMeter實(shí)戰(zhàn)軟件性能測(cè)試

2023-04-11 08:00:00

PythonOtsu閾值算法圖像背景分割

2010-09-09 10:06:56

Zigbee協(xié)議棧加密算法

2023-05-29 07:31:35

單調(diào)棧數(shù)組循環(huán)

2021-12-15 09:21:59

Webpack 前端Sourcemap

2021-09-08 09:52:34

語(yǔ)言

2019-05-21 14:33:01

2021-03-16 14:45:39

Zabbix 5.2Grafana監(jiān)控

2024-07-15 09:58:03

OpenRestyNginx日志

2022-02-02 21:37:57

云計(jì)算全棧云運(yùn)營(yíng)

2025-02-26 05:00:00

DFS算法遞歸

2022-06-02 07:11:13

JVMJava棧

2022-02-08 07:56:38

云廠商云計(jì)算云服務(wù)

2023-02-23 08:00:00

Python機(jī)器學(xué)習(xí)編程代碼
點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)