Python内置库的数据结构

Python内置库中的数据结构

Python标准库提供了多种数据结构，非常适合用于算法实现。以下是常用的几种：

1. 栈 (Stack)

Python中可以使用列表(list)作为栈：

stack = []
stack.append(1)# 入栈
stack.append(2)
top = stack[-1]# 查看栈顶元素
popped = stack.pop()# 出栈，返回2

2. 队列 (Queue)/双端队列

普通队列 (FIFO)

from collections import deque

queue = deque()
queue.append(1)# 入队
queue.append(2)
first = queue[0]# 查看队首元素
dequeued = queue.popleft()# 出队，返回1

3. 堆 (Heap)/优先队列 (Priority Queue)

Python的heapq模块提供了堆队列算法实现（最小堆）：

import heapq

nums = [3, 1, 4, 1, 5, 9, 2, 6]
heapq.heapify(nums)# 将列表转换为堆
heapq.heappush(nums, 0)# 添加元素
smallest = heapq.heappop(nums)# 弹出最小元素
n_largest = heapq.nlargest(3, nums)# 获取最大的3个元素

4. 哈希表/字典 (Dictionary) 和 OrderedDict，set，orderedset借助OrderedDict

普通字典

d = {'a': 1, 'b': 2}
d['c'] = 3
keys = d.keys()
values = d.values()

有序字典

from collections import OrderedDict

od = OrderedDict()
od['a'] = 1
od['b'] = 2
# 保持插入顺序

5.线程安全的结构：栈、队列、堆

在 Python 中，queue 模块提供了多种线程安全的队列实现，适用于多线程编程场景。以下是 queue 模块中主要数据结构的用法和区别：

---

1. queue.Queue（先进先出队列，FIFO）

import queue

q = queue.Queue(maxsize=3)# 设置队列最大容量（可选）

# 入队
q.put(1)
q.put(2)
q.put(3)

# 队列满时阻塞（默认），可设置超时或非阻塞
# q.put(4, block=False)# 队列满时直接报错 queue.Full
# q.put(4, timeout=1.0)# 等待1秒后仍满则报错

# 出队
print(q.get())# 1（先进入的先取出）
print(q.get())# 2

# 队列空时阻塞（默认），可设置非阻塞或超时
# print(q.get(block=False))# 队列空时直接报错 queue.Empty
# print(q.get(timeout=1.0))# 等待1秒后仍空则报错

# 辅助方法
print(q.qsize())# 当前队列元素数量（非线程安全，慎用）
print(q.empty())# 是否为空
print(q.full())# 是否已满

---

2. queue.LifoQueue（后进先出队列，LIFO，类似栈）

import queue

stack = queue.LifoQueue()
stack.put(1)
stack.put(2)
stack.put(3)

print(stack.get())# 3（最后进入的最先取出）
print(stack.get())# 2

---

3. queue.PriorityQueue（优先队列，基于堆）

import queue

pq = queue.PriorityQueue()

# 插入元素（优先级, 数据），优先级数字越小越先出
pq.put((3, "Low priority"))
pq.put((1, "High priority"))
pq.put((2, "Medium priority"))

print(pq.get())# (1, "High priority")
print(pq.get())# (2, "Medium priority")

---

关键区别

队列类型	顺序规则	线程安全	大小限制	特殊方法
Queue	FIFO（先进先出）	✅	可选	task_done(), join()
LifoQueue	LIFO（后进先出）	✅	可选	同 Queue
PriorityQueue	按优先级排序	✅	可选	同 Queue

---

常见用途

1. 多线程任务调度：主线程向队列提交任务，工作线程消费。
2. 生产者-消费者模型：协调不同线程的数据交换。
3. 广度优先搜索（BFS）：使用 Queue 实现。
4. 深度优先搜索（DFS）：使用 LifoQueue 模拟栈。

---

注意事项

• 线程安全：所有操作（put()/get()）自带锁，适合多线程。
• 性能： Queue > PriorityQueue。
• 单线程场景：直接使用 collections.deque（更快但非线程安全）。