python队列的实现,数据结构与算法python实现

　　本文主要详细介绍Python的队列。本文中的示例代码非常详细，具有一定的参考价值。感兴趣的朋友可以参考一下，希望能帮到你。

　　00-1010模拟打印机任务队列流程主要模拟步骤：构建队列程序模拟打印程序模拟打印流程(附注释)总结

目录

　　计算机科学中有很多排队的例子。例如，计算机实验室中有10计算机，所有这些计算机都连接到同一台打印机。当学生需要打印时，他们的打印任务将进入队列.队列中的第一个作业是要执行的打印作业。如果一个任务在队列的后面，它必须等到所有前面的任务完成。

　　学生向共享打印机发送打印请求。这些打印作业存储在队列中，并按照先到先得.的顺序执行。此设置可能会导致许多问题。最重要的是打印机是否能处理一定的工作量。如果没有，学生可能会因为等待时间太长而错过课程。

　　考虑一个计算机实验室的场景：在任何给定的时间里，实验室里都有10的学生。他们在这一小时内最多能打印出《2时报》，打印的页数来自1到20页不等.实验室的打印机老旧，每分钟只能打印出质量很低的10页。您也可以提高打印质量，但这将导致每分钟打印机只打印5页面。降低打印速度可能会导致学生等待时间过长。那么，我应该如何设置打印速度呢？

　　这个问题可以通过构建模型来解决。我们需要为学生,打印任务和打印机.构建对象，当学生提交给打印任务,时，我们需要将它们添加到打印机的任务队列.中。当打印机完成一项任务时，它会检查队列以查看是否有任何任务要处理。我们感兴趣的是学生们平均要等多久才能拿到印刷的文章。该时间等于队列中打印作业的平均等待时间。

　　在模拟中应该应用一些概率知识。例如，学生可能打印1-20页的文章。如果每页出现的概率相等，则可以通过从1到20模拟一篇文章的随机页数来计算打印作业的实际时长。

　　如果实验室里有10的学生，一小时每个人打印5次，那么两.平均有每小时的打印工作要回答这个问题，20需要考虑任务与时间的比例。每小时20个任务相当于每180秒1个任务。

　　在任意一秒，创建一个打印请求的概率是多少？模拟的本质。我们希望在公共参数已知的情况下，尽可能精确地进行模拟。

模拟打印机任务队列过程

　　1.创建一个可以通过1~180的一个随机数来模拟每秒内产生打印请求的概率(1/180的概率)。如果随机数正好是180，那么就认为有 一个打印请求被创建。注意，可能会出现多个请求接连被创建的情况，也可能很长一段时间内都没有请求。这就是.起初在打印任务队列的每个使团都会有一个到来.队列是空的。

　　2.每一秒钟(时间戳)，做以下事情。

　　是否有新创建的打印作业？如果是，将currentSecond作为其时间戳，并将任务添加到队列中。如果打印机空闲，有任务等待执行，则执行以下操作：从currentSecond中取出第一个任务，提交给打印机；使用队列.

　　Second 减去该任务的时间戳，以此计算其等待时间；

　　3.当模拟完成之后，根据等待时间列表中的值计算平均等待时间。

​构建队列程序

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) # 队列(列表)长度
　　

模拟打印程序

