线性数据结构（linear data structure）第二讲队列（queue）

队列的添加和移除原则为：先入先出（first-in first out, FIFO）。生活中排队就是队列。

今晚我们看完球在簋街附近打车，前面有100多位在等，这就是一个队列。问：这里的first-in一定会first-out么？如果把first-out定义成被服务，那是的，先叫车先打到车；如果把first-out定义为移出队列，那就不是，用户取消了也会被移出队列。

队列的操作：

  • Queue() 创建一个新队列，返回空的队列。
  • enqueue(item) 在队列尾部增加一个元素，返回None。
  • dequeue() 从队列头部移除一个元素，返回移除的元素。
  • peek() 返回队列中下一个被移除的元素。
  • is_empty() 返回队列是否为空，True或者False。
  • size() 返回队列中元素个数。

队列的实现：

class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.insert(0, item)
    def dequeue(self):
        return self.items.pop()
    def peek(self):
        return self.items[-1]
    def is_empty(self):
        return self.items == []
    def size(self):
        return len(self.items)

队列的优点：

  • 操作很快。

队列的用处：

  • 广度优先搜索：用队列记录将要被访问的节点，先加入，先被查看
  • 处理器：CPU中的scheduler中等待被执行的队列
  • 循环播放列表

判断是否需要用队列：考虑场景中有没有依次、FIFO、循环的需求。 - myself

参考资料：