编辑“︁栈的应用场景”︁（章节）

= 栈的应用场景 =

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

== 基本概念回顾 ==
栈的基本操作包括：
* '''push'''：将元素压入栈顶。
* '''pop'''：移除并返回栈顶元素。
* '''peek'''（或 '''top'''）：查看栈顶元素但不移除。
* '''isEmpty'''：检查栈是否为空。

== 常见应用场景 ==

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

==== 示例 ====
<syntaxhighlight lang="python">
def function_a():
    print("进入 function_a")
    function_b()
    print("退出 function_a")

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

function_a()
</syntaxhighlight>

'''输出：'''
<pre>
进入 function_a
进入 function_b
退出 function_a
</pre>

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

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

==== 示例：中缀转后缀 ====
<syntaxhighlight lang="python">
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-*+
</syntaxhighlight>

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

=== 3. 括号匹配 ===
栈可用于检查表达式中的括号是否匹配，如 <code>()</code>、<code>[]</code>、<code>{}</code>。

==== 示例 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

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

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

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

==== 示例 ====
<syntaxhighlight lang="python">
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
</syntaxhighlight>

== 高级应用 ==
=== 6. 深度优先搜索（DFS） ===
在图或树的遍历中，栈用于实现 DFS 的非递归版本。

<syntaxhighlight lang="python">
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')
</syntaxhighlight>

'''输出：'''
<pre>
A
B
D
E
F
C
</pre>

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

== 总结 ==
栈的应用场景包括但不限于：
* 函数调用与递归
* 表达式求值与转换
* 括号匹配检查
* 浏览器历史管理
* 撤销操作实现
* 深度优先搜索
* 内存管理

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

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:线性数据结构]]