棧的實(shí)現(xiàn)：Python數(shù)據(jù)結(jié)構(gòu)與算法
作者：子午Python
棧是一個(gè)非常實(shí)用的數(shù)據(jù)結(jié)構(gòu)，可以幫助我們解決許多編程問(wèn)題。通過(guò)理解其后進(jìn)先出的特性和如何在Python中實(shí)現(xiàn)，你可以更加靈活地應(yīng)用棧來(lái)解決問(wèn)題。
棧（Stack）是一種特殊的線(xiàn)性數(shù)據(jù)結(jié)構(gòu)，遵循后進(jìn)先出（LIFO）的原則，即最后添加進(jìn)棧的元素最先被移除。
1. 棧的基本概念
棧的操作主要有兩種：壓棧（Push）和彈棧（Pop）。壓棧是將元素放入棧頂，彈棧是從棧頂移除元素。
# 使用Python的列表實(shí)現(xiàn)一個(gè)簡(jiǎn)單的棧
stack = []
# 壓棧操作
stack.append(10)
stack.append(20)
stack.append(30)
# 此時(shí)棧的狀態(tài)為 [10, 20, 30]2. 訪(fǎng)問(wèn)棧頂元素
不移除元素，只是查看棧頂?shù)脑亍?/p>
# 查看棧頂元素
top_element = stack[-1] # 結(jié)果是 303. 彈棧操作
移除棧頂?shù)脑亍?/p>
# 彈棧操作
top_element = stack.pop() # 移除并返回棧頂元素，結(jié)果是 30
# 此時(shí)棧的狀態(tài)為 [10, 20]4. 棧的輔助操作
(1) 檢查棧是否為空
is_empty = not bool(stack) # 如果棧為空，結(jié)果為 True(2) 獲取棧的大小
size = len(stack) # 結(jié)果是 2，因?yàn)闂Ｖ杏袃蓚€(gè)元素5. 棧的應(yīng)用
棧在編程中有很多應(yīng)用，以下是一些常見(jiàn)的例子：
- 函數(shù)調(diào)用：每當(dāng)函數(shù)被調(diào)用時(shí)，都會(huì)將一個(gè)新的記錄（通常稱(chēng)為“幀”）壓入調(diào)用棧。
- 撤銷(xiāo)操作：例如文字編輯器的撤銷(xiāo)功能。
- 括號(hào)匹配：檢查表達(dá)式中的括號(hào)是否正確匹配。
括號(hào)匹配示例：
def is_parentheses_balanced(expr):
stack = []
mapping = {")": "(", "}": "{", "]": "["}
for char in expr:
if char in mapping.values():
stack.append(char)
elif char in mapping.keys():
if stack == [] or mapping[char] != stack.pop():
return False
return stack == []
# 使用示例
expr = "{[()]}"
print(is_parentheses_balanced(expr)) # True，因?yàn)槔ㄌ?hào)是匹配的6. 實(shí)現(xiàn)一個(gè)完整的棧類(lèi)
為了更好地使用棧，我們可以實(shí)現(xiàn)一個(gè)棧類(lèi)，提供更多有用的方法。
class Stack:
def __init__(self):
self.items = []
def push(self, item):
"""壓棧操作"""
self.items.append(item)
def pop(self):
"""彈棧操作，返回棧頂元素"""
return self.items.pop()
def peek(self):
"""查看棧頂元素，不移除"""
return self.items[-1]
def is_empty(self):
"""檢查棧是否為空"""
return len(self.items) == 0
def size(self):
"""返回棧的大小"""
return len(self.items)
# 使用棧類(lèi)
s = Stack()
s.push(10)
s.push(20)
print(s.peek()) # 20
print(s.pop()) # 207. 綜合案例：簡(jiǎn)單的后綴表達(dá)式求值
后綴表達(dá)式，也稱(chēng)為逆波蘭表示法，是一種不需要括號(hào)的數(shù)學(xué)表示法。例如，表達(dá)式 3 + 4 在后綴表達(dá)式中表示為 3 4 +。 我們可以使用棧來(lái)計(jì)算后綴表達(dá)式的值。
def evaluate_postfix(expr):
stack = Stack()
tokens = expr.split()
for token in tokens:
if token.isdigit():
stack.push(int(token))
else:
operand2 = stack.pop()
operand1 = stack.pop()
if token == "+":
stack.push(operand1 + operand2)
elif token == "-":
stack.push(operand1 - operand2)
elif token == "*":
stack.push(operand1 * operand2)
elif token == "/":
stack.push(operand1 / operand2)
return stack.pop()
# 使用示例
expr = "3 4 + 2 *"
print(evaluate_postfix(expr)) # 結(jié)果是 14，因?yàn)?(3 + 4) * 2 = 14小結(jié)
棧是一個(gè)非常實(shí)用的數(shù)據(jù)結(jié)構(gòu)，可以幫助我們解決許多編程問(wèn)題。通過(guò)理解其后進(jìn)先出的特性和如何在Python中實(shí)現(xiàn)，你可以更加靈活地應(yīng)用棧來(lái)解決問(wèn)題。
責(zé)任編輯：趙寧寧
來(lái)源：
子午Python
