栈的应用场景
栈（Stack）是一种线性数据结构，遵循后进先出（LIFO）的原则。这意味着最后进入栈的元素会最先被移除。栈的操作主要包括入栈（push）和出栈（pop），以及查看栈顶元素（peek）。由于其独特的特性，栈在编程中有许多实际应用场景。
本文将介绍栈的常见应用场景，并通过代码示例和实际案例帮助你更好地理解栈的作用。
1. 函数调用栈
在编程中，函数调用是栈的典型应用之一。每当一个函数被调用时，系统会将该函数的执行上下文（如局部变量、返回地址等）压入栈中。当函数执行完毕后，系统会从栈中弹出该上下文，并返回到调用函数的位置。
示例
以下是一个简单的递归函数调用栈的示例：
def factorial(n):
if n == 0:
return 1
else:
return n * factorial(n - 1)
print(factorial(5)) # 输出: 120
在这个例子中，每次调用 factorial 函数时，当前的 n 值会被压入栈中。当递归到达 n == 0 时，栈中的值会依次弹出并计算阶乘。
2. 表达式求值
栈可以用于解析和计算数学表达式，尤其是中缀表达式（如 3 + 4 * 2）。通过使用栈，我们可以将中缀表达式转换为后缀表达式（逆波兰表达式），然后利用栈进行计算。
示例
以下是一个简单的后缀表达式求值示例：
def evaluate_postfix(expression):
stack = []
for token in expression.split():
if token.isdigit():
stack.append(int(token))
else:
b = stack.pop()
a = stack.pop()
if token == '+':
stack.append(a + b)
elif token == '-':
stack.append(a - b)
elif token == '*':
stack.append(a * b)
elif token == '/':
stack.append(a // b)
return stack.pop()
print(evaluate_postfix("3 4 2 * +")) # 输出: 11
在这个例子中，栈用于存储操作数，并在遇到运算符时进行计算。
3. 括号匹配
栈可以用于检查表达式中的括号是否匹配。例如，检查一个字符串中的 {}、[] 和 () 是否成对出现。
示例
以下是一个括号匹配的示例：
def is_balanced(expression):
stack = []
brackets = {')': '(', '}': '{', ']': '['}
for char in expression:
if char in brackets.values():
stack.append(char)
elif char in brackets.keys():
if not stack or stack.pop() != brackets[char]:
return False
return not stack
print(is_balanced("{[()]}")) # 输出: True
print(is_balanced("{[(])}")) # 输出: False
在这个例子中，栈用于存储左括号，并在遇到右括号时检查是否匹配。
4. 浏览器的前进与后退功能
浏览器的前进和后退功能是栈的另一个典型应用。每次访问一个新页面时，当前页面的 URL 会被压入栈中。当用户点击“后退”按钮时，系统会从栈中弹出上一个页面的 URL。
示例
以下是一个简单的浏览器历史记录模拟：
class BrowserHistory:
def __init__(self):
self.back_stack = []
self.forward_stack = []
def visit(self, url):
self.back_stack.append(url)
self.forward_stack = []
def back(self):
if len(self.back_stack) > 1:
self.forward_stack.append(self.back_stack.pop())
return self.back_stack[-1]
return None
def forward(self):
if self.forward_stack:
self.back_stack.append(self.forward_stack.pop())
return self.back_stack[-1]
return None
history = BrowserHistory()
history.visit("page1.com")
history.visit("page2.com")
print(history.back()) # 输出: page1.com
print(history.forward()) # 输出: page2.com
在这个例子中，back_stack 用于存储访问历史，forward_stack 用于存储“后退”后的页面。
5. 撤销操作
许多应用程序（如文本编辑器）提供了撤销（Undo）功能，这也是栈的应用之一。每次用户执行一个操作时，该操作会被压入栈中。当用户选择撤销时，系统会从栈中弹出最近的操作并执行反向操作。
总结
栈是一种简单但功能强大的数据结构，广泛应用于编程的各个领域。通过本文的介绍，你应该对栈的常见应用场景有了更深入的理解，包括函数调用、表达式求值、括号匹配、浏览器历史记录和撤销操作等。
如果你想进一步练习栈的应用，可以尝试以下任务：
- 实现一个简单的计算器，支持加减乘除运算。
- 编写一个程序，检查 HTML 文档中的标签是否匹配。
- 模拟一个文本编辑器的撤销功能。
希望本文对你理解栈的应用场景有所帮助！如果你有任何问题或建议，欢迎在评论区留言。