import random
　　# 模拟打印机
　　class Printer:
　　 # 打印机初始化
　　 def __init__(self, ppm):
　　 self.pagerate = ppm # 打印速度 页/分钟
　　 self.currentTask = None # 现有任务
　　 self.timeRemain = 0 # 该任务所需时间
　　 # 打印任务倒计时 0代表打印完成
　　 def tick(self):
　　 # 如果打印机正在执行任务
　　 if self.currentTask != None:
　　 # 该任务执行时间 = 执行时间 - 1（执行时间倒计时）
　　 self.timeRemaining = self.timeRemaining - 1 
　　 if self.timeRemaining <= 0: # 该任务执行时间 <= 0
　　 self.currentTask = None # 该任务执行完毕
　　 # 判断打印机是否空闲
　　 def busy(self):
　　 if self.currentTask != None:
　　 return True
　　 else:
　　 return False
　　 # 打印机接受新任务
　　 def startNext(self, newtask):
　　 self.currentTask = newtask
　　 # 新打印任务需要时间 = 新任务页数 * (60 / 每分钟打印多少页的速度)
　　 # (60 / 每分钟打印多少页的速度) = 每打印一页所需要的秒数
　　 self.timeRemaining = newtask.getPages() * (60 / self.pagerate)
　　# 模拟单个任务的属性
　　class Task:
　　 # 任务初始化
　　 def __init__(self, time):
　　 self.timestamp = time # 创建任务的时间点
　　 self.pages = random.randrange(1, 21) # 任务页数 在 1~20 间随机生成
　　 def getStamp(self):
　　 return self.timestamp # 获取任务创建的时间点
　　 def getPages(self):
　　 return self.pages # 获取任务的页数
　　 def waitTime(self, currenttime):
　　 # 任务的等待时间 = 当前时间 - 任务创建的时间点
　　 return currenttime - self.timestamp 
　　# 模拟学生创建的新打印请求
　　def newPrintTask():
　　 # 打印请求是一个随机事件
　　 # 通过1~180之间的一个随机数来模拟每秒内产生打印请求的概率
　　 # 如果随机数正好是180，那么就认为有一个打印请求被创建。
　　 num = random.randrange(1, 181)
　　 if num == 180:
　　 return True
　　 else:
　　 return False
　　# 模拟打印过程
　　def simulation(numSeconds, pagesPerMinute):
　　 labprinter = Printer(pagesPerMinute)
　　 printQueue = Queue()
　　 waitingtimes = []
　　 for currentSecond in range(numSeconds):
　　 if newPrintTask():
　　 task = Task(currentSecond)
　　 printQueue.enqueue(task)
　　 if(not labprinter.busy())and(not printQueue.isEmpty()):
　　 nexttask = printQueue.dequeue()
　　 waitingtimes.append(nexttask.waitTime(currentSecond))
　　 labprinter.startNext(nexttask)
　　 labprinter.tick()
　　 averageWait = sum(waitingtimes)/len(waitingtimes)
　　 print("平均等待 %6.2f 秒，还有 %3d 个任务等待处理"
　　 % (averageWait, printQueue.size()))
　　

模拟打印过程（有注释）

def simulation(numSeconds, pagesPerMinute):
　　 # numSeconds-时间段
　　 # pagesPerMinute-打印速度，页/分钟
　　 labprinter = Printer(pagesPerMinute) # 创建打印机
　　 printQueue = Queue() # 创建打印机任务队列
　　 waitingtimes = [] # 创建等待时间数据样本列表
　　 for currentSecond in range(numSeconds): # 一次循环代表一秒
　　 if newPrintTask(): # 如果 有打印请求创建
　　 task = Task(currentSecond) # 创建打印任务并记录当前时间点
　　 printQueue.enqueue(task) # 打印任务进入打印机任务队列
　　 # 如果 打印机空闲 并且 打印机任务队列有任务
　　 if(not labprinter.busy())and(not printQueue.isEmpty()):
　　 nexttask = printQueue.dequeue() # 从队列取出新任务
　　 # 根据当前时间点计算新任务在任务队列里的等待时间 并将等待时间记录进样本列表
　　 waitingtimes.append(nexttask.waitTime(currentSecond))
　　 labprinter.startNext(nexttask) # 开始执行新任务 打印机进入忙碌状态
　　 labprinter.tick() # 每循环一次 当前打印任务执行倒计时减少一秒
　　 averageWait = sum(waitingtimes)/len(waitingtimes)
　　 print("平均等待 %6.2f 秒，还有 %3d 个任务等待处理" % (averageWait, printQueue.size()))
　　

　　需要注意的是，时间戳是我们根据循环模拟出来的，我们给定了numSeconds 时间段后，每循环一次相当于时间过了一秒。

　　虽然每次模拟的结果不一定相同。但对此我们不需要在意。这是由于随机数的本质导致的。我们感兴趣的是当参数改变时结果出现的趋势。​

　　下面是一些结果：

　　我们根据模拟得到了打印机在两种速度下，一小时内的任务执行情况的参考数据。可以很明显的看到，当打印质量提升后，学生平均等待时间相比低质量情况下显著增加，并且任务处理未完成的次数也出现了增加，所以设置打印机为低质量模式是最合适的。

总结

　　本篇文章就到这里了，希望能够给你带来帮助，也希望您能够多多关注盛行IT软件开发工作室的更多内容!

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。