在 Python 中实现一个高效的队列

Question

我一直在尝试用 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

原文由 random_coder_101 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 1

正如 Uri Goren 在上面敏锐地指出 的那样，Python 标准库已经为您幸运地实现了一个高效的队列： collections.deque 。

不该做什么

避免通过自己动手来重新发明轮子：

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

引用 官方 deque 文档：

虽然 list 对象支持类似的操作，但它们针对快速固定长度操作进行了优化，并为 pop(0) 和 insert(0, v) 操作带来 O(n) 内存移动成本—基础数据表示的大小和位置。

更关键的是， 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()

证据就在地狱般的布丁中：

 >>> 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 类提供了 更多的特性，包括：

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

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

原文由 Cecil Curry 发布，翻译遵循 CC BY-SA 4.0 许可协议

Answer 2

您可以保留头节点和尾节点而不是队列列表 queue class

 class Node:
    def __init__(self, item = None):
        self.item = item
        self.next = None
        self.previous = None

class Queue:
    def __init__(self):
        self.length = 0
        self.head = None
        self.tail = None

    def enqueue(self, value):
        newNode = Node(value)
        if self.head is None:
            self.head = self.tail = newNode
        else:
            self.tail.next = newNode
            newNode.previous = self.tail
            self.tail = newNode
        self.length += 1

    def dequeue(self):
        item = self.head.item
        self.head = self.head.next
        self.length -= 1
        if self.length == 0:
            self.tail = None
        return item

原文由 Shaon shaonty 发布，翻译遵循 CC BY-SA 4.0 许可协议