Python 内置数据结构实战：字典、集合、栈、队列与优先队列

2026-09-04 33 预计阅读时间: 1 分钟
来源: realpython.com AI 摘要 Original link

Disclaimer: This article is an AI-assisted summary. Read it together with the original source when precision matters. The summary may omit context, version differences, or edge cases and is not official documentation.

预计阅读时间：7 分钟

Python 提供了多种开箱即用的数据结构。真正影响程序质量的，不是能否写出 list.append()，而是能否根据访问方式、顺序要求、去重规则和性能约束，选出合适的容器。下面通过字典、数组、记录、集合、栈、队列和优先队列，梳理常见选择及其边界。

先从访问模式选择容器

需求 常用结构 典型操作
按键查找、维护映射关系 dict mapping[key]、get()
保存有序的通用对象序列 list 索引、追加、切片
保存类型一致的紧凑数值 array.array 数值追加、序列化
表示字段固定的记录 dataclass、NamedTuple 属性访问、比较
去重或执行集合运算 set 成员测试、交并差集
后进先出 list append()、pop()
先进先出 collections.deque append()、popleft()
总是取出最高优先级任务 heapq heappush()、heappop()

这里最容易踩坑的是把 list 当成所有问题的默认答案。例如，用 items.pop(0) 实现队列会移动后续元素；数据量增大后，这种线性成本会变得明显。deque.popleft() 更符合队列的访问模型。

映射、记录与集合解决不同问题

dict 表达的是“键到值”的映射。它适合索引用户、聚合计数或保存配置，但不应该用难以理解的位置编号模拟记录：

from dataclasses import dataclass

@dataclass(frozen=True)
class User:
    user_id: int
    name: str
    roles: set[str]

users = {
    101: User(101, "Ada", {"admin", "editor"}),
    102: User(102, "Lin", {"viewer"}),
}

editors = {
    user.name
    for user in users.values()
    if "editor" in user.roles
}

print(editors)

这个例子把职责分开了：字典负责按 user_id 定位对象，数据类定义记录字段，集合负责角色去重和成员测试。frozen=True 只会阻止字段被重新赋值，并不会让字段内部的可变集合自动变成不可变对象；如果记录需要深层不可变，可以将 roles 攓成 frozenset[str]。

普通 list 能保存任意 Python 对象，通常也是序列的默认选择。array.array 则要求元素使用同一种基础类型，适合需要更紧凑表示或与二进制数据交互的场景。对于大量科学计算，通常还需要评估 NumPy，而不是把内置 array 当成完整的向量计算工具。

一段代码练习栈、队列和优先队列

下面的脚本可以直接使用 Python 3.10 或更高版本运行。优先队列中的数字越小，表示优先级越高；递增的计数器用于在优先级相同时稳定排序，并避免 Python 尝试比较任务对象。

from collections import deque
from dataclasses import dataclass, field
from heapq import heappop, heappush
from itertools import count

# 栈：后进先出
stack = []
stack.append("parse")
stack.append("validate")
assert stack.pop() == "validate"

# 队列：先进先出
queue = deque(["job-a", "job-b"])
queue.append("job-c")
assert queue.popleft() == "job-a"

# 优先队列：优先级数字越小，越早处理
@dataclass
class Task:
    name: str
    payload: dict = field(default_factory=dict)

sequence = count()
priority_queue = []

def schedule(priority: int, task: Task) -> None:
    heappush(priority_queue, (priority, next(sequence), task))

schedule(20, Task("send-report"))
schedule(10, Task("restore-service", {"region": "ap-east"}))
schedule(10, Task("notify-operator"))

while priority_queue:
    priority, _, task = heappop(priority_queue)
    print(priority, task.name, task.payload)

运行命令：

python data_structures_demo.py

输出顺序应为 restore-service、notify-operator、send-report。需要注意，heapq 提供的是最小堆，并不会让整个列表始终处于完全排序状态；它只保证堆顶元素最小。如果需要查看所有任务的排序结果，应复制后再排序，避免破坏正在使用的队列。

复杂度只是决策的一部分

在通常情况下，字典和集合的查找、插入具有平均常数时间复杂度，列表尾部追加和弹出也很高效。队列左端操作应优先考虑 deque，堆的插入与弹出通常是对数复杂度。不过，容器选择还要考虑语义、内存、并发和可维护性。

可以用这份清单检查实现：

  • 是否需要通过键查找？使用 dict，不要反复线性扫描列表。
  • 是否只关心唯一值和成员关系？使用 set。
  • 是否需要固定字段和清晰类型？使用 dataclass 或 NamedTuple。
  • 是否从同一端压入和弹出？使用 list 实现栈。
  • 是否从右端写入、左端读取？使用 deque 实现队列。
  • 是否按动态优先级逐个取值？使用 heapq；多线程任务调度可评估 queue.PriorityQueue。
  • 是否真的需要紧凑同类型数组？确认 array.array、第三方数值数组或普通列表哪个更符合后续计算方式。

数据结构不是孤立的语法题。把“如何写”进一步追问成“程序下一步如何访问这些数据”，通常就能缩小选择范围，并提前避开性能和语义上的错配。

# Python # 后端

相关推荐