Python案例中的堆栈如何应用？

Python中的堆栈应用案例

堆栈（Stack）是一种后进先出（LIFO，Last In First Out）的数据结构，在Python中有广泛的应用场景,下面我通过几个典型案例来详细说明。

基础实现方式

使用列表模拟堆栈

# 使用Python列表作为堆栈
stack = []
# 入栈
stack.append('A')
stack.append('B')
stack.append('C')
print(f"当前堆栈: {stack}")  # ['A', 'B', 'C']
# 出栈
top = stack.pop()
print(f"弹出的元素: {top}")  # C
print(f"当前堆栈: {stack}")  # ['A', 'B']
# 查看栈顶元素（不弹出）
peek = stack[-1] if stack else None
print(f"栈顶元素: {peek}")  # B
# 判断堆栈是否为空
print(f"堆栈是否为空: {len(stack) == 0}")  # False

使用collections.deque实现（性能更优）

from collections import deque
# 创建堆栈
stack = deque()
# 入栈
stack.append('X')
stack.append('Y')
stack.append('Z')
# 出栈
stack.pop()  # Z

经典应用案例

案例1：括号匹配检测

def is_valid_parentheses(s: str) -> bool:
    """
    检查括号是否匹配
     "()[]{}" 返回 True, "([)]" 返回 False
    """
    stack = []
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in mapping:  # 遇到右括号
            # 如果栈为空或栈顶不匹配，则无效
            if not stack or stack.pop() != mapping[char]:
                return False
        else:  # 遇到左括号，入栈
            stack.append(char)
    # 所有左括号都被匹配后，栈应为空
    return len(stack) == 0
# 测试
print(is_valid_parentheses("()[]{}"))  # True
print(is_valid_parentheses("([)]"))    # False
print(is_valid_parentheses("{[]}"))    # True

案例2：浏览器的前进后退功能

class BrowserHistory:
    """
    模拟浏览器的前进和后退功能
    """
    def __init__(self, homepage: str):
        self.back_stack = [homepage]  # 后退堆栈
        self.forward_stack = []       # 前进堆栈
        self.current = homepage
    def visit(self, url: str) -> None:
        """访问新页面"""
        # 清空前进堆栈，因为新的访问会中断前进记录
        self.forward_stack.clear()
        # 当前页面压入后退栈
        self.back_stack.append(self.current)
        # 更新当前页面
        self.current = url
        print(f"访问: {url}")
    def back(self) -> str:
        """后退一步"""
        if not self.back_stack:
            print("无法后退")
            return self.current
        # 当前页面压入前进栈
        self.forward_stack.append(self.current)
        # 从后退栈弹出上一个页面
        self.current = self.back_stack.pop()
        print(f"后退到: {self.current}")
        return self.current
    def forward(self) -> str:
        """前进一步"""
        if not self.forward_stack:
            print("无法前进")
            return self.current
        # 当前页面压入后退栈
        self.back_stack.append(self.current)
        # 从前进栈弹出下一个页面
        self.current = self.forward_stack.pop()
        print(f"前进到: {self.current}")
        return self.current
# 使用示例
browser = BrowserHistory("google.com")
browser.visit("python.org")     # 访问: python.org
browser.visit("stackoverflow.com")  # 访问: stackoverflow.com
browser.back()                  # 后退到: python.org
browser.back()                  # 后退到: google.com
browser.forward()               # 前进到: python.org
browser.visit("github.com")     # 访问: github.com，清空前进栈

案例3：表达式求值（逆波兰表示法）

def evaluate_rpn(tokens: list) -> int:
    """
    计算逆波兰表达式
     ["2", "1", "+", "3", "*"] 表示 (2+1)*3 = 9
    """
    stack = []
    operators = {'+', '-', '*', '/'}
    for token in tokens:
        if token not in operators:
            # 数字直接入栈
            stack.append(int(token))
        else:
            # 弹出两个操作数
            b = stack.pop()  # 注意弹出顺序
            a = stack.pop()
            # 执行运算
            if token == '+':
                result = a + b
            elif token == '-':
                result = a - b
            elif token == '*':
                result = a * b
            else:  # 除法
                result = int(a / b)  # 向零取整
            # 结果入栈
            stack.append(result)
    return stack[0]
