网站设计专业有哪些课程,陈木胜拍完怒火重案了吗,德阳小程序开发,建设律师推广网站目录
一、何谓队列
二、队列抽象数据类型
三、用Python实现队列
四、模拟#xff1a;传土豆
五、模拟#xff1a;打印任务
5.1 主要模拟步骤
5.2 Python实现 一、何谓队列
队列是有序集合#xff0c;添加操作发生在“尾部”#xff0c;移除操作则发生在“头部”。新…目录
一、何谓队列
二、队列抽象数据类型
三、用Python实现队列
四、模拟传土豆
五、模拟打印任务
5.1 主要模拟步骤
5.2 Python实现 一、何谓队列
队列是有序集合添加操作发生在“尾部”移除操作则发生在“头部”。新元素从尾部进入队列然后一直向前移动到头部直到成为下一个被移除的元素。
最新添加的元素必须在队列尾部等待在队列中时间最长的元素则排在最前面。这种排序原则被称作FIFO即先进先出也称先到先得。
二、队列抽象数据类型
队列抽象数据类型由下面的结构和操作定义。如前所述队列是元素的有序集合添加操作发生在其尾部移除操作则发生在头部。队列的操作顺序是FIFO它支持以下操作。
Queue()创建一个空队列。它不需要参数且会返回一个空队列。enqueue(item)在队列的尾部添加一个元素。它需要一个元素作为参数不返回任何值。dequeue()从队列的头部移除一个元素。它不需要参数且会返回一个元素并修改队列的内容。isEmpty()检查队列是否为空。它不需要参数且会返回一个布尔值。size()返回队列中元素的数目。它不需要参数且会返回一个整数。
在“队列内容”一列中队列的头部位于右端。
三、用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)qQueue()
print(q.isEmpty())q.enqueue(dog)
q.enqueue(4)
qQueue()
print(q.isEmpty())q.enqueue(4)
q.enqueue(dog)
q.enqueue(True)
print(q.size())print(q.isEmpty())q.enqueue(8.4)
print(q.dequeue())
print(q.dequeue())
print(q.size()) 四、模拟传土豆
展示队列用法的一个典型方法是模拟需要以FIFO方式管理数据的真实场景。考虑这样做一个儿童游戏传土豆。在这个游戏中孩子们围成一圈并依次尽可能快地传递一个土豆。某个时刻大家停止传递此时手里有土豆的孩子就得退出游戏。重复上述过程直到只剩下一个孩子。
我们将针对传土豆游戏实现通用的模拟程序。该程序接受一个名字列表和一个用于计数的常数num并且返回最后一人的名字。
我们使用队列来模拟一个环。假设握着土豆的孩子位于队列的头部。在模拟传土豆的过程中程序将孩子的名字移出队列然后立刻将其插入队列的尾部。随后这个孩子会一直等待直到再次到达队列的头部。在出列和入列num次之后此时位于队列头部的孩子出局新一轮游戏开始。如此反复直到队列中只剩下一个名字队列的大小为1。
from pythonds.basic import Queue
def hotpotato(namelist,num):simqueueQueue()for name in namelist:simqueue.enqueue(name)while simqueue.size()1:for i in range(num):simqueue.enqueue(simqueue.dequeue())simqueue.dequeue()return simqueue.dequeue()print(hotpotato([Bill,David,Susan,Jane,Kent,Brad],7)) 五、模拟打印任务
考虑计算机实验室里的这样一个场景在任何给定的一小时内实验室里都有约10个学生。他们在这一小时内最多打印2次并且打印的页数从1到20不等。实验室的打印机比较老旧每分钟只能以低质量打印10页。可以将打印质量调高但是这样做会导致打印机每分钟只能打印5页。降低打印速度可能导致学生等待过长时间。
可以通过构建一个实验室模型来解决该问题。我们需要学生、打印任务和打印机构建对象。当学生提交打印任务时我们需要将它们加入等待列表中该列表是打印机上的打印任务队列。当打印机执行完一个任务后它会检查该队列看看其中是否还有需要处理的任务。我们感兴趣的是学生平均需要等待多久才能拿到打印好的文章。这个时间等于打印任务在队列中的平均等待时间。
在模拟时需要应用一些概率学知识。举例来说学生打印的文章可能有1~20页。如果各页数出现的概率相等那么打印任务的实际时长可以通过1~20的一个随机数来模拟。
如果实验室有10个学生并且在一小时内每个人都打印两次那么每小时平均就有20个打印任务。每小时20个任务相当于每180秒1个任务。
可以通过1~180的一个随机数来模拟每秒内产生打印任务的概率。如果随机数正好是180那么就认为有一个打印任务被创建。注意可能会出现多个任务接连被创建的情况也可能很长一段时间内没有任务。
5.1 主要模拟步骤
1创建一个打印任务队列。每一个任务到来时都会有一个时间戳。一开始队列是空的。
2针对每一秒currentSecond执行以下操作。
是否有新创建的打印任务如果是以currentSecond作为其时间戳并将该任务加入到队列中。如果打印机空闲并且有正在等待执行的任务执行以下操作
从队列中取出第一个任务并提交给打印机用currentSecond减去该任务的时间戳以此计算其等待时间将该任务的等待时间存入一个列表以备后用根据该任务的页数计算执行时间。
打印机进行一秒的打印同时从该任务的执行时间中减去一秒。如果打印任务执行完毕或者说任务需要的时间减为0则说明打印机回到空闲状态。
3当模拟完成后根据等待时间列表中的值计算平均等待时间。
5.2 Python实现
我们创建3个类Printer、Task和PrintQueue。它们分别模拟打印机、打印任务和队列。
Printer类需要检查当前是否有待完成的任务。如果有那么打印机就处于工作状态并且其工作所需的时间可以通过要打印的页数来计算。其构造方法会初始化打印速度即每分钟打印多少页。tick方法会减量计时并且在执行任务之后将打印机设置成空闲状态。
class Printer:def __init__(self,ppm):self.pagerateppmself.currentTaskNoneself.timeRemaining0def tick(self):if self.currentTask ! None:self.timeRemainingself.timeRemaining-1if self.timeRemaining0:self.currentTaskNonedef busy(self):if self.currentTask!None:return Trueelse:return Falsedef startNext(self,newtask):self.currentTasknewtaskself.timeRemainingnewtask.getPages()*60/self.pagerate
Task类代表单个打印任务。当任务被创建时随机数生成器会随机提供页数取值范围是1~20.我们使用random模块中的randrange函数来生成随机数。
import random
class Task:def __init__(self,time):self.timestamptimeself.pagesrandom.randrange(1,21)def getStamp(self):return self.timestampdef getPages(self):return self.pagesdef waitTime(self,currenttime):return currenttime-self.timestamp
主模拟程序实现了之前描述的算法。printQueue对象是队列抽象数据类型的实例。布尔辅助函数newPrintTask判断是否有新创建的打印任务。我们再一次使用random模块中的rangrange函数来生成随机数不过这一次的取值范围是1~180.平均每180秒有一个打印任务。通过从随机数中选取180可以模拟这个随机事件。该模拟程序允许设置总时间和打印机每分钟打印多少页。
class Printer:def __init__(self, ppm):self.pagerate ppmself.currentTask Noneself.timeRemaining 0def tick(self):if self.currentTask ! None:self.timeRemaining self.timeRemaining - 1if self.timeRemaining 0:self.currentTask Nonedef busy(self):if self.currentTask ! None:return Trueelse:return Falsedef startNext(self, newtask):self.currentTask newtaskself.timeRemaining newtask.getPages() * 60 / self.pagerateimport randomclass Task:def __init__(self, time):self.timestamp timeself.pages random.randrange(1, 21)def getStamp(self):return self.timestampdef getPages(self):return self.pagesdef waitTime(self, currenttime):return currenttime - self.timestampfrom pythonds.basic import Queue
import randomdef simulation(numSeconds,pagesPerMinute):labprinterPrinter(pagesPerMinute)printQueueQueue()waitingtimes[]for currentSecond in range(numSeconds):if newPrintTask():taskTask(currentSecond)printQueue.enqueue(task)if (not labprinter.busy()) and (not printQueue.isEmpty()):nexttaskprintQueue.dequeue()waitingtimes.append(nexttask.waitTime(currentSecond))labprinter.startNext(nexttask)labprinter.tick()averageWaitsum(waitingtimes)/len(waitingtimes)print(Average Wait %6.2f secs %3d tasks remaining.%(averageWait,printQueue.size()))def newPrintTask():numrandom.randrange(1,181)if num180:return Trueelse:return Falsefor i in range(10):simulation(3600,5)
