人工智能之编程进阶 Python高级： 栈和队列

前言

列表（**list**）可以很方便地用作栈（Stack）和队列（Queue）的底层实现，但它们的性能特性不同，适用于不同场景。本文详细讲解如何用list实现栈和队列，并指出最佳实践以及queue库的使用方式

一、用list实现栈（Stack）

✅ 栈的特点（LIFO：Last In, First Out）

• 后进先出
• 主要操作：压栈（push）、弹栈（pop）

✅ 使用list实现栈（高效！）

Python 的list在尾部（末尾）的操作是O(1)时间复杂度，因此用列表尾部作为栈顶是最高效的。

代码语言：python

AI代码解释

# 创建一个栈 stack = [] # 压栈（push）—— 使用 append() stack.append(1) stack.append(2) stack.append(3) print(stack) # [1, 2, 3] # 弹栈（pop）—— 使用 pop()（默认弹出最后一个） top = stack.pop() print(top) # 3 print(stack) # [1, 2] # 查看栈顶（不弹出） if stack: top = stack[-1] print("栈顶:", top) # 2 # 判断栈是否为空 if not stack: print("栈为空")

✅ 栈的典型应用

• 括号匹配
• 函数调用栈
• 表达式求值（如后缀表达式）
• 撤销操作（Undo）

示例：括号匹配

代码语言：python

AI代码解释

def is_valid_parentheses(s): stack = [] pairs = {')': '(', ']': '[', '}': '{'} for char in s: if char in '([{': stack.append(char) # 左括号入栈 else: if not stack or stack.pop() != pairs[char]: return False # 不匹配 return not stack # 栈空则匹配成功 print(is_valid_parentheses("([{}])")) # True print(is_valid_parentheses("([)]")) # False

✅结论：**list**非常适合实现栈！

二、用list实现队列（Queue）

⚠️ 队列的特点（FIFO：First In, First Out）

• 先进先出
• 主要操作：入队（enqueue）、出队（dequeue）

❌ 用list实现队列的问题

如果用list的头部作为队首（出队），尾部作为队尾（入队）：

代码语言：python

AI代码解释

queue = [] # 入队（在尾部添加）—— O(1) queue.append('A') queue.append('B') queue.append('C') # 出队（从头部弹出）—— O(n) ❌ 低效！ first = queue.pop(0) # 删除并返回第一个元素

问题：list.pop(0)需要将后面所有元素向前移动一位，时间复杂度为O(n)，数据量大时性能很差。

三、队列的正确实现方式

✅ 方案 1：使用collections.deque（推荐！）

deque（双端队列）在两端的操作都是O(1)，是实现队列的最佳选择。

代码语言：python

AI代码解释

from collections import deque # 创建队列 queue = deque() # 入队（尾部添加）—— O(1) queue.append('A') queue.append('B') queue.append('C') # 出队（头部弹出）—— O(1) first = queue.popleft() print(first) # 'A' print(queue) # deque(['B', 'C']) # 查看队首（不弹出） if queue: front = queue[0] print("队首:", front) # 'B' # 判断队列是否为空 if not queue: print("队列为空")

✅ 方案 2：使用queue.Queue（线程安全）

适用于多线程环境：

代码语言：python

AI代码解释

from queue import Queue q = Queue() q.put('A') # 入队 q.put('B') item = q.get() # 出队（阻塞式） print(item) # 'A'

📌注意：queue.Queue是线程安全的，但性能略低于deque，单线程程序推荐用deque。

四、对比总结

五、实际应用示例

1. 用栈实现深度优先搜索（DFS）

代码语言：python

AI代码解释

def dfs_iterative(graph, start): visited = set() stack = [start] while stack: node = stack.pop() if node not in visited: print(node) visited.add(node) # 将邻居加入栈（顺序影响遍历方向） stack.extend(reversed(graph[node]))

2. 用队列实现广度优先搜索（BFS）

代码语言：python

AI代码解释

from collections import deque def bfs(graph, start): visited = set() queue = deque([start]) while queue: node = queue.popleft() if node not in visited: print(node) visited.add(node) queue.extend(graph[node])

六、最佳实践建议

🔥记住：栈 → 用list队列 → 用deque不要用list.pop(0)做队列！

七、扩展：自定义栈和队列类（可选）

代码语言：python

AI代码解释

# 自定义栈类 class Stack: def __init__(self): self._items = [] def push(self, item): self._items.append(item) def pop(self): if self.is_empty(): raise IndexError("pop from empty stack") return self._items.pop() def peek(self): if self.is_empty(): raise IndexError("peek from empty stack") return self._items[-1] def is_empty(self): return len(self._items) == 0 def size(self): return len(self._items) # 自定义队列类 from collections import deque class Queue: def __init__(self): self._items = deque() def enqueue(self, item): self._items.append(item) def dequeue(self): if self.is_empty(): raise IndexError("dequeue from empty queue") return self._items.popleft() def front(self): if self.is_empty(): raise IndexError("front from empty queue") return self._items[0] def is_empty(self): return len(self._items) == 0 def size(self): return len(self._items)

总结

本文主要介绍列表实现栈和队列。Python 的list是实现栈的理想选择但不适合实现队列（因pop(0)效率低）， 队列应使用collections.deque，理解底层操作的时间复杂度，才能写出高性能代码！