python - 队列的高效实现——入队和出队的时间复杂度

Question

我目前正在阅读一本关于数据结构/算法的教科书。练习之一是使用Python列表结构实现一个高效的队列:入队和出队的时间复杂度平均需要为O(1)。书上说，对于特定的出队情况，时间复杂度应该是O(n)，其余时间应该是O(1)。我实现它时，队列的后部是列表的末尾，队列的前部是列表的开头；当我将一个元素出队时，我不会将其从列表中删除，而是简单地增加一个计数器，以便该方法知道列表中的哪个元素代表队列的前面。这是我的代码:

class FasterQueue:
    def __init__(self):
        self.items = []
        self.index = 0
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        index = self.index
        self.index += 1
        return self.items[index]
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)

我的问题:书上说在某些情况下出队应该花费O(1)。我不知道这是什么情况，因为出队似乎总是只是在某个索引处获取值。我的队列实现无效还是我遗漏了其他内容？或者教科书只是在寻找另一种更常见的实现？

非常感谢您的帮助。

Answer 1

使其使用更多 Python 风格的功能，我会这样做:

class FasterQueue:
    def __init__(self):
        self.items = []
        self.index = 0

    def enqueue(self, item):
        self.items.append(item)

    def dequeue(self):
        # do this first so IndexErrors don't cause us ignore items
        obj = self.items[self.index]
        # release the reference so we don't "leak" memory
        self.items[self.index] = None
        self.index += 1
        return obj

    def isEmpty(self):
        return self.index == len(self.items)

    def size(self):
        return len(self.items)

    def try_shrink(self):
        nactive = len(self.items) - self.index
        if nactive + 2 < self.index // 2:
            self.items = self.items[self.index:]
            self.index = 0

添加了一个 try_shrink 方法，尝试释放已用的内存空间，在 dequeue() 末尾调用此方法可能会很有用 - 否则列表会任意增长并浪费大量内存。那里的常数并不令人惊奇，但应该可以防止它经常收缩。这个操作的时间复杂度为 O(n)，可能就是所提到的