人工智能之编程进阶 Python高级

第一章 栈和队列

---

文章目录

• 人工智能之编程进阶 Python高级
• 前言
• 一、用 `list` 实现栈（Stack）
• • ✅ 栈的特点（LIFO：Last In, First Out）
  • ✅ 使用 `list` 实现栈（高效！）
  • ✅ 栈的典型应用
  • • 示例：括号匹配
• 二、用 `list` 实现队列（Queue）
• • ⚠️ 队列的特点（FIFO：First In, First Out）
  • ❌ 用 `list` 实现队列的问题
• 三、队列的正确实现方式
• • ✅ 方案 1：使用 `collections.deque`（推荐！）
  • ✅ 方案 2：使用 `queue.Queue`（线程安全）
• 四、对比总结
• 五、实际应用示例
• • 1. 用栈实现深度优先搜索（DFS）
  • 2. 用队列实现广度优先搜索（BFS）
• 六、最佳实践建议
• 七、扩展：自定义栈和队列类（可选）
• 总结
• 资料关注

---

前言

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

---

一、用 list 实现栈（Stack）

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

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

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

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

# 创建一个栈
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）

示例：括号匹配

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 的 头部 作为队首（出队），尾部 作为队尾（入队）：

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)**​，是实现队列的最佳选择。

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（线程安全）

适用于多线程环境：

from queue import Queue

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

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

---

四、对比总结

操作	list（栈）	list（队列）	deque（队列）
尾部添加​	append()→O(1)	append()→O(1)	append()→O(1)
尾部弹出	pop()→O(1)	—	pop()→O(1)
头部添加​	insert(0, x)→O(n)	—	appendleft()→O(1)
头部弹出	—	pop(0)→**O(n)**❌	popleft()→**O(1)**✅

---

五、实际应用示例

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

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）

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（使用 append() 和 pop()）✅
实现队列	collections.deque（使用 append() 和 popleft()）✅
多线程队列	queue.Queue
优先级队列	heapq 模块

🔥 ​记住​：

• 栈 → 用 list
• 队列 → 用 deque
• 不要用 list.pop(0) 做队列！

---

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

# 自定义栈类
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，理解底层操作的时间复杂度，才能写出高性能代码！

资料关注

相关资料获取:
公众号：咚咚王

《Python编程：从入门到实践》
《利用Python进行数据分析》
《算法导论中文第三版》
《概率论与数理统计（第四版） (盛骤) 》
《程序员的数学》
《线性代数应该这样学第3版》
《微积分和数学分析引论》
《（西瓜书）周志华-机器学习》
《TensorFlow机器学习实战指南》
《Sklearn与TensorFlow机器学习实用指南》
《模式识别（第四版）》
《深度学习 deep learning》伊恩·古德费洛著 花书
《Python深度学习第二版(中文版)【纯文本】 (登封大数据 (Francois Choliet)) (Z-Library)》
《深入浅出神经网络与深度学习+(迈克尔·尼尔森（Michael+Nielsen） 》
《自然语言处理综论 第2版》
《Natural-Language-Processing-with-PyTorch》
《计算机视觉-算法与应用(中文版)》
《Learning OpenCV 4》
《AIGC：智能创作时代》杜雨+&+张孜铭
《AIGC原理与实践：零基础学大语言模型、扩散模型和多模态模型》
《从零构建大语言模型（中文版）》
《实战AI大模型》
《AI 3.0》