队列是一种有次序的数据集合，其特征是，新数据项的添加总发生在一端（通常称为尾端（rear））而现存数据类型的移除总发生在另一端（通常称为首段（front））。
当数据项加入队列，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首。
抽象数据类型 Queue 是一个有次序的数据集合。、数据项仅添加到尾端 rear；而仅从首端 front 移除。
抽象数据类型Queue由如下操作定义：
Queue()：创建一个空队列对象，返回值为Queue对象；
enqueue(item)：将数据项item添加到队尾，无返回值；
dequeue()：从队首移除数据项，返回值为队首数据项，队列被修改；
isEmpty()：测试是否空队列，返回值为布尔值
size()：返回队列中数据项的个数。
class Queue: # 创造空队列
def __init__(self):
self.items = []
def isEmpty(self): # 判断空队列
return self.items == []
def enqueue(self, item): # 将item添加队尾
self.items.insert(0, item)
def dequeue(self): # 将队首删除
return self.items.pop()
def size(self): # 队列中数据个数
return len(self.items)2.1 热土豆（击鼓传花）（约瑟夫环）
给定一个数，从 1 开始数，每数到给定数的人出局，直到仅剩一人。
用队列来实现整个问题的算法，给定参与游戏的人名列表，以及固定数字。
模拟程序采用队列来存放所有参与游戏的人名，游戏开始，只需要让队首的人出队，随即在到队尾入队即可。
def hotPotato(namelist, num):
simqueue = Queue() # 初始化Queue
[simqueue.enqueue(name) for name in namelist]
# 将玩家名字入队
while simqueue.size() > 1:
# 玩家不唯一时，按照指定数字进行遍历玩家，到达指定数字时，出队。
[simqueue.enqueue(simqueue.dequeue()) for i in range(1,num)]
simqueue.dequeue()
return simqueue.dequeue()2.2 打印任务
多人共享打印机，采取 “先到先服务”的队列策略。
首要问题：
打印系统的容量有多大。
在能够接受的等待时间内，系统能容纳多少用户以多高频率提交打印任务。
具体实例配置如下：
在一个实验室中，任意一小时内，大约有十名学生在场，在一小时中，每人会发起 2 次左右的打印，每次打印 1~20 页。
打印机的性能：以草稿模式，每分钟十页。
以正常模式，每分钟五页。
对问题进行抽象，确定相关对象和过程：
对象：打印任务，打印队列，打印机
打印任务属性：提交时间，打印页数
打印机属性：打印速度，打印进行时间
过程：生成和提交打印任务
确定生成概率：每小时十位同学提交20份作业，概率 1/180 /s
确定打印页数：实例为 1~20 ，即概率在 1~20 之间均等
实施打印：新作业开始打印进行倒计时，到达 0 打印下一份作业
模拟流程：
创造打印队列对象
时间按秒为单位流逝
按照概率生成打印作业，加入打印队列
如果打印机空闲，且对列不为空，则取出队首任务打印，记录等待时间
若果打印机繁忙，则按照打印速度进行 1 秒打印
如果当前打印结束，打印机进入空闲
时间用尽，统计平均等待时间
作业等待时间
生成作业时间，记录生成时间戳
开始打印时，当前时间减去生成时间
作业打印时间
生成作业时，纪录作业的页数
开始打印时，页数除以打印速度
import random
class Printer: # 打印机
def __init__(self, ppm):
self.pagerate = ppm # 打印速度
self.currentTask = None # 打印任务
self.timeRemaining = 0 # 任务倒计时
def tick(self): # 打印1秒
if self.currentTask is not None:
self.timeRemaining = self.timeRemaining - 1
if self.timeRemaining <= 0:
self.currentTask = None
def busy(self): # 打印忙
if self.currentTask is not 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
# 等待时间 currenttime - self.timestamp
def newPrintTask():
num = random.randrange(1, 181) # 1/180 概率生成作业
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(10):
simulation(3600, 5)