python - 添加队列中的数据

Question

我认为队列是第一个来的人首先得到服务的队列。然后其他人在后面加入他。我用 Python 编写了以下实现来实现这一点:

class Queue:
    def __init__(self):
        self.item = []
    def enqueue(self,value):
        self.item.append(value)
    def dequeue(self):
        return self.item.pop(0)
    def size(self):
        return len(self.item)
    def isEmpty(self):
        return self.item == []

但是当我查看在线教程时，我发现队列的实现如下:

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

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

    def enqueue(self, item):
        self.items.insert(0,item)

    def dequeue(self):
        return self.items.pop()

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

根据这个在线实现，item被添加到第一个。但我的直觉告诉我应该将该项目添加到列表的后面(附加)并从前面删除(删除第一项)。我想知道哪种形式是正确的，如果我不正确，那么我没有正确理解的是什么？

Answer 1

两种方法都行。我同意您的直觉，即在右侧添加并在左侧弹出，因此基础列表始终按从旧到新的顺序排列。

就其值(value)而言，这两种实现都是低效的——在位置零处插入或弹出是一个 O(n) 操作。

参见 collections.deque()对于 O(1) 实现。