首页 > 编程语言 > 详细

python之队列

时间:2021-09-11 21:18:52      阅读:15      评论:0      收藏:0      [点我收藏+]

  1.1、何谓队列

  队列是有序集合,添加操作发生在“尾部”,移除操作则发生在“头部”。新元素从尾部进入队列,然后一直向前移动到头部,知道成为下一个被移除的元素。

  最新添加的元素必须在队列的尾部等待,在队列中时间最长的元素则排在最前面。这种排序元素被称作FIFO(first-in first-out),即先进先出,也称为先到先得。

  在日常生活中,我们经常排队,这便是最简单的例子。进电影院要排队,在超市结账要排队,买咖啡也要排队(等着从盘子栈中去盘子)。好的队列只允许一头进,另一头出,不可能发生插队或者中途离开的情况。下图展示了一个由python数据对象组成的简单队列。

技术分享图片

 

   计算机科学中也有众多的队列例子。我的计算机实验室有30台计算机,他们斗鱼同一台打印机相连。当学生需要打印的时候,他们的打印任务会进入一个队列。该队列中的第一个任务就是即将执行打印任务。如果一个任务排在队列的最后面,那么它必须等到前面的任务都执行完毕后才能执行。我们稍后会更深入地探讨这个有趣的例子。

  操作系统使用一些队列来控制计算机进程。调度机制往往基于一个队列算法,其目标是尽可能快的执行程序,同事服务尽可能多的用户。在打字时,我们有时会发现字符出现的速度比击键速度慢。这是由于计算机正在做其他的工作。击键操作被放入一个类型于队列的缓冲区,以便对应的字符按正确的顺序显示。

  1.2、队列抽象数据类型

  队列抽象数据类型由下面的结构和操作定义。如前所述,队列是元素的有序集合,添加操作发生在其尾部,移除操作则发生在头部。队列的操作顺序是FIFO,它支持一下操作。

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

  1.3、用python实现队列

  创建一个新来实现队列抽象数据类型是十份合理的。像之前一样,我们利用简洁强大的列表来实现队列。

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

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)

 

python之队列

原文:https://www.cnblogs.com/mtfan01/p/15251317.html

(0)
(0)
   
举报
评论 一句话评论(0
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!