高效实现入队和出队的时间复杂度

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

O(n)是管理列表长度的必然结果。

这是一个解决方案。通常，它以O（1）的形式运行，并且由于出列方法中发生的额外步骤，它有时是O（n）。

当列表增长过大并触发清理时，会发生O（n）步骤。请注意，一般来说，这应该在dequeue方法内部完成。在外面做会更复杂，效率也会更低。

class FasterQueue:
    def __init__(self, maxwaste=100):
        self.items = []
        self.nout = 0
        self.maxwaste = maxwaste
    def enqueue(self, item):
        self.items.append(item)
    def dequeue(self):
        if len(self.items):
            retv = self.items[self.nout]
            self.nout += 1
            if self.nout >= self.maxwaste:
                self.items = self.items[self.nout:]
                self.nout =0
            return retv
        else:
            print( 'empty' )
            raise ValueError
    def listQ(self):
        return ' '.join( self.items[self.nout:] )
    def isEmpty(self):
        return self.nout == len(self.items)
    def size(self):
        return len(self.items) - self.nout

q = FasterQueue(5)

for n in range(10):
    q.enqueue( str(n) )

print( 'queue size %d  nout %d items %s'%(q.size(),q.nout,q.listQ()) )
print( q.items )

while True:
    try:
        print( 'dequeue %s'%q.dequeue() )
        print( 'queue size %d  nout %d items %s'%(q.size(),q.nout,q.listQ()) )
        print( q.items )
    except:
        print( 'empty' )
        break

运行上面的代码会产生下面的输出，注意当超过maxwaste时浪费的内存的回收。出于演示操作的目的，此处将Maxwaste设置为小值。

queue size 10  nout 0 items 0 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 0
queue size 9  nout 1 items 1 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 1
queue size 8  nout 2 items 2 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 2
queue size 7  nout 3 items 3 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 3
queue size 6  nout 4 items 4 5 6 7 8 9
['0', '1', '2', '3', '4', '5', '6', '7', '8', '9']
dequeue 4
queue size 5  nout 0 items 5 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 5
queue size 4  nout 1 items 6 7 8 9
['5', '6', '7', '8', '9']
dequeue 6
queue size 3  nout 2 items 7 8 9
['5', '6', '7', '8', '9']
dequeue 7
queue size 2  nout 3 items 8 9
['5', '6', '7', '8', '9']
dequeue 8
queue size 1  nout 4 items 9
['5', '6', '7', '8', '9']
dequeue 9
queue size 0  nout 0 items 
[]
empty
empty

Answer 2

按照我的理解，enqueue应该在末尾插入，dequeue应该从开头删除。所以代码应该是

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

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

def dequeue(self):
    if self.items:
        return self.items.pop(0)
    print("Underflow")

def isEmpty(self):
    return self.items == []

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

Answer 3

让它使用一些更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方法，试图释放已使用的内存空间，在de队列（）的末尾调用它可能很有用-否则列表会任意变长并浪费大量内存。其中的常量并不惊人，但应该可以防止它过于频繁地收缩。此操作将是O（n），可能就是所指的内容