栈的实现：Python数据结构与算法
栈（Stack）是一种特殊的线性数据结构，遵循后进先出（LIFO）的原则，即最后添加进栈的元素最先被移除。
1. 栈的基本概念
栈的操作主要有两种：压栈（Push）和弹栈（Pop）。压栈是将元素放入栈顶，弹栈是从栈顶移除元素。
# 使用Python/ target=_blank class=infotextkey>Python的列表实现一个简单的栈
stack = []
# 压栈操作
stack.Append(10)
stack.append(20)
stack.append(30)
# 此时栈的状态为 [10, 20, 30]
2. 访问栈顶元素
不移除元素，只是查看栈顶的元素。
# 查看栈顶元素
top_element = stack[-1] # 结果是 30
3. 弹栈操作
移除栈顶的元素。
# 弹栈操作
top_element = stack.pop() # 移除并返回栈顶元素，结果是 30
# 此时栈的状态为 [10, 20]
4. 栈的辅助操作
4.1 检查栈是否为空
is_empty = not bool(stack) # 如果栈为空，结果为 True
4.2 获取栈的大小
size = len(stack) # 结果是 2，因为栈中有两个元素
5. 栈的应用
栈在编程中有很多应用，以下是一些常见的例子：
-
函数调用：每当函数被调用时，都会将一个新的记录（通常称为“帧”）压入调用栈。 -
撤销操作：例如文字编辑器的撤销功能。 -
括号匹配：检查表达式中的括号是否正确匹配。
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. 实现一个完整的栈类
为了更好地使用栈，我们可以实现一个栈类，提供更多有用的方法。
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. 综合案例：简单的后缀表达式求值
后缀表达式，也称为逆波兰表示法，是一种不需要括号的数学表示法。例如，表达式 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中实现，你可以更加灵活地应用栈来解决问题。
