堆棧（英語(yǔ)：stack）又稱為棧或堆疊澡腾，是計(jì)算機(jī)科學(xué)中一種特殊的串列形式的抽象數(shù)據(jù)類型，其特殊之處在于只能允許在鏈表或數(shù)組的一端進(jìn)行加入數(shù)據(jù)（英語(yǔ)：push）和輸出數(shù)據(jù)（英語(yǔ)：pop）的運(yùn)算。由于堆棧數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行操作返奉，因而按照后進(jìn)先出（LIFO, Last In First Out）的原理運(yùn)作。 來(lái)自維基百科
抽象數(shù)據(jù)描述如下：
ADT Stack:
Stack(self) # 創(chuàng)建空棧
is_empty(self) # 判斷棧是否為空
push(self, elem) # 將元素elem加入棧
pop(self) # 刪除棧中最后加入的元素并將其返回
top(self) # 取得棧中最后壓入的元素吗氏，不刪除
棧大多的實(shí)現(xiàn)是采用線性表
順序表?xiàng)?shí)現(xiàn)
- 定義一個(gè)異常類
class StackUnderflow(ValueError): # 棧下溢(空棧訪問)
pass
-
Python的 list 是線性表的一種實(shí)現(xiàn)芽偏，在此使用 list 作為棧元素存儲(chǔ)區(qū)，整體實(shí)現(xiàn)如下：
class SStack:
def __init__(self):
self._elems = [] # 使用list存儲(chǔ)棧元素
def is_empty(self):
return self._elems == []
def push(self, elem):
self._elems.append(elem)
def pop(self):
if self._elems == []:
raise StackUnderflow("in SStack.pop()")
return self._elems.pop()
def top(self):
if self._elems == []:
raise StackUnderflow("in SStack.top()")
return self._elems[-1]
- 簡(jiǎn)單的書寫測(cè)試用例
if __name__ == '__main__':
s = SStack()
assert s.is_empty() is True
try:
s.pop()
except StackUnderflow:
print("StackUnderflow")
s.push(123)
assert s.is_empty() is not True
assert s.pop() == 123
簡(jiǎn)單應(yīng)用：括號(hào)匹配問題
給定一個(gè)字符串弦讽，其中的字符只包含三種括號(hào)：花括號(hào){ }污尉、中括號(hào)[ ]、圓括號(hào)( )往产，即它僅由( ) [ ] { }這六個(gè)字符組成被碗。
設(shè)計(jì)算法，判斷該字符串是否有效仿村，即字符串中括號(hào)是否匹配锐朴。括號(hào)匹配要求括號(hào)必須以正確的順序配對(duì)，如{ [ ] ( ) }或[ ( { } [ ] ) ]等為正確的格式蔼囊，而[ ( ] )或{ [ ( ) }或( { } ] )均為不正確的格式焚志。
完整的括號(hào)匹配算法流程如下：
- 從前向后掃描字符串，遇到無(wú)關(guān)字符則跳過(guò)畏鼓；
- 遇到左括號(hào) x酱酬，就把 x 壓棧；
- 遇到右括號(hào) y:
- 如果發(fā)現(xiàn)棧頂元素x和該括號(hào)y匹配云矫，則棧頂元素出棧岳悟，繼續(xù)判斷下一個(gè)字符；
- 如果棧頂元素x和該括號(hào)y不匹配，字符串不匹配贵少；
- 如果棧為空呵俏，字符串不匹配；
- 掃描完成后滔灶，如果棧恰好為空普碎，則字符串匹配，否則录平，字符串不匹配麻车。
代碼如下：
def check_parens(text):
stack = SStack()
left_parens = "([{"
right_parens = ")]}"
parens = {")":"(", "]":"[", "}":"{"}
for i in text:
if i in left_parens:
stack.push(i)
elif i in right_parens:
if stack.is_empty():
return False
if parens[i] != stack.pop():
return False
if stack.is_empty():
return True
return False
if __name__ == '__main__':
assert check_parens("[{1232}]") is True
assert check_parens("[{[}]") is False
assert check_parens("[{123444]}]") is False
assert check_parens("][{}]") is False
棧與函數(shù)調(diào)用經(jīng)典問題之簡(jiǎn)單背包問題
遞歸實(shí)現(xiàn)如下：
# 簡(jiǎn)單背包問題
def knap_rec(weight, wlist, n):
if weight == 0:
return True
if weight < 0 or (weight > 0 and n < 1):
return False
if knap_rec(weight - wlist[n-1], wlist, n-1):
return True
if knap_rec(weight, wlist, n-1):
return True
else:
return False
assert knap_rec(100, [90, 40, 20, 10, 50], 4) is True
棧實(shí)現(xiàn)如下：
# 可利用回溯法的設(shè)計(jì)思想來(lái)解決背包問題。
# 首先將 n 件物品排成一列斗这，依次選榷；若裝入某件物品后表箭，背包內(nèi)物品的總質(zhì)量不超過(guò)背包最大裝載質(zhì)量時(shí)赁咙，則裝入（進(jìn)棧）；
# 否則放棄這件物品的選擇免钻，選擇下一件物品試探彼水，直至裝入的物品總和正好是背包的最大轉(zhuǎn)載質(zhì)量為止。這時(shí)我們稱背包裝滿极舔。
# 若裝入若干物品的背包沒有滿凤覆，而且又無(wú)其他物品可以選入背包，說(shuō)明已裝入背包的物品中有不合格者拆魏，需從背包中取出最后裝入的物品（退棧）
# 然后在未裝入的物品中挑選盯桦，重復(fù)此過(guò)程，直至裝滿背包（有解）渤刃，或無(wú)物品可選（無(wú)解）為止拥峦。
def knapstack(weight, wlist):
n = len(wlist) # 可選的物品數(shù)量
stack = SStack() # 創(chuàng)建一個(gè)棧
k = 0 # 當(dāng)前所選擇的物品游標(biāo)
while stack.is_empty() is not True or k < n: # 棧不為空或者k<n
while weight > 0 and k < n: # 還有剩余空間并且有物品可裝
if weight >= wlist[k]: # 剩余空間大于等于當(dāng)前物品重量
print(wlist[k])
stack.push(k) # 把物品裝備背包
weight -= wlist[k] # 背包空間減少
k += 1 # 繼續(xù)向后找
if weight == 0: # 找到解
print(stack._elems)
# return True
# 回退過(guò)程
k = stack.pop() # 把最后一個(gè)物品拿出來(lái)
print(wlist[k])
weight += wlist[k] # 背包總?cè)萘考由蟱[k]
print(weight)
k += 1 # 裝入下一個(gè)物品
