当前位置:首页 > Python > 正文

Python栈操作详解:从入门到实战 | Python算法教程

Python栈操作详解:从基础到实战应用

掌握栈数据结构在Python中的实现与应用

什么是栈?

栈(Stack)是一种遵循后进先出(LIFO)原则的数据结构。想象一下堆叠盘子——你总是把新盘子放在顶部,取用时也是从顶部开始拿取。

在计算机科学中,栈被广泛应用于:

  • 函数调用管理
  • 表达式求值(如括号匹配)
  • 撤销(Undo)机制
  • 浏览器的前进/后退功能
  • 深度优先搜索算法

在Python中实现栈

Python没有专门的栈数据结构,但我们可以使用内置的listcollections.deque来实现栈的功能。

1. 使用列表(list)实现栈

列表是最简单直接的栈实现方式:


# 创建空栈
stack = []

# 压栈操作(添加元素到栈顶)
stack.append(1)  # 栈:[1]
stack.append(2)  # 栈:[1, 2]
stack.append(3)  # 栈:[1, 2, 3]

# 弹栈操作(移除并返回栈顶元素)
top = stack.pop()  # 返回3,栈变为:[1, 2]

# 查看栈顶元素(不移除)
peek = stack[-1]   # 返回2,栈不变:[1, 2]

# 检查栈是否为空
is_empty = len(stack) == 0  # 返回False

# 获取栈的大小
size = len(stack)  # 返回2
                

2. 使用collections.deque实现栈

对于需要更高性能的场景(特别是大型数据集),使用deque是更好的选择:


from collections import deque

# 创建空栈
stack = deque()

# 压栈操作
stack.append(10)  # 栈:[10]
stack.append(20)  # 栈:[10, 20]

# 弹栈操作
top = stack.pop()  # 返回20

# 查看栈顶元素
peek = stack[-1]   # 返回10

# 检查栈是否为空
is_empty = len(stack) == 0  # 返回False
                

栈的基本操作

压栈 (Push)

将新元素添加到栈的顶部

stack.append(element)

弹栈 (Pop)

移除并返回栈顶元素

stack.pop()

查看栈顶 (Peek)

返回栈顶元素但不移除

stack[-1]

栈大小 & 判空

检查栈状态

len(stack)
len(stack) == 0

实战应用:括号匹配算法

栈最经典的应用之一是检查表达式中的括号是否匹配:


def is_balanced(expression):
    """检查括号是否匹配"""
    stack = []
    mapping = {')': '(', '}': '{', ']': '['}
    
    for char in expression:
        # 如果是开括号,压栈
        if char in mapping.values():
            stack.append(char)
        # 如果是闭括号
        elif char in mapping.keys():
            # 如果栈为空或栈顶不匹配,返回False
            if not stack or stack.pop() != mapping[char]:
                return False
    
    # 如果栈为空,则所有括号都匹配
    return len(stack) == 0

# 测试用例
print(is_balanced("(){}[]"))     # True
print(is_balanced("([{}])"))     # True
print(is_balanced("(]"))         # False
print(is_balanced("([)]"))       # False
print(is_balanced("((()"))       # False
                

算法解析:

  1. 遍历表达式中的每个字符
  2. 遇到开括号((、{、[)时压入栈中
  3. 遇到闭括号()、}、])时:
    • 如果栈为空 → 括号不匹配
    • 如果栈顶元素与当前闭括号不匹配 → 括号不匹配
  4. 遍历完成后,如果栈为空则所有括号匹配

自定义栈类实现

我们可以创建一个Stack类来封装栈的功能,使代码更清晰易用:


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)
    
    def __str__(self):
        """返回栈的字符串表示"""
        return str(self.items)

# 使用自定义栈类
if __name__ == "__main__":
    s = Stack()
    s.push(10)
    s.push(20)
    s.push(30)
    
    print("栈内容:", s)        # [10, 20, 30]
    print("栈顶元素:", s.peek()) # 30
    print("弹出:", s.pop())     # 30
    print("弹出:", s.pop())     # 20
    print("栈是否为空:", s.is_empty()) # False
    print("栈大小:", s.size())  # 1
                

总结

栈是算法和程序设计中不可或缺的数据结构,通过本教程我们学习了:

  • 使用Python列表实现栈的基本操作(压栈、弹栈、查看栈顶)
  • 利用collections.deque实现高性能栈
  • 栈在括号匹配算法中的实际应用
  • 如何封装自定义栈类提高代码可读性

掌握栈的操作和原理,将有助于你解决更多复杂的算法问题,提升编程能力!

发表评论