# 测试
print(evaluate_rpn(["2", "1", "+", "3", "*"]))  # 9
print(evaluate_rpn(["4", "13", "5", "/", "+"]))  # 6 (4 + 13/5)

案例4：深度优先搜索（DFS）

def dfs_maze(maze: list, start: tuple, end: tuple) -> list:
    """
    使用堆栈实现迷宫深度优先搜索
    返回从起点到终点的路径
    """
    rows, cols = len(maze), len(maze[0])
    stack = [(start, [start])]  # (当前位置, 路径)
    visited = {start}
    # 四个方向：上、下、左、右
    directions = [(-1, 0), (1, 0), (0, -1), (0, 1)]
    while stack:
        (x, y), path = stack.pop()
        # 到达终点
        if (x, y) == end:
            return path
        # 探索四个方向
        for dx, dy in directions:
            nx, ny = x + dx, y + dy
            # 检查是否在迷宫内、是否为通道、是否已访问
            if (0 <= nx < rows and 0 <= ny < cols and 
                maze[nx][ny] == 0 and (nx, ny) not in visited):
                visited.add((nx, ny))
                stack.append(((nx, ny), path + [(nx, ny)]))
    return []  # 无解
# 测试迷宫求解
maze = [
    [0, 0, 0, 0, 1],
    [1, 1, 0, 1, 0],
    [0, 0, 0, 0, 0],
    [0, 1, 1, 1, 0],
    [0, 0, 0, 0, 0]
]
start = (0, 0)
end = (4, 4)
path = dfs_maze(maze, start, end)
print(f"找到路径: {path}")

案例5：函数调用栈模拟

class CallStackSimulator:
    """
    模拟函数调用堆栈，用于调试或跟踪函数调用
    """
    def __init__(self):
        self.call_stack = []
    def call_function(self, func_name: str, **kwargs):
        """模拟函数调用"""
        call_info = {
            'function': func_name,
            'arguments': kwargs,
            'local_vars': {}
        }
        self.call_stack.append(call_info)
        print(f"→ 调用 {func_name}({kwargs})")
        return call_info
    def return_from_function(self, return_value=None):
        """模拟函数返回"""
        if not self.call_stack:
            raise RuntimeError("调用栈为空")
        call_info = self.call_stack.pop()
        func_name = call_info['function']
        print(f"← {func_name} 返回: {return_value}")
        return return_value
    def add_local_variable(self, name: str, value):
        """在当前函数作用域添加局部变量"""
        if self.call_stack:
            self.call_stack[-1]['local_vars'][name] = value
    def print_call_stack(self):
        """打印当前调用栈"""
        print("\n当前调用栈:")
        for i, call in enumerate(reversed(self.call_stack)):
            indent = "  " * (len(self.call_stack) - i - 1)
            print(f"{indent}{call['function']}({call['arguments']})")
            if call['local_vars']:
                for var, val in call['local_vars'].items():
                    print(f"{indent}  {var} = {val}")
# 使用示例
simulator = CallStackSimulator()
def factorial(n):
    simulator.call_function('factorial', n=n)
    if n <= 1:
        simulator.add_local_variable('result', 1)
        simulator.return_from_function(1)
        return 1
    result = n * factorial(n - 1)
    simulator.add_local_variable('result', result)
    simulator.return_from_function(result)
    return result
# 测试
factorial(3)
simulator.print_call_stack()

堆栈的实际应用总结

性能考虑

# 不同实现的性能对比
import time
from collections import deque
# 使用列表作为堆栈
list_stack = []
start = time.perf_counter()
for i in range(1000000):
    list_stack.append(i)
for _ in range(1000000):
    list_stack.pop()
print(f"List stack: {time.perf_counter() - start:.4f}秒")
# 使用deque作为堆栈
deque_stack = deque()
start = time.perf_counter()
for i in range(1000000):
    deque_stack.append(i)
for _ in range(1000000):
    deque_stack.pop()
print(f"Deque stack: {time.perf_counter() - start:.4f}秒")

堆栈是一种基础而强大的数据结构，掌握它在Python中的应用对于编写高效、结构清晰的代码非常有帮助。