上一篇
Python栈操作详解:从入门到实战 | Python算法教程
- Python
- 2025-08-16
- 1350
Python栈操作详解:从基础到实战应用
掌握栈数据结构在Python中的实现与应用
什么是栈?
栈(Stack)是一种遵循后进先出(LIFO)原则的数据结构。想象一下堆叠盘子——你总是把新盘子放在顶部,取用时也是从顶部开始拿取。
在计算机科学中,栈被广泛应用于:
- 函数调用管理
- 表达式求值(如括号匹配)
- 撤销(Undo)机制
- 浏览器的前进/后退功能
- 深度优先搜索算法
在Python中实现栈
Python没有专门的栈数据结构,但我们可以使用内置的list
或collections.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
算法解析:
- 遍历表达式中的每个字符
- 遇到开括号((、{、[)时压入栈中
- 遇到闭括号()、}、])时:
- 如果栈为空 → 括号不匹配
- 如果栈顶元素与当前闭括号不匹配 → 括号不匹配
- 遍历完成后,如果栈为空则所有括号匹配
自定义栈类实现
我们可以创建一个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
实现高性能栈 - 栈在括号匹配算法中的实际应用
- 如何封装自定义栈类提高代码可读性
掌握栈的操作和原理,将有助于你解决更多复杂的算法问题,提升编程能力!
本文由JiangFengNeng于2025-08-16发表在吾爱品聚,如有疑问,请联系我们。
本文链接:https://521pj.cn/20258303.html
发表评论