Python栈结构案例有哪些？

Python栈结构常见案例

栈（Stack）是一种后进先出（LIFO, Last In First Out）的数据结构，以下是几个经典案例：

括号匹配检查

def is_valid_brackets(s: str) -> bool:
    """检查括号是否匹配"""
    stack = []
    bracket_map = {')': '(', ']': '[', '}': '{'}
    for char in s:
        if char in bracket_map.values():
            stack.append(char)
        elif char in bracket_map.keys():
            if not stack or stack.pop() != bracket_map[char]:
                return False
        else:
            continue
    return len(stack) == 0
# 测试
print(is_valid_brackets("()[]{}"))  # True
print(is_valid_brackets("([)]"))   # False

表达式求值（逆波兰表达式）

def eval_rpn(tokens: list) -> int:
    """计算逆波兰表达式"""
    stack = []
    operators = {'+', '-', '*', '/'}
    for token in tokens:
        if token not in operators:
            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)
            else:  # '/'
                # Python的//除法对于负数需要特殊处理
                stack.append(int(a / b))
    return stack[0]
# 测试
print(eval_rpn(["2", "1", "+", "3", "*"]))  # 9
print(eval_rpn(["4", "13", "5", "/", "+"])) # 6

浏览器的前进后退功能

class BrowserHistory:
    def __init__(self, homepage: str):
        self.history = [homepage]
        self.current = 0
    def visit(self, url: str) -> None:
        """访问新页面，清除forward历史"""
        self.history = self.history[:self.current + 1]
        self.history.append(url)
        self.current += 1
    def back(self, steps: int) -> str:
        """后退steps步"""
        self.current = max(0, self.current - steps)
        return self.history[self.current]
    def forward(self, steps: int) -> str:
        """前进steps步"""
        self.current = min(len(self.history) - 1, self.current + steps)
        return self.history[self.current]
# 测试
browser = BrowserHistory("leetcode.com")
browser.visit("google.com")
browser.visit("facebook.com")
print(browser.back(1))  # google.com
print(browser.back(1))  # leetcode.com
print(browser.forward(1))  # google.com

汉诺塔问题

def hanoi(n: int, source: str, target: str, auxiliary: str):
    """使用栈的思想解决汉诺塔问题"""
    if n == 1:
        print(f"移动盘子 1 从 {source} 到 {target}")
        return
    hanoi(n-1, source, auxiliary, target)
    print(f"移动盘子 {n} 从 {source} 到 {target}")
    hanoi(n-1, auxiliary, target, source)
# 测试
hanoi(3, 'A', 'C', 'B')

十进制转二进制

def decimal_to_binary(n: int) -> str:
    """十进制转二进制（栈实现）"""
    if n == 0:
        return "0"
    stack = []
    while n > 0:
        stack.append(str(n % 2))
        n //= 2
    return ''.join(reversed(stack))
# 测试
print(decimal_to_binary(10))  # 1010
print(decimal_to_binary(255)) # 11111111

用栈实现队列

class QueueUsingStacks:
    def __init__(self):
        self.stack_in = []
        self.stack_out = []
    def enqueue(self, x: int) -> None:
        """入队"""
        self.stack_in.append(x)
    def dequeue(self) -> int:
        """出队"""
        self._transfer()
        return self.stack_out.pop()
    def peek(self) -> int:
        """查看队首"""
        self._transfer()
        return self.stack_out[-1]
    def empty(self) -> bool:
        """判断队列是否为空"""
        return not self.stack_in and not self.stack_out
    def _transfer(self):
        """将stack_in的元素转移到stack_out"""
        if not self.stack_out:
            while self.stack_in:
                self.stack_out.append(self.stack_in.pop())
# 测试
queue = QueueUsingStacks()
queue.enqueue(1)
queue.enqueue(2)
print(queue.peek())  # 1
print(queue.dequeue())  # 1
print(queue.empty())  # False

监控系统调用栈（函数调用追踪）

