栈的应用场景

栈的应用场景

栈（Stack）是一种遵循后进先出（LIFO, Last In First Out）原则的线性数据结构。它在计算机科学中有广泛的应用，从函数调用到表达式求值，再到浏览器的“后退”功能。本节将详细介绍栈的常见应用场景，并提供代码示例和实际案例。

基本概念回顾

栈的基本操作包括：

• push：将元素压入栈顶。
• pop：移除并返回栈顶元素。
• peek（或 top）：查看栈顶元素但不移除。
• isEmpty：检查栈是否为空。

常见应用场景

1. 函数调用栈

在程序执行过程中，函数调用（包括递归）依赖于栈来管理调用顺序。每次调用函数时，当前函数的局部变量、返回地址等信息被压入栈；函数返回时，这些信息被弹出。

示例

def function_a():
    print("进入 function_a")
    function_b()
    print("退出 function_a")

def function_b():
    print("进入 function_b")

function_a()

输出：

进入 function_a
进入 function_b
退出 function_a

解释： 调用顺序为： 1. function_a 被调用，其上下文入栈。 2. function_a 调用 function_b，function_b 的上下文入栈。 3. function_b 执行完毕，其上下文出栈。 4. function_a 继续执行，最后其上下文出栈。

2. 表达式求值

栈可用于解析和计算数学表达式，如中缀表达式转后缀表达式（逆波兰表示法）或直接求值。

示例：中缀转后缀

def infix_to_postfix(expression):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '^': 3}
    stack = []
    output = []
    
    for char in expression:
        if char.isalnum():
            output.append(char)
        elif char == '(':
            stack.append(char)
        elif char == ')':
            while stack and stack[-1] != '(':
                output.append(stack.pop())
            stack.pop()  # 移除 '('
        else:
            while stack and stack[-1] != '(' and precedence[char] <= precedence.get(stack[-1], 0):
                output.append(stack.pop())
            stack.append(char)
    
    while stack:
        output.append(stack.pop())
    
    return ''.join(output)

print(infix_to_postfix("a+b*(c^d-e)"))  # 输出: abcd^e-*+

解释： 1. 操作数直接输出。 2. 操作符根据优先级入栈或弹出。 3. 括号内的表达式优先处理。

3. 括号匹配

栈可用于检查表达式中的括号是否匹配，如 ()、[]、{}。

示例

def is_balanced(expr):
    stack = []
    pairs = {')': '(', ']': '[', '}': '{'}
    
    for char in expr:
        if char in pairs.values():
            stack.append(char)
        elif char in pairs:
            if not stack or stack.pop() != pairs[char]:
                return False
    return not stack

print(is_balanced("{[()]}"))  # 输出: True
print(is_balanced("{[)]}"))   # 输出: False

4. 浏览器后退功能

浏览器的“后退”按钮使用栈记录访问历史。每次访问新页面时，URL 入栈；点击“后退”时，URL 出栈并加载前一个页面。

graph LR A[访问页面1] --> B[访问页面2] B --> C[访问页面3] C --> D[点击后退] D --> E[返回页面2]

5. 撤销操作（Undo）

文本编辑器（如 Word）的“撤销”功能使用栈记录操作。每次编辑操作（如输入、删除）被压入栈；撤销时弹出并反向执行。

示例

class TextEditor:
    def __init__(self):
        self.text = ""
        self.undo_stack = []
    
    def write(self, chars):
        self.undo_stack.append(('delete', len(chars)))
        self.text += chars
    
    def undo(self):
        if not self.undo_stack:
            return
        action, data = self.undo_stack.pop()
        if action == 'delete':
            self.text = self.text[:-data]

editor = TextEditor()
editor.write("Hello")
editor.write(" World")
print(editor.text)  # 输出: Hello World
editor.undo()
print(editor.text)  # 输出: Hello

高级应用

6. 深度优先搜索（DFS）

在图或树的遍历中，栈用于实现 DFS 的非递归版本。

def dfs(graph, start):
    visited = set()
    stack = [start]
    
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            print(node)
            stack.extend(reversed(graph[node]))  # 保证顺序

graph = {
    'A': ['B', 'C'],
    'B': ['D', 'E'],
    'C': ['F'],
    'D': [],
    'E': ['F'],
    'F': []
}
dfs(graph, 'A')

输出：

A
B
D
E
F
C

7. 内存管理

栈内存用于存储局部变量和函数调用，由系统自动管理。堆内存（动态分配）需手动管理（如 C 的 malloc）。

总结

栈的应用场景包括但不限于：

• 函数调用与递归
• 表达式求值与转换
• 括号匹配检查
• 浏览器历史管理
• 撤销操作实现
• 深度优先搜索
• 内存管理

理解栈的原理和场景有助于编写高效、清晰的代码。