详解详解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保护下的线程安全方法。
static PyObject *
deque_append(dequeobject *deque, PyObject *item) {
Py_INCREF(item);
if (deque_append_internal(deque, item, deque->maxlen) < 0)
return NULL;
Py_RETURN_NONE;
}
通过dis方法可以看到,append是原子操作(一行字节码)。
评论0