操作
- Queue() 创建一个空的队列
- enqueue(item) 往队列中添加一个item元素
- dequeue() 从队列头部删除一个元素
- is_empty() 判断一个队列是否为空
- size() 返回队列的大小
class Queue(object):
"""队列"""
def __init__(self):
self.items = [] def is_empty(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) if __name__ == "__main__":
q = Queue()
q.enqueue("hello")
q.enqueue("world")
q.enqueue("itcast")
print q.size()
print q.dequeue()
print q.dequeue()
print q.dequeue()
烫手山芋
from pythonds.basic.queue import Queue def hotPotato(namelist, num):
simqueue = Queue()
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))
模拟：打印机
主要模拟步骤
- 创建打印任务的队列，每个任务都有个时间戳。队列启动的时候为空。
-
每秒（currentSecond）：
- 是否创建新的打印任务？如果是，将
currentSecond作为时间戳添加到队列。 - 如果打印机不忙并且有任务在等待
- 从打印机队列中删除一个任务并将其分配给打印机
- 从
currentSecond中减去时间戳，以计算该任务的等待时间。 - 将该任务的等待时间附件到列表中稍后处理。
- 根据打印任务的页数，确定需要多少时间。
- 打印机需要一秒打印，所以得从该任务的所需的等待时间减去一秒。
- 如果任务已经完成，换句话说，所需的时间已经达到零，打印机空闲。
- 是否创建新的打印任务？如果是，将
- 模拟完成后，从生成的等待时间列表中计算平均等待时间。
# 模拟打印机
class Printer:
def __init__(self, ppm):
self.pagerate = ppm
self.currentTask = None
self.timeRemaining = 0 def tick(self):
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 # 模拟任务
import random 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 #模拟打印机任务队列
from pythonds.basic.queue import Queue import random 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())) def newPrintTask():
num = random.randrange(1,181)
if num == 180:
return True
else:
return False for i in range(10):
simulation(3600,5)