棧的實現：Python數據結構與算法
作者：子午Python
棧是一個非常實用的數據結構，可以幫助我們解決許多編程問題。通過理解其后進先出的特性和如何在Python中實現，你可以更加靈活地應用棧來解決問題。
棧（Stack）是一種特殊的線性數據結構，遵循后進先出（LIFO）的原則，即最后添加進棧的元素最先被移除。
1. 棧的基本概念
棧的操作主要有兩種：壓棧（Push）和彈棧（Pop）。壓棧是將元素放入棧頂，彈棧是從棧頂移除元素。
# 使用Python的列表實現一個簡單的棧
stack = []
# 壓棧操作
stack.append(10)
stack.append(20)
stack.append(30)
# 此時棧的狀態為 [10, 20, 30]2. 訪問棧頂元素
不移除元素，只是查看棧頂的元素。
# 查看棧頂元素
top_element = stack[-1] # 結果是 303. 彈棧操作
移除棧頂的元素。
# 彈棧操作
top_element = stack.pop() # 移除并返回棧頂元素，結果是 30
# 此時棧的狀態為 [10, 20]4. 棧的輔助操作
(1) 檢查棧是否為空
is_empty = not bool(stack) # 如果棧為空，結果為 True(2) 獲取棧的大小
size = len(stack) # 結果是 2，因為棧中有兩個元素5. 棧的應用
棧在編程中有很多應用，以下是一些常見的例子：
- 函數調用：每當函數被調用時，都會將一個新的記錄（通常稱為“幀”）壓入調用棧。
- 撤銷操作：例如文字編輯器的撤銷功能。
- 括號匹配：檢查表達式中的括號是否正確匹配。
括號匹配示例：
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，因為括號是匹配的6. 實現一個完整的棧類
為了更好地使用棧，我們可以實現一個棧類，提供更多有用的方法。
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)
# 使用棧類
s = Stack()
s.push(10)
s.push(20)
print(s.peek()) # 20
print(s.pop()) # 207. 綜合案例：簡單的后綴表達式求值
后綴表達式，也稱為逆波蘭表示法，是一種不需要括號的數學表示法。例如，表達式 3 + 4 在后綴表達式中表示為 3 4 +。 我們可以使用棧來計算后綴表達式的值。
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)) # 結果是 14，因為 (3 + 4) * 2 = 14小結
棧是一個非常實用的數據結構，可以幫助我們解決許多編程問題。通過理解其后進先出的特性和如何在Python中實現，你可以更加靈活地應用棧來解決問題。
責任編輯：趙寧寧
來源：
子午Python
