Python栈模拟案例怎么编写？

本文目录导读：

1. 基本栈实现
2. 括号匹配检查
3. 表达式求值（逆波兰表达式）
4. 十进制转二进制
5. 浏览器前进后退功能
6. 栈排序
7. 汉诺塔问题
8. 关键知识点

我来介绍几个常见的Python栈模拟案例,从简单到复杂：

基本栈实现

class Stack:
    def __init__(self):
        self.items = []
    def push(self, item):
        """入栈"""
        self.items.append(item)
    def pop(self):
        """出栈"""
        if not self.is_empty():
            return self.items.pop()
        return None
    def peek(self):
        """查看栈顶元素"""
        if not self.is_empty():
            return self.items[-1]
        return None
    def is_empty(self):
        """判断是否为空"""
        return len(self.items) == 0
    def size(self):
        """获取栈大小"""
        return len(self.items)
    def __str__(self):
        return str(self.items)
# 测试
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack)  # [1, 2, 3]
print(stack.pop())  # 3
print(stack.peek())  # 2

括号匹配检查

def is_balanced(expression):
    """检查括号是否匹配"""
    stack = []
    brackets = {')': '(', '}': '{', ']': '['}
    for char in expression:
        if char in '({[':
            stack.append(char)
        elif char in ')}]':
            if not stack or stack.pop() != brackets[char]:
                return False
    return len(stack) == 0
# 测试
print(is_balanced("()"))      # True
print(is_balanced("()[]{}"))  # True
print(is_balanced("({[]})"))  # True
print(is_balanced("({[})"))   # False
print(is_balanced("("))       # False

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

def evaluate_rpn(expression):
    """计算逆波兰表达式"""
    stack = []
    operators = {'+', '-', '*', '/'}
    for token in expression.split():
        if token not in operators:
            stack.append(float(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[0]
# 测试
print(evaluate_rpn("3 4 + 5 *"))  # (3+4)*5 = 35
print(evaluate_rpn("2 3 + 4 5 + *"))  # (2+3)*(4+5) = 45

十进制转二进制

def decimal_to_binary(n):
    """十进制转二进制"""
    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 BrowserHistory:
    def __init__(self):
        self.back_stack = []  # 后退栈
        self.forward_stack = []  # 前进栈
        self.current = None
    def visit(self, url):
        """访问新页面"""
        if self.current:
            self.back_stack.append(self.current)
        self.current = url
        self.forward_stack.clear()  # 清空前栈
        print(f"访问: {url}")
    def back(self):
        """后退"""
        if not self.back_stack:
            print("无法后退")
            return
        self.forward_stack.append(self.current)
        self.current = self.back_stack.pop()
        print(f"后退到: {self.current}")
    def forward(self):
        """前进"""
        if not self.forward_stack:
            print("无法前进")
            return
        self.back_stack.append(self.current)
        self.current = self.forward_stack.pop()
        print(f"前进到: {self.current}")
# 测试
browser = BrowserHistory()
browser.visit("google.com")
browser.visit("youtube.com")
browser.visit("github.com")
browser.back()  # 后退到 youtube.com
browser.back()  # 后退到 google.com
browser.forward()  # 前进到 youtube.com

栈排序

def sort_stack(stack):
    """对栈进行排序"""
    if not stack or stack.size() <= 1:
        return stack
    temp_stack = Stack()
    while not stack.is_empty():
        temp = stack.pop()
        while not temp_stack.is_empty() and temp_stack.peek() > temp:
            stack.push(temp_stack.pop())
        temp_stack.push(temp)
    while not temp_stack.is_empty():
        stack.push(temp_stack.pop())
    return stack
# 测试
s = Stack()
[5, 2, 8, 1, 9, 3].map(lambda x: s.push(x))
print("原始栈:", s)
sorted_stack = sort_stack(s)
print("排序后:", sorted_stack)

汉诺塔问题

class HanoiTower:
    def __init__(self, n):
        self.towers = {
            'A': Stack(),
            'B': Stack(),
            'C': Stack()
        }
        # 初始化，将盘子放在A柱
        for i in range(n, 0, -1):
            self.towers['A'].push(i)
        self.moves = 0
    def move(self, n, source, target, auxiliary):
        """递归移动盘子"""
        if n == 1:
            disk = self.towers[source].pop()
            self.towers[target].push(disk)
            self.moves += 1
            print(f"移动盘子 {disk}: {source} -> {target}")
        else:
            self.move(n-1, source, auxiliary, target)
            self.move(1, source, target, auxiliary)
            self.move(n-1, auxiliary, target, source)
# 测试
hanoi = HanoiTower(3)
print("解决3层汉诺塔：")
hanoi.move(3, 'A', 'C', 'B')
print(f"总共移动了 {hanoi.moves} 步")

关键知识点

1. 栈的特性：后进先出（LIFO）
2. 基本操作：push（入栈）、pop（出栈）、peek（查看栈顶）
3. 应用场景：
   • 函数调用栈
   • 括号匹配
   • 表达式求值
   • 撤销操作
   • 深度优先搜索

这些案例涵盖了栈的基本使用和常见应用场景,可以根据实际需求选择合适的实现方式。

标签： 栈模拟 案例编程