我一直在尝试用 Python 实现队列，但遇到了问题。

我正在尝试使用列表来实现队列数据结构，但是我不太清楚如何进行 enqueue 和 dequeue O(1) 操作。

我在网上看到的每个例子，似乎只是附加 enqueue 操作并从 dequeue 操作的列表中删除第一个元素。但这会使 dequeue 操作 O(n)(其中 n 是列表的大小)正确吗？

我错过了什么基本的东西吗？或者您是否必须使用 LinkedLists 来有效地实现 Queue？

import unittest

class Queue:
    def __init__(self):
        self._queue = []
        self.size = 0
        self.maxSize = 10

    def enqueue(self, item):
        if self.size < self.maxSize:
            self._queue.append(item)

    def dequeue(self):
        '''
        Removes an item from the front of the list. Remove first element of
        the array
        '''
        first = self._queue[0]
        del self._queue[0]
        return first

最佳答案

作为 Uri Goren 机敏的 noted above，Python stdlib 已经为您幸运地实现了一个高效的队列:collections.deque。

什么不该做

避免自己动手来重新发明轮子:

• Linked list implementation 。这样做可以将 dequeue() 和 enqueue() 方法的最坏情况时间复杂度降低到 O(1)，collections.deque 类型已经这样做了。考虑到其基于 C 的传统，它也是线程安全的，并且可能具有更高的空间和时间效率。
• Python list implementation 。正如我 note below 一样，根据 Python 列表实现 enqueue() 方法会将其最坏情况的时间复杂度增加到 O(n)。 因为从列表中删除最后一项基于 C 的数组，因此 Python 列表是一个常量时间操作，根据 Python 列表实现 dequeue() 方法保留相同的最坏情况时间复杂度 O(1)。但谁在乎？ enqueue() 仍然慢得可怜。

引用 official deque documentation :

Though list objects support similar operations, they are optimized for fast fixed-length operations and incur O(n) memory movement costs for pop(0) and insert(0, v) operations which change both the size and position of the underlying data representation.

更关键的是，deque还通过在初始化时传递的maxlen参数提供了对最大长度的开箱即用支持，避免了手动尝试限制队列大小的需要(由于 if 条件中隐含的竞争条件，这不可避免地破坏了线程安全)。

做什么

相反，根据标准 collections.deque 类型实现您的 Queue 类，如下所示:

from collections import deque

class Queue:
    '''
    Thread-safe, memory-efficient, maximally-sized queue supporting queueing and
    dequeueing in worst-case O(1) time.
    '''


    def __init__(self, max_size = 10):
        '''
        Initialize this queue to the empty queue.

        Parameters
        ----------
        max_size : int
            Maximum number of items contained in this queue. Defaults to 10.
        '''

        self._queue = deque(maxlen=max_size)


    def enqueue(self, item):
        '''
        Queues the passed item (i.e., pushes this item onto the tail of this
        queue).

        If this queue is already full, the item at the head of this queue
        is silently removed from this queue *before* the passed item is
        queued.
        '''

        self._queue.append(item)


    def dequeue(self):
        '''
        Dequeues (i.e., removes) the item at the head of this queue *and*
        returns this item.

        Raises
        ----------
        IndexError
            If this queue is empty.
        '''

        return self._queue.pop()

证据就在 hell 般的布丁中:

>>> queue = Queue()
>>> queue.enqueue('Maiden in Black')
>>> queue.enqueue('Maneater')
>>> queue.enqueue('Maiden Astraea')
>>> queue.enqueue('Flamelurker')
>>> print(queue.dequeue())
Flamelurker
>>> print(queue.dequeue())
Maiden Astraea
>>> print(queue.dequeue())
Maneater
>>> print(queue.dequeue())
Maiden in Black

一个人去很危险

实际上，也不要那样做。

最好只使用原始的 deque 对象，而不是尝试将该对象手动封装在 Queue 包装器中。上面定义的 Queue 类仅作为 deque API 通用实用程序的简单演示。

deque类提供了significantly more features，包括:

...iteration, pickling, len(d), reversed(d), copy.copy(d), copy.deepcopy(d), membership testing with the in operator, and subscript references such as d[-1].

只需在需要单端或双端队列的任何地方使用deque。就是这样。

关于python - 在 Python 中实现一个高效的队列，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/45688871/