什么是队列?
队列是一种有次序的数据集合,其特征是新数据项的添加总发生在一端(通常称为"尾rear端",而现存数据项的另一端的移除总发生在另一端(通常称为"首front"端。当数据项加入队列，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首
新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首，这种次序安排的原则成为（FIFO：First-in-first-out)先进先出
队列的例子出现在我们日常生活的方方面面:排队
队列仅有一个入口和一个出口
抽象数据类型Queue
Queue():创建一个空队列对象,返回Queue对象;
enqueue(item):将数据项item添加到队尾,无返回值;
dequeue():从队首移除数据项,返回值为队首数据项,队列被修改
isEmpty():测试是否空队列,返回值为布尔值
size():返回队列中数据项的个数
peek():查看队列最早的元素
实现:
class Queue:
def __init__(self):
self.items = []
def enqueue(self,item):
return self.items.append(item)
def dequeue(self,):
return self.items.pop(0)
def isEmpty(self):
return len(self.items)==0
def size(self):
return len(self.items)
def peek(self):
return self.items[0]
队列的应用
热土豆问题(约瑟夫问题)
传说犹太人反叛罗马人,落到困境,约瑟夫和39人决定殉难,坐成一圈儿,报数1~7,报到7的人由旁边杀死,结果约瑟夫给自己安排了个位置,最后活了下来。
算法流程：
- 模拟程序采用队列来存放所有参加游戏的人名，按照传递土豆的方向从队首排到队尾，游戏时，队首始终是持有土豆的人
- 模拟游戏开始，只需要将队首的人出队，随机再到队尾入队，算是土豆的一次传递，传递到num次后，将队首的人移除，不再入队如此反复，直到队列中剩余一人
def hotpotato(namelist,num):#放名字的列表,num为数到几出列
q = Queue()
for name in namelist:
q.enqueue(name)
while q.size()>1:
for i in range(num):
q.enqueue(q.dequeue())
q.dequeue()
return q.dequeue()
print(hotpotato(['江苏','北京','南京','上海'],4))
队列的应用2 模拟打印任务
一台计算机可能连着一台打印机，有些打印机连在局部网络上，用户可以通过网络把文件送去打印。
由于打印机速度有限，用户的使用需求也会有各种变化，有可能出现这样的情况：当打印机正在工作，打印一个文件的过程中，又有用户通过某些方式送来一个或几个需要打印的文件，对于多台机器共享的网络打印机，经常会出现接受到一些打印任务，但却由于正在工作不能立即楚处理它们的情况。在这些情况中，待打印文件都需要缓存。
打印机的管理程序（可能出现在不同层次）管理着一个缓存打印任务的队列。接到新任务时，如果打印机正在忙，管理程序就将该任务放入队列。一旦打印机完成了当前工作，管理程序就查看队列，取出其中最早的任务送给打印机。
**模拟流程：
- 一个实验室任意一小时内,大约有10名学生在.在这一个小时中,每个人会发起2次左右的打印,每次1-20页
打印机:以草稿模式打印:每分钟10页,正常模式,每分钟5页
问题是:怎么设定打印机的模式,让大家都不会等太久的前提下尽量提高打印机质量
这是一个典型的决策支持问题,但无法通过规则直接进行计算
我们要用一段程序来模拟这种打印任务场景,然后对程序运行结果进行分析,以支持对打印机模式设定的决策
首先对问题进行建模
-
1对象:打印任务 打印队列 打印机
打印任务属性:提交时间 打印页数
打印队列属性: 具有FIFO性质的打印任务队列(first input first output)
打印机属性:打印速度 是否忙 -
2过程:生成和提交打印任务
确定生成概率:实例为每小时会有10个学生提交的20个作业,这样,概率是每180秒会有1个作业生成并提交,概率为每秒1/180
确定打印页数:实例是1-20页,那么就是1-20页之间的概率相同 -
3过程:实施打印
当前的打印作业:正在打印的作业
打印结束倒计时:新作业开始打印时开始倒计时,回0表示打印完毕,可以处理下一个作业 -
4模拟时间:
统一的时间框架:以最小单位(秒)均匀流逝的时间,设定结束时间
同步所有过程:在一个单位时间里,对生成打印任务和实施打印两个过程各处理一次
打印任务:模拟流程
1创建打印队列对象
2时间按照秒的单位流逝
按照概率生成打印作业,加入打印队列
如果打印机空闲,且队列不空,则取出队首作业打印记录此作业等待时间
如果打印机忙,则按照打印速度进行1秒打印
如果当前作业打印完成,则打印机进入空闲
3时间用尽,开始统计平均等待时间
作业的等待时间:
生成作业时,记录生成的时间戳
开始打印时,当前时间减去生成时间即可
作业的打印时间
生成作业时,记录作业的页数
开始打印时,页数除以打印速度即可
**
mport random
#打印机属性:打印速度 是否忙
class Printer:
def __init__(self,ppm):
self.pagerate=ppm#打印速度
self.current_task=None#打印任务
self.time_remaining=0#倒计时
def tick(self):#打印1秒.有任务时,打印结束倒计时-1.当倒计时为0,打印完成
if self.current_task != None:
self.time_remaining = self.time_remaining -1
if self.time_remaining <= 0:
self.current_task = None
def busy(self):#是否忙
if self.current_task != None:
return True
else:
return False
def start_next(self,new_task):#打印新作业
self.current_task=new_task
self.time_remaining=new_task.getPages()*self.pagerate
class Task:
#打印任务属性:提交时间 打印页数
def __init__(self,time):
self.timestamp = time#生成时间戳
self.pages = random.randrange(1,21)#实例是1-20页,那么就是1-20页之间的概率相同
def getStamp(self):
return self.timestamp
def getPages(self):
return self.pages
def waitTime(self,current_time):
return current_time - self.timestamp #等待时间:
# 生成作业时,记录生成的时间戳
# 开始打印时,当前时间减去生成时间即可
def newPrintTask():#概率是每180秒会有1个作业生成并提交,概率为每秒1/180.所以生成新任务的概率是1/180
num = random.randrange(1,181)
if num == 180:
return True
else:
return False
def simulation(num_second,page_perminute):
labprinter = Printer(page_perminute)
print_queue=Queue()
waitingtimes=[]
for currentSecond in range(num_second):
if newPrintTask():
task = Task(currentSecond)
print_queue.enqueue(task)
if(not labprinter.busy()) and (not print_queue.isEmpty()):
nexttask = print_queue.dequeue()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.tick()
averageWait = sum(waitingtimes)/len(waitingtimes)
print('Average Wait %6.2f secs %3d tasks remaining.'%(averageWait,print_queue.size()))
for i in range(10):
simulation(3600,1)
class Task:
# 任务初始化
def __init__(self, time):
# time 为传入的任务创建时间，也就是入队时间
self.in_time = time
self.pages = random.randrange(1, 21) # 随机生成1到20页之间的页数
# 返回任务需要打印的页数
def getPage(self):
return self.pages
def waitTime(self, out_time):
# out_time为当前时间戳
return out_time - self.in_time
class Printer:
# 打印机初始化
def __init__(self, timeperpage):
# timeperpage 为每页打印所需要的时间，设定好后便是恒定的值
self.timeperpage = timeperpage
self.current_task = None # 记录当前正在处理的任务
self.remaining_time = 0 # 记录当前任务的剩余处理时间
# 返回打印机中是否有任务
def isBusy(self):
return self.current_task != None
# 载入新的任务
def loadTask(self, next_task):
# next_task 为新的任务
self.current_task = next_task
self.remaining_time = next_task.getPage() * self.timeperpage # 计算新的剩余打印时间
# 打印
def printTask(self):
if self.isBusy(): # 有任务需要处理
self.remaining_time -= 1 # 打印，也就是将剩余打印时间减一
if self.remaining_time <= 0: # 当前任务打印结束
self.current_task = None
else: # 空闲中
pass
def simulation(total_time, timeperpage):
# total_time为总的实验时间，timeperpage为每页打印所需要的时间
waiting_time = [] # 记录每个任务的等待时间
printer = Printer(timeperpage) # 初始化打印机
waitQueue = Queue() # 初始化任务等待队列
for second in range(total_time):
rand_num = random.randrange(1, 181) # 产生1到180之间的随机数
if rand_num == 1:
new_task = Task(second) # 产生新任务
waitQueue.enqueue(new_task) # 新任务进入等待队列
if (not printer.isBusy()) and (not waitQueue.isEmpty()): # 打印机空闲并且有任务在等
next_task = waitQueue.dequeue() # 弹出下一个任务
waiting_time.append(new_task.waitTime(second)) # 计算并记录等待时间
printer.loadTask(next_task) # 载入新的任务
printer.printTask() # 打印
average_time = sum(waiting_time) / len(waiting_time)
return average_time,waitQueue.size()
def main():
timeperpage = 6#打一页所需时间
total_time = 36000 #10小时
print("-----------------")
for i in range(10):
average_time,wait_ = simulation(total_time,timeperpage)
print("平均等待打印时间为：%.5f 秒"%average_time)
print('剩余等待%3d'%(wait_))
print("-----------------")
if __name__ == "__main__":
main()
转载：https://blog.csdn.net/rhythmcc/article/details/105435758