Python中是否有非同步队列？

Question

我正在使用Python（实际上是pypy3）练习编程竞赛。在一个问题中，我需要使用队列——我只需要将元素放在一端并从另一端取出。根据文档，似乎有两个选项：queue.Queue和queue.deque。我首先尝试使用queue.Queue解决问题，但我的解决方案超过了时间限制。然后我切换到queue.deque，并通过了问题（虽然接近极限）。

从文档中可以看出，这两种容器都是线程安全的（至少对于一些deque操作），而我永远不会使用多个线程。Python中是否有简单的非同步队列？

- Ivaylo Strandjev

---

你尝试过使用 collections.deque 吗？ - PM 2Ring

@PM2Ring，看起来这个容器也是同步的：Deques支持线程安全、内存高效的从deque的任一侧进行附加和弹出，两个方向的O(1)性能大致相同。 - Ivaylo Strandjev

@PM2Ring 我明白了，所以这些操作不需要锁定。看起来这个结构可能会有用。你链接的问题没有比较colllection.deque和queue.deque。它们之间有什么区别？ - Ivaylo Strandjev

queue.Queue（在Python 2中又称为Queue.Queue）在内部使用了一个collections.deque；如果您不需要queue.Queue的特殊功能，则应该使用一个普通的collections.deque。 - PM 2Ring

@PM2Ring请考虑添加一个回答，解释你所讲的内容。 - Ivaylo Strandjev

Answer 1

deque 并没有提供同步功能，文档只是说明由于对于增加和删除元素采用原子操作，所以可以保证线程安全。特别的，在 CPython 中除了全局解释器锁之外，并没有其他的锁机制。如果你需要使用双端队列或者先进先出的队列（FIFO），那么你应该使用 double-ended queue。如果你需要一个后进先出的栈，则使用列表（list）。在内部，deque 实现使用了一个长度固定的双向链表块。

queue.Queue 内部使用了一个 deque，此外还使用了互斥锁来保护这些不会被 deque 原子操作处理的剩余操作。

因此，你的问题不在于选择 deque，而很可能是算法的其他方面。

- Antti Haapala -- Слава Україні

Answer 2

你可以使用两个普通列表（作为堆栈）来模拟队列。

class Queue:
    def __init__(self):
        self.l1 = []   # Add new items here
        self.l2 = []   # Remove items here

    # O(1) time - simple stack push
    def enqueue(self, x):
        self.l1.append(x)

    # O(1) when l2 is not empty
    # O(k) if l2 is empty, but k is bounded by the number
    # of preceding calls to enqueue. Abusing the notation a bit,
    # you can think of the average for each call in a series to be
    # (k*O(1) + O(k))/k = O(1)
    def dequeue():
        if not self.l2:
            self.l2 = self.l1[::-1] #  Copy and reverse
            self.l1 = []
        return self.l2.pop()

- chepner

---

当存在collections.deque时，没有理由使用这个；（此外，这是一个不线程安全的deque示例） - Antti Haapala -- Слава Україні

问题明确说明线程安全不是问题。这只是为了指出实现队列相当简单。 - chepner