队列 Queue
1. 简介
队列是一种有次序的数据集合 ，其特征是数据项的添加和移除分别发生在该集合的两端：
- 数据项的添加发生在尾端（rear）
- 现存数据的移除发生在首端（front）
这种次序安排原则称为（FIFO：first in first out 先进先出）
例子：
1. 面向多用户的打印机
2. 计算机系统中的进程调度
3. 键盘缓冲
ADT数据类型 Queue的python实现（用list来实现queue，index = 0 为rear端, 在这种情况下，enqueu的复杂度为O(n), dequeue的复杂度为O(1) )
class Queue:
def __init__(self): #创建一个空队列，返回值为Queue对象
self.items = []
def enqueue(self,item): # 在队列尾端添加数据项item，无返回值
self.items.insert(0.item)
def dequeue(self): # 从队首移除一个数据项，返回修改后的数据项
return self.items.pop()
def isEmpty(self): # 判断队列是否为空，返回值为bool型
return self.items == []
def size(self): # 返回队列中数据项的个数
return len(self.items)
2. Queue的应用
2.1 热土豆问题
传烫手的热土豆，鼓声听的时候，手里有土豆的小孩要出列（击鼓传花）
用队列来实现热土豆问题的算法，参加游戏的人名列表，以及传土豆的次数num，返回最后剩下的人名
names = ['Bill','David','Susan','Jane','Joe','Kent']
def passPotato(names,num):
simQueue = Queue()
for name in names:
simQueue.enqueue(name)
while simQueue.size() > 1:
for i in range(num):
simQueue.enqueue(simQueue.dequeue())
simQueue.dequeue()
return simQueue.dequeue()
print(passPotato(names, 7))
2.2 打印任务
模拟算法： 打印任务
一个实验室内，在任意一小时内，大约有10名学生在场，这一小时中，没人会发起2次左右的打印，每次1～20页。
打印机的性能 ：
草稿模式打印：每分钟10页
正常模式打印：每分钟5页
现在设计一段程序模拟打印的过程，然后对程序运行结果进行分析，以支持打印机模式设定的决策。
建模对象：打印机，打印队列，打印任务
| 打印机属性： | 提交时间 | 打印页数 |
| 打印队列属性： | 具有FIFO性质的打印任务队列 | |
| 打印机的属性： | 打印速度 | 是否忙 |
对打印任务的生成进行建模
确定生成概率：20/60*60 = 1/180 # 平均每180秒会有一个task
每个任务的打印页数 1～20，概率相等
对打印过程进行建模
打印结束倒计时：新作业开始打印时开始倒计时，回0表示打印完成，可以处理下一个任务
模拟时间
同一时间的框架：秒
同步所有过程：在一个时间单位内，对生成打印任务和实施打印时间两个过程各处理一次
整个流程的模拟：
1. 创建打印队列对象
2. 时间按照秒的单位流逝
- 按照概率生成打印作业，加入打印队列
- 如果打印机空闲，且队列不空，则取出队首作业打印，记录此作业等待的时间
- 如果打印机忙，则按照打印速度进行1秒打印
- 如果当前作业但因完成，则打印机进入空闲
作业的等待时间：
- 生成作业时， 记录生成的时间戳
- 开始打印时， 当前时间减去生成时间即可
作业的打印时间：
- 生成作业时，记录作业的页数。 开始打印时，页数除以打印速度即可
import random
class Printer:
def __init__(self,ppm):
self.pagerate = ppm # 打印速度 pages/min
self.currentTask = None # 打印任务
self.timeRemaining = 0 # 打印时间
def tick(self): # 打印1秒
if self.currentTask != None:
self.timeRemaining = self.timeRemaining -1
if self.timeRemaining <= 0:
self.currentTask = None
def busy(self): #判断打印机是否忙
if self.currentTask != None:
return True
else:
return False
def startNext(self,newTask): #打印新作业
self.currentTask = newTask
self.timeRemaining = newTask.getPages()*60/self.pagerate #打印新作业所需要的秒数
class Task:
def __init__(self,time):
self.timestamp = time #任务生成时间戳
self.pages = random.randrange(1,21) # 随机生成打印页数
def getStamp(self): #获取任务生成时间戳
return self.timestamp
def getPages(self): # 获取任务页数
return self.pages
def waitTime(self,currenttime): # 任务等待时间
return currenttime - self.timestamp
def newPrintTask(): #根据概率判断是否生成新的任务
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("Average Wait %6.2f secs %3d tasks remaining." %(averageWait,printQueue.size()))
for i in range(20):
simulation(3600,5)
标签：打印机,队列,self,打印,Queue,数据结构,def From： https://www.cnblogs.com/wujiadeqiao/p/16656394.html