Python数据结构与算法中的队列详解(1)

目录 什么是队列？ 构建一个队列 总结

什么是队列？

队列，与栈类似，是 有序集合 。添加操作发生在  [尾部] ，移除操作只发生在  [头部] 。新元素只从 尾部进入 队列，然后一直向前移动到头部，直到成为下一个被移除的元素。?

最新添加的元素必须在队列的尾部等待，在队列中时间最长的元素则排在最前面。这种排序原则被称作 FIFO（first-in first-out） ，即 先进先出 ，也称先到先得。在日常生活中，我们经常排队，这便是最简单的队列例子。进电影院要排队，在超市结账要排队，买咖啡也要排队。好的队列只允许一头进，另一头出，不可能发生插队或者中途离开的情况。?

构建一个队列

如前所述，队列是元素的有序集合， 添加 操作发生在其 尾部 ， 移除 操作则发生在 头部 。队列的操作顺序是  FIFO ，它支持以下操作。

创建 一个空队列。它不需要参数，且会 返回一个空队列 。 Queue() 在队列的 尾部添加 一个元素。 它需要 一个元素作为参数 ，不返回任何值。 enqueue(item) 从队列的 头部移除 一个元素。它不需要参数，且会 返回一个元素 ，并 修改 队列的内容。 dequeue() 检查队列 是否为空 。它不需要参数， 且会 返回一个布尔值 。 isEmpty() 返回队列中 元素的数目 。它不需要参数，且会 返回一个整数 。 size()?

与构建 栈 一样，我们利用简洁强大的 列表来实现队列 。?

需要确定列表的哪一端是队列的 尾部 ，哪一端是 头部 。 我们假设队列的尾部在列表的 位置0 处。 如此一来，便可以使用  insert  函数向 队列的尾部 添加新元素。 pop  则可用于移除 队列头部的元素 （列表中的最后一个元素）。这意味着 添加操作 的时间复杂度是O(n)， 移除操作 则是O(1)。?

队列实现代码如下：

class Queue:
    def __init__(self):
        self.items = []            # 构建空队列
        print("你创建了一个队列")
    def isEmpty(self):
        return self.items ==[]     # 判断是否为空
    def enqueue(self,item):
        self.items.insert(0, item) # 在队列尾部(列表左端)插入元素
        print("你在队列尾部插入了一个%s" % item)
    def dequeue(self):
        print("你在队列头部移除了一个元素")
        return self.items.pop()    # 在队列头部(列表右端)移出元素
    def size(self):
        return len(self.items)     # 队列(列表)长度
    def look(self):
        print(self.items)

下图展示了队列的操作及其返回结果：

总结

本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注的更多内容!    

查看更多关于Python数据结构与算法中的队列详解(1)的详细内容...