队列的实现与应用

抽象数据类型queue的定义

实现了以下数据结构与操作方法的数据类型称为queue

一、队列的python实现

• 方法一：标准库

from queue import Queue

基于list实现

class Queue():def __init__(self):self.items = []def enqueue(self, item):#左边为rear,右边为front;即右边为队首#insert(0)操作为O（n)self.items.insert(0, item)def dequeue(self):return self.items.pop()def isEmpty(self):return self.items == []def size(self):return len(self.items)

二、队列应用

2.1 hot potato问题

from queue import Queue#热土豆/击鼓传花问题;从0开始数 def hot_potato(players, num):q = Queue()for player in players:q.enqueue(player)while q.size() > 1:for i in range(num):q.enqueue(q.dequeue())q.dequeue()#循环结束后，只剩下一个playerreturn q.dequeue()if __name__ == '__main__':print(hot_potato(["Bill","David","Susan","Jane","Kent","Brad"],7))

2.2模拟打印机平均等待时间

• 每180秒产生一个打印task
• 每个task打印1-20页
• 打印机速率有两种：10页/min,5页/min
• 求1小时内task的平均等待时间（进入队列到弹出队列）以及未完成的task数目

关键：模拟的本质：for i in range(3600) ,遍历一次代表1秒，而非真正的时间戳

from queue import Queue from random import randrangeclass Printer():def __init__(self, pagerate):#参数1：当前处理任务剩余秒数；参数2：当前任务对象；参数3：每分钟打印张数self.seconds_ramianing = 0self.current_task = Noneself.pagerate = pageratedef start_task(self,task):self.current_task = taskself.seconds_ramianing = task.get_page()* 60/self.pageratedef tick(self):#减小一个点数；消耗一秒if self.current_task != None:self.seconds_ramianing -= 1if self.seconds_ramianing == 0:self.current_task = Nonedef busy(self):return self.current_task != Noneclass Task():def __init__(self, current_time):self.page = randrange(1,21)self.timestamp = current_timedef wait_time(self,current_time):return current_time - self.timestampdef get_page(self):return self.pagedef task_appear():#随机发生器，看能否在【1,180】内命中180，命中即判定该秒发生了一个task#该函数执行平均180次有一次成功num = randrange(1,181)return num == 180def simulation(sum_seconds,pages_per_min):#参数1：总的模拟时间；参数2：打印机速率printer = Printer(pages_per_min)task_queue = Queue()wait_times = []for i in range(sum_seconds):#秒为最小模拟单位#模拟task是否产生if task_appear():newtask = Task(i)task_queue.enqueue(newtask)#模拟是否提交task队列中的taskif not printer.busy() and not task_queue.isEmpty():current_task = task_queue.dequeue()wait_times.append(current_task.wait_time(i))printer.start_task(current_task)#printer计时也要减小printer.tick()#计算平均等待时间ave_wait_time = sum(wait_times)/len(wait_times)print('Average waiting time is {}, and {} tasks remaining!'.format(ave_wait_time,task_queue.size()))if __name__ == '__main__':for i in range(10):simulation(3600, 5)print('*'*100)for i in range(10):simulation(3600, 10)

总结

以上是生活随笔为你收集整理的队列的实现与应用的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。