import time
from contextlib import contextmanager
class CallStack:
    def __init__(self):
        self.stack = []
    @contextmanager
    def trace(self, func_name: str):
        """追踪函数调用"""
        self.stack.append(func_name)
        start_time = time.time()
        print(f"进入: {func_name}")
        print(f"当前调用栈: {' -> '.join(self.stack)}")
        try:
            yield
        finally:
            elapsed = time.time() - start_time
            print(f"退出: {func_name} (耗时: {elapsed:.3f}s)")
            self.stack.pop()
# 使用示例
def main():
    call_stack = CallStack()
    def func_a():
        with call_stack.trace("func_a"):
            time.sleep(0.1)
            func_b()
    def func_b():
        with call_stack.trace("func_b"):
            time.sleep(0.2)
            func_c()
    def func_c():
        with call_stack.trace("func_c"):
            time.sleep(0.1)
    func_a()
# main()

撤销/重做功能

class UndoRedoManager:
    def __init__(self):
        self.undo_stack = []
        self.redo_stack = []
    def add_action(self, action: str):
        """添加新操作"""
        self.undo_stack.append(action)
        self.redo_stack.clear()  # 新操作清除重做历史
        print(f"执行: {action}")
    def undo(self):
        """撤销"""
        if self.undo_stack:
            action = self.undo_stack.pop()
            self.redo_stack.append(action)
            print(f"撤销: {action}")
        else:
            print("没有可撤销的操作")
    def redo(self):
        """重做"""
        if self.redo_stack:
            action = self.redo_stack.pop()
            self.undo_stack.append(action)
            print(f"重做: {action}")
        else:
            print("没有可重做的操作")
# 测试
editor = UndoRedoManager()
editor.add_action("输入文字A")
editor.add_action("输入文字B")
editor.add_action("输入文字C")
editor.undo()  # 撤销输入文字C
editor.undo()  # 撤销输入文字B
editor.redo()  # 重做输入文字B

深度优先搜索（DFS）使用栈

def dfs_graph(graph: dict, start_node: str) -> list:
    """图的深度优先搜索（栈实现）"""
    visited = set()
    stack = [start_node]
    result = []
    while stack:
        node = stack.pop()
        if node not in visited:
            visited.add(node)
            result.append(node)
            # 将邻居节点加入栈
            for neighbor in reversed(graph.get(node, [])):
                if neighbor not in visited:
                    stack.append(neighbor)
    return result
# 测试
graph = {
    'A': ['B', 'C'],
    'B': ['A', 'D', 'E'],
    'C': ['A', 'F'],
    'D': ['B'],
    'E': ['B', 'F'],
    'F': ['C', 'E']
}
print(dfs_graph(graph, 'A'))  # ['A', 'C', 'F', 'E', 'B', 'D']

最小栈（支持获取最小值）

class MinStack:
    def __init__(self):
        self.stack = []  # (value, current_min)
    def push(self, val: int) -> None:
        """入栈"""
        if not self.stack:
            self.stack.append((val, val))
        else:
            current_min = min(val, self.stack[-1][1])
            self.stack.append((val, current_min))
    def pop(self) -> int:
        """出栈"""
        if not self.stack:
            raise IndexError("空栈")
        val, _ = self.stack.pop()
        return val
    def top(self) -> int:
        """查看栈顶元素"""
        if not self.stack:
            raise IndexError("空栈")
        return self.stack[-1][0]
    def get_min(self) -> int:
        """获取最小值"""
        if not self.stack:
            raise IndexError("空栈")
        return self.stack[-1][1]
# 测试
min_stack = MinStack()
min_stack.push(-2)
min_stack.push(0)
min_stack.push(-3)
print(min_stack.get_min())  # -3
min_stack.pop()
print(min_stack.top())      # 0
print(min_stack.get_min())  # -2

这些案例展示了栈在不同领域的应用,核心都是利用其后进先出的特性来解决特定问题。

标签： 案例