棧（Stack）在計算機領(lǐng)域是一個被廣泛應(yīng)用的集合，棧是線性集合，訪問都嚴格地限制在一段，叫做頂（top）。
舉個例子，棧就想一摞洗干凈的盤子，你每次取一個新盤子，都是放在這一摞盤子的最上頭，當(dāng)你往里面添加盤子的時候，也是放在最上面，處在底部的盤子，你可能永遠也用不到。
棧的最常見操作，有如下兩個：
push(a) # 壓入，將a壓入的棧中
pop(） # 彈出，將棧的最后一個元素彈出
可是使用Python的列表數(shù)據(jù)結(jié)構(gòu)，來模擬棧的操作，使用append來模擬push，使用列表的pop來模擬棧的pop，但是這樣做有一個弊端，那就是列表原本自帶的操作方法同樣能夠使用，可能會造成混亂。
- 棧的實現(xiàn)
下面就通過借助Python的列表，來自定義一個棧類：
class Stack(object):
"""使用數(shù)組實現(xiàn)一個棧"""
def __init__(self):
self.data = []
def push(self, num):
"""壓棧操作"""
self.data.append(num)
def pop(self):
"""返回從棧中彈出的元素, 當(dāng)棧為空的時候, 拋出IndexError"""
return self.data.pop()
def peek(self):
"""查看當(dāng)前棧頂?shù)脑? 當(dāng)棧為空的時候, 拋出IndexError"""
return self.data[-1]
def __len__(self):
"""返回棧的長度, 調(diào)用len(obj)時會自動調(diào)用obj對象的__len__方法"""
return len(self.data)
def isEmpty(self):
"""判斷棧是否為空"""
return True if len(self.data)==0 else False
def clear(self):
"""清空棧"""
self.data = []
def __repr__(self):
"""當(dāng)前對象的表現(xiàn)形式, 在終點直接鍵入對象時會調(diào)用"""
return 'Stack_' + str(self.data)
def __str__(self):
"""當(dāng)前對象的字符串表示, 使用print(obj)時會調(diào)用"""
return 'Stack_' + str(self.data)
以上代碼實現(xiàn)了一個簡單的基于列表的棧。
- 棧的應(yīng)用
棧應(yīng)用的一個很典型的例子，就是檢查括號是否匹配。
例如： 每一個開始的[后面，都應(yīng)該跟著一個位置正確的]，并且每一個(后面，也應(yīng)該跟著一個位置正確的結(jié)束的).
-
(...)...(...)匹配 -
(...)...(...不匹配 -
)...((...)不匹配
像第三個示例中，雖然左右括號的數(shù)量是相等的，但是也是不匹配的，所以不能通過簡單的檢查數(shù)量來實現(xiàn)括號的檢測。
一種非常有效的解決方式就是使用棧： - 掃描整個字符串， 如果遇到一個開始的括號，將它壓入到棧中
- 如果遇到一個結(jié)束的括號，檢查棧頂?shù)脑?，如果是結(jié)束的括號，就將當(dāng)前括號壓入棧中，如果是開始的括號，檢查與當(dāng)前括號是否能配對，不能配對則不匹配
- 如果遇到一個結(jié)束的括號，并且當(dāng)前棧為空的話，那么也是不匹配的。
代碼實現(xiàn)如下：
def isBalance(text):
"""棧的應(yīng)用,檢查括號是否平衡"""
result_stack = Stack()
for i in text:
if i in ['{', '[', '(']:
result_stack.push(i)
elif i in ['}', ']', ')']:
# 遇到結(jié)束括號的情況
if result_stack.isEmpty():
# 如果當(dāng)前棧為空, 不匹配,返回False
return False
chFromStack = result_stack.pop()
if not ((chFromStack == '{' and i == '}' )
or (chFromStack == '[' and i == ']')
or (chFromStack == '(' and i == ')')):
# 如果不滿足匹配條件, 則返回False
return False
# 遍歷結(jié)束后, 如果結(jié)果棧為空, 則代表括號匹配, 棧不為空, 括號不匹配
return result_stack.isEmpty()
