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

第一章 栈和队列

前言

列表（ 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
• 队列 → 用  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》