11. 常用数据结构
11.1. 栈
list 的 append() 和 pop() 方法使得 list 类型可以作为简单的栈使用。
11.2. 队列
Attention
Python 2 的队列模块为 Queue ，Python 3 的队列模块为 queue 。
11.2.1. queue
import queue
queue 模块实现了多生产者、多消费者队列，适用于消息必须安全地在多线程间交换的线程编程。
类
- class queue.Queue(maxsize=0)
先进先出。
maxsize 指明了队列中能存放的数据个数的上限。 一旦达到上限，插入会导致阻塞，直到队列中的数据被消费掉。 如果 maxsize 小于或者等于 0，队列大小没有限制。
- class queue.LifoQueue(maxsize=0)
后进先出，类似于栈。
- class queue.PriorityQueue(maxsize=0)
优先队列。
一般使用 tuple（优先级 + 数据）作为队列元素，优先级为 tuple 的第一项。 默认 tuple 第一项越小，优先级越高，越先出队列。优先级相同则会比较数据项，如果数据类型没有定义
__lt__或__gt__成员，就会报错。\(\color{darkgreen}{Code}\)
1## Merge k Sorted Lists 2## https://leetcode.com/problems/merge-k-sorted-lists 3 4# Definition for singly-linked list. 5# class ListNode: 6# def __init__(self, val=0, next=None): 7# self.val = val 8# self.next = next 9 10from queue import PriorityQueue 11 12class Solution: 13 def mergeKLists(self, lists: List[Optional[ListNode]]) -> Optional[ListNode]: 14 setattr(ListNode, "__lt__", lambda self, other: self.val < other.val) 15 pq = PriorityQueue() 16 dummy = ListNode(None, None) 17 curr = dummy 18 for l in lists: 19 if l: pq.put(l) 20 while not pq.empty(): 21 p = pq.get() 22 curr.next = p 23 curr = p 24 if p.next: pq.put(p.next) 25 return dummy.next
异常
- exception queue.Empty
对 空 的队列对象调用非阻塞的
get()或get_nowait()时引发的异常。
- exception queue.Full
对 满 的队列对象调用非阻塞的
put()或put_nowait()时引发的异常。
方法
队列（ Queue LifoQueue PriorityQueue ）具有以下公共方法。
- qsize()
返回队列的（ 大致 ）大小。多进程/线程情景下，
qsize() > 0不保证后续的get()不被阻塞，qsize() < maxsize也不保证put()不被阻塞。
- empty()
如果队列为空，返回 True ，否则返回 False 。多进程/线程情景下，如果
empty()返回 True ，不保证后续调用的put()不被阻塞；如果empty()返回 False ，也不保证后续调用的get()不被阻塞。
- put(item, block=True, timeout=None)
将 item 放入队列。如果
block=True且timeout=None，则在必要时阻塞至有空闲插槽可用；如果 timeout 是个正数，将最多阻塞 timeout 秒，如果在这段时间没有可用的空闲插槽，将引发queue.Full异常。如果block=False，若有空闲插槽立即可用，则把 item 放入队列，否则引发queue.Full异常（在这种情况下，timeout 将被忽略）。
- put_nowait(item)
相当于
put(item, block=False)。
- get(block=True, timeout=None)
从队列中 移除并返回 一个 item。如果
block=True且timeout=None，则在必要时阻塞至 item 可获取；如果 timeout 是个正数，将最多阻塞 timeout 秒，如果在这段时间内 item 仍不能获取，将引发queue.Empty异常。如果block=False，若一个 item 可立即获取，则返回一个 item，否则引发queue.Empty异常（这种情况下，timeout 将被忽略）。
- get_nowait()
相当于
get(block=False)。
- task_done()
在消费者进程/线程中使用，每个
get()被用于获取一个任务，后续调用task_done()用来告诉队列：该任务的处理已经完成。如果被调用的次数多于放入队列中的 item 数量，将引发
ValueError异常。
- join()
阻塞至队列中所有的 item 都被接收和处理完毕。每调用一次
task_done()，未完成计数就会减少 1，当未完成计数降到零的时候，阻塞被解除。
1from queue import PriorityQueue
2
3q = PriorityQueue()
4q.put((1,'apple'))
5q.put((10,'app'))
6q.put((5,'banana'))
7
8while not q.empty():
9 print(q.get(), q.qsize())
(1, 'apple') 2
(5, 'banana') 1
(10, 'app') 0
1import threading
2import queue
3
4q = queue.Queue()
5
6def worker():
7 while True:
8 item = q.get()
9 print(f'Working on {item}')
10 print(f'Finished {item}')
11 q.task_done()
12
13# Turn-on the worker thread.
14threading.Thread(target=worker, daemon=True).start()
15
16# Send thirty task requests to the worker.
17for item in range(5):
18 q.put(item)
19
20# Block until all tasks are done.
21q.join()
22print('All work completed')
Working on 0
Finished 0
Working on 1
Finished 1
Working on 2
Finished 2
Working on 3
Finished 3
Working on 4
Finished 4
All work completed
Tip
多进程/线程情景下，既然 qsize() 和 empty() 不可信，那么判断循环结束条件应该注意，应使用异常来判断。
1while True:
2 try:
3 ## ...
4 item = q.get(block=False)
5 ## ...
6 except queue.Empty:
7 break
1while True:
2 try:
3 ## ...
4 q.put(item, block=False)
5 ## ...
6 except queue.Full:
7 break
11.2.2. deque
双端队列（Double-Ended Queue）。
from collections import deque
- 方法：
append, appendleft
pop, popleft
extend, extendleft
reverse
rotate
count
clear
1>>> dq = deque(range(5))
2>>> dq
3deque([0, 1, 2, 3, 4])
4>>> dq.rotate() ## right-shift
5>>> dq
6deque([4, 0, 1, 2, 3])
7>>> dq.rotate(3)
8>>> dq
9deque([1, 2, 3, 4, 0])
10>>> dq.rotate(-3) ## left-shift
11deque([4, 0, 1, 2, 3])
12>>> dq.reverse()
13>>> dq
14deque([3, 2, 1, 0, 4])
11.3. 堆
import heapq
heapq 创建的是 小顶堆 ，堆顶元素是堆的最小元素。
11.3.1. 创建堆
heappush
基于空列表[]，使用
heappush把元素逐个插入堆中。heappop(h)弹出并返回堆顶元素。h[0] 是最小值。如果插入元素是元组（tuple），则元组的第一项自动成为优先级，值越小，优先级越高。堆顶元素优先级最高，值最小。
1>>> def heapsort(iterable): 2... h = [] 3... for value in iterable: 4... heapq.heappush(h, value) 5... return [heapq.heappop(h) for _ in range(len(h))] ## 不能直接返回 h 6... 7>>> heapsort([1, 3, 5, 7, 9, 2, 4, 6, 8, 0]) 8[0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
heapify(list_x)
把列表转换为堆，in-place，线性时间。
1>>> h = [2, 3, 5, 1, 54, 23, 132] 2>>> heapq.heapify(h) 3>>> print h 4[1, 2, 5, 3, 54, 23, 132] ## h 是堆，但是h不一定是有序的，只能保证 h[0] 是最小值。 5>>> print [heapq.heappop(h) for _ in range(len(h))] 6[1, 2, 3, 5, 23, 54, 132]
merge
合并多个排序后的序列，返回排序后的序列的迭代器。
1>>> h1 = [32, 3, 5, 34, 54, 23, 132] 2>>> h2 = [23, 2, 12, 656, 324, 23, 54] 3>>> h1 = sorted(h1) 4>>> h2 = sorted(h2) 5>>> h = heapq.merge(h1, h2) 6>>> print type(h), list(h) 7<type 'generator'> [2, 3, 5, 12, 23, 23, 23, 32, 34, 54, 54, 132, 324, 656]
heapreplace
删除堆中最小元素，并插入新的元素。
1>>> h = [32, 3, 5, 34, 54, 23, 132] 2>>> heapq.heapify(h) 3>>> heapq.heapreplace(h, 9) 4>>> print [heapq.heappop(h) for _ in range(len(h))] 5[5, 9, 23, 32, 34, 54, 132]
11.3.2. 获取最值
heapq.nlargest(n, iterable[, key])
heapq.nsmallest(n, iterable[, key])
返回一个长度为 \(n\) 的列表，包含数据中的前 \(n\) 个最大/最小的元素。使用 key 定义排序关键字。
1>>> nums = [1, 3, 4, 5, 2]
2>>> print heapq.nlargest(3, nums)
3[5, 4, 3]
4>>> print heapq.nsmallest(3, nums)
5[1, 2, 3]
6
7>>> info = [
8... {'name': 'IBM', 'price': 91.1},
9... {'name': 'AAPL', 'price': 543.22},
10... {'name': 'FB', 'price': 21.09},
11... {'name': 'HPQ', 'price': 31.75},
12... {'name': 'YHOO', 'price': 16.35},
13... {'name': 'ACME', 'price': 115.65}
14... ]
15>>> cheap = heapq.nsmallest(2, info, key=lambda x:x['price'])
16>>> expensive = heapq.nlargest(2, info, key=lambda x:x['price'])
17>>> print cheap
18[{'price': 16.35, 'name': 'YHOO'}, {'price': 21.09, 'name': 'FB'}]
19>>> print expensive
20[{'price': 543.22, 'name': 'AAPL'}, {'price': 115.65, 'name': 'ACME'}]
11.3.3. 大顶堆
heapq 默认创建小顶堆，为了创建大顶堆，有以下 trick:
heapq.heappush(-x) ## 插入 x
x = - heapq.heappop(h) ## 弹出堆顶元素
11.3.4. 数列前 K 大的数
Hint：建立大小为 \(K\) 的小顶堆，对后续所有数进行遍历：如果大于堆顶元素，则有可能是前 \(K\) 大的数，堆顶元素弹出，插入该数。 时间复杂度 \(\mathcal{O}(NlogK)\)。
1import heapq as hq
2
3class TopKHeap(object):
4 def __init__(self, k=3):
5 self.k = k
6 self.data = []
7
8 def push(self, x):
9 if len(self.data) < self.k:
10 hq.heappush(self.data, x)
11 else:
12 min_number = self.data[0]
13 if x > min_number:
14 hq.heapreplace(self.data, x)
15
16 def topk(self):
17 return list(reversed([hq.heappop(self.data) for _ in range(len(self.data))]))
18
19def main():
20 nums = range(1, 10)
21 tkh = TopKHeap(3)
22 for n in nums:
23 tkh.push(n)
24 print tkh.topk() ## [9, 8, 7]
25
26if __name__ == '__main__':
27 main()
11.4. 计数器
from collections import Counter
Counter 用于统计频率。属性与字典类似，有 keys() ，values() ，items() 等。
Note
Counter 统计之后并不一定是按照频率从高到低排列的。
1>>> cnt = Counter() ## 空计数器
2>>> for word in ['red', 'blue', 'red', 'green', 'blue', 'blue']:
3... cnt[word] += 1
4>>> cnt
5Counter({'blue': 3, 'red': 2, 'green': 1})
6>>> cnt = Counter(['red', 'blue', 'red', 'green', 'blue', 'blue'])
7>>> cnt
8Counter({'blue': 3, 'red': 2, 'green': 1})
9
10>>> cnt.most_common(2) ## 返回出现频率最高的两个元素
11[('blue', 3), ('red', 2)]
12
13>>> c = Counter('gallahad')
14>>> c
15Counter({'a': 3, 'l': 2, 'h': 1, 'g': 1, 'd': 1})
16
17>>> c = Counter({'red': 4, 'blue': 12})
18>>> c
19Counter({'blue': 12, 'red': 4})
20>>> c['green'] ## 访问不存在关键字, 可使用 c.get('green')
210
11.5. 参考资料
queue — A synchronized queue class
python中的Queue(队列)详解
Python collections使用
Python标准库模块之heapq
python使用heapq实现小顶堆（TopK大）/大顶堆（BtmK小）
Counter