简析Python中的四种队列
队列是一种只允许在一端进行插入操作,而在另一端进行删除操作的线性表。 在 Python 文档中搜索队列(queue)会发现,Python 标准库中包含了四种队列,分别是 queue.Queue / asyncio.Queue / multiprocessing.Queue / collections.deque。 collections.deque deque 是双端队列(double-ended queue)的缩写,由于两端都能编辑,deque 既可以用来实现栈(stack)也可以用来实现队列(queue)。 deque 支持丰富的操作方法,主要方法如图: 相比于 list 实现的队列,deque 实现拥有更低的时间和空间复杂度。list 实现在出队(pop)和插入(insert)时的空间复杂度大约为 O(n),deque 在出队(pop)和入队(append)时的时间复杂度是 O(1)。 deque 也支持 in 操作符,可以使用如下写法: q = collections.deque([1, 2, 3, 4]) print(5 in q) # False print(1 in q) # True deque 还封装了顺逆时针的旋转的方法:rotate。 # 顺时针 q = collections.deque([1, 2, 3, 4]) q.rotate(1) print(q) # [4, 1, 2, 3] q.rotate(1) print(q) # [3, 4, 1, 2] # 逆时针 q = collections.deque([1, 2, 3, 4]) q.rotate(-1) print(q) # [2, 3, 4, 1] q.rotate(-1) print(q) # [3, 4, 1, 2] 线程安全方面,通过查看 collections.deque 中的 append()、pop()等方法的源码可以知道,他们都是原子操作,所以是 GIL 保护下的线程安全方法。 ...