在Python中实现高效的队列

Question

我一直在尝试在Python中实现队列，并且遇到了问题。

我试图使用列表来实现Queue数据结构，但是我不太清楚如何进行enqueue和dequeueO（1）操作。

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

我有基本的东西想念吗？还是必须使用LinkedLists有效地实现队列？

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

Answer 1

作为开放的格伦机敏上面提到的，Python的STDLIB已经实施了您的幸运代表一种有效的队列：collections.deque。

不该做什么

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

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

引用官方deque文档：

尽管list对象支持类似的操作，但它们已针对快速固定长度的操作进行了优化，并且会招致O（n）的内存移动成本pop(0)以及insert(0, v)更改基础数据表示的大小和位置的操作。

更重要的是，deque 它还maxlen通过初始化时传递的参数提供了对最大长度的开箱即用支持，从而避免了手动尝试限制队列大小的需要（由于有条件的情况下隐含的竞争条件，不可避免地破坏了线程安全性） ）。

该怎么办

而是Queue按照以下标准collections.deque类型来实现您的类：

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上面定义的类仅作为dequeAPI 通用实用程序的简单演示而给出。

本deque类提供显著更多的功能，包括：

...迭代，酸洗，len(d)，reversed(d)，copy.copy(d)，copy.deepcopy(d)，成员运算符和下标引用，如与测试d[-1]。

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

Answer 2

You can keep head and tail node instead of a queue list in 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