Python栈案例如何实现栈结构操作

wen python案例 2026-06-30 29

Python栈案例：从零实现栈结构操作与实战解析

目录导读

栈数据结构核心概念 – 什么是栈？LIFO原则图解
Python手动实现栈类 – 基于列表与链表两种方案
关键操作详解 – push、pop、peek、is_empty、size
四个经典案例实战 – 括号匹配、进制转换、网页后退、表达式求值
性能对比与最佳实践 – 列表 vs collections.deque
常见问题问答 – 面试高频考点解析

栈数据结构核心概念

栈（Stack）是一种受限的线性表，只允许在同一端进行插入和删除操作，这一端称为栈顶，另一端称为栈底，栈遵循后进先出（LIFO, Last In First Out）原则。

Python栈案例如何实现栈结构操作

形象比喻：一叠盘子，你只能从最上面取盘子，也只能把新盘子放在最上面。

栈的核心特征

插入操作：入栈（push）
删除操作：出栈（pop）
栈顶访问：peek（查看但不移除）
所有操作的时间复杂度均为 O(1)

Python手动实现栈类

基于列表（list）实现

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()  # 从尾部移除 = 出栈
        raise IndexError("pop from empty stack")
    def peek(self):
        if not self.is_empty():
            return self.items[-1]
        raise IndexError("peek from empty stack")
    def is_empty(self):
        return len(self.items) == 0
    def size(self):
        return len(self.items)

基于collections.deque（双端队列）

from collections import deque
class StackDeque:
    def __init__(self):
        self.items = deque()
    def push(self, item):
        self.items.append(item)
    def pop(self):
        return self.items.pop()
    def peek(self):
        return self.items[-1]
    def is_empty(self):
        return len(self.items) == 0
    def size(self):
        return len(self.items)

性能提示：若只需栈操作，list足够高效；若需要频繁在两端操作，deque更优。

关键操作详解与时间复杂度

操作	描述	时间复杂度
`push(x)`	将x压入栈顶	O(1)
`pop()`	弹出并返回栈顶元素	O(1)
`peek()`	返回栈顶元素但不移除	O(1)
`is_empty()`	检查栈是否为空	O(1)
`size()`	返回栈中元素个数	O(1)

注意：若使用list且栈顶在头部，则pop(0)的时间复杂度为O(n)，因此永远选择在尾部操作。

四个经典案例实战

案例1：括号匹配检测

def is_balanced(expr):
    stack = Stack()
    mapping = {')': '(', ']': '[', '}': '{'}
    for char in expr:
        if char in mapping.values():
            stack.push(char)
        elif char in mapping:
            if stack.is_empty() or stack.pop() != mapping[char]:
                return False
    return stack.is_empty()
print(is_balanced("({[]})"))  # True
print(is_balanced("([)]"))    # False

原理：遇到左括号入栈，遇到右括号与栈顶匹配。

案例2：十进制转二进制

def decimal_to_binary(num):
    stack = Stack()
    while num > 0:
        stack.push(num % 2)
        num //= 2
    return ''.join(str(stack.pop()) for _ in range(stack.size()))
print(decimal_to_binary(10))  # 1010

原理：不断对2取余并压栈，最后依次弹出。

案例3：模拟浏览器后退功能

class BrowserHistory:
    def __init__(self):
        self.back_stack = Stack()
        self.forward_stack = Stack()
        self.current = None
    def visit(self, url):
        if self.current:
            self.back_stack.push(self.current)
        self.current = url
        self.forward_stack = Stack()  # 清空前进
    def back(self):
        if not self.back_stack.is_empty():
            self.forward_stack.push(self.current)
            self.current = self.back_stack.pop()
        return self.current
    def forward(self):
        if not self.forward_stack.is_empty():
            self.back_stack.push(self.current)
            self.current = self.forward_stack.pop()
        return self.current

案例4：中缀表达式转后缀（逆波兰）

def infix_to_postfix(expr):
    precedence = {'+': 1, '-': 1, '*': 2, '/': 2, '(': 0}
    stack = Stack()
    output = []
    for token in expr.split():
        if token.isdigit():
            output.append(token)
        elif token == '(':
            stack.push(token)
        elif token == ')':
            while not stack.is_empty() and stack.peek() != '(':
                output.append(stack.pop())
            stack.pop()  # 移除 '('
        else:  # 运算符
            while (not stack.is_empty() and 
                   precedence[stack.peek()] >= precedence[token]):
                output.append(stack.pop())
            stack.push(token)
    while not stack.is_empty():
        output.append(stack.pop())
    return ' '.join(output)
print(infix_to_postfix("3 + 5 * ( 2 - 8 )"))  # 3 5 2 8 - * +

性能对比与最佳实践

实现方式	优点	缺点
`list`实现	简单直观，大多数场景足够	大量动态扩容时性能波动
`deque`实现	线程安全，内存连续，访问快	需要额外导入模块
链表实现	无容量限制，内存稳定	占用更多内存，非连续缓存不友好