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

如下圖所示

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

棧的接口

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

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

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

# 創(chuàng)建一個棧

In[1]: s = []

# 往棧內(nèi)添加一個元素

In[2]: s.append(1)

In[3]: s

Out[3]: [1]

# 刪除棧內(nèi)的一個元素

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

# 獲取棧內(nèi)元素的數(shù)量

In[9]: len(s)

Out[9]: 1

In[10]: s.append(2)

In[11]: s.append(3)

# 取棧頂?shù)脑?/p>

In[12]: s[-1]

Out[12]: 3

一大波實(shí)例

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

括號匹配

題目

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

正確的格式

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

錯誤的格式

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

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

思路

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

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

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

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

解決代碼

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

#!/use/bin/env python

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

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

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

defmatch(expr):

"""

:param expr:傳過來的字符串

:return:返回是否是正確的

"""

stack = []# 創(chuàng)建一個棧

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

ifbrackets inLEFT:# 如果當(dāng)前字符在左括號內(nèi)

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

elifbrackets inRIGHT:# 如果是右括號

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

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

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

returnFalse# 返回False

stack.pop()# 刪除左括號

returnnotstack# 如果棧內(nèi)沒有值則返回True，否則返回False

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

print(result)

迷宮問題

題目

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

如圖所示

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

思路

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

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

從臨近的四個點(diǎn)中可到達(dá)的點(diǎn)中任意選取一個，走到該點(diǎn)；

如果在到達(dá)某點(diǎn)后臨近的4個點(diǎn)都不走，說明已經(jīng)走入死胡同，此時退棧，退回一步嘗試其他點(diǎn)；

反復(fù)執(zhí)行第二、三、四步驟直到找到出口；

解決代碼

#!/use/bin/env python

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

definitMaze():

"""

:return: 初始化迷宮

"""

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

walls = [# 記錄了墻的位置

(1,3),

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

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

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

(5,4)

]

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

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

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

fori,jinwalls:# 把所有墻的點(diǎn)設(shè)置為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: 起始點(diǎn)

:param end: 結(jié)束點(diǎn)

:return: 行走的每個點(diǎn)

"""

i,j = start# 分解起始點(diǎn)的坐標(biāo)

ei,ej = end# 分解結(jié)束點(diǎn)的左邊

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

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

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

i,j = stack[-1]# 獲取當(dāng)前老鼠所站的位置點(diǎn)

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

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

ifmaze[i + di][j + dj] == 0:# 如果當(dāng)前點(diǎn)可走

maze[i + di][j + dj] = 1# 把當(dāng)前點(diǎn)置為1

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

break

else:# 如果所有的點(diǎn)都不可走

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)]

后綴表達(dá)式求值

題目

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

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

思路

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

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

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

解決代碼

#!/use/bin/env python

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

operators = {# 運(yùn)算符操作表

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

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

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

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

}

defevalPostfix(e):

"""

:param e: 后綴表達(dá)式

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

"""

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

stack = []

fortokenintokens:# 迭代列表中的元素

iftoken.isdigit():# 如果當(dāng)前元素是數(shù)字

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

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

f = operators[token]# 獲取運(yùn)算符操作表中對應(yīng)的lambda表達(dá)式

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

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

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

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

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

print(result)

# 14

背包問題

題目

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

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

解決代碼

#!/use/bin/env python

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

defknapsack(t,w):

"""

:param t: 背包總?cè)萘?/p>

:param w: 物品重量列表

:return:

"""

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

stack = []# 創(chuàng)建一個棧

k = 0# 當(dāng)前所選擇的物品游標(biāo)

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

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

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

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

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

k += 1# 繼續(xù)向后找

ift == 0:# 找到了解

print(stack)

# 回退過程

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

t += w[k]# 背包總?cè)萘考由蟱[k]

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

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

"""

[0, 2, 3, 5]

[0, 2, 4]

[1, 5]

[3, 4, 5]

"""