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