Python的数据结构与算法的队列详解(3)

class Queue:
    def __init__(self):
        self.items = []            # 构建空队列
    def isEmpty(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)     # 队列(列表)长度

import random
# 模拟打印机
class Printer:
    # 打印机初始化
    def __init__(self, ppm):
        self.pagerate = ppm      # 打印速度 页/分钟
        self.currentTask = None  # 现有任务
        self.timeRemain = 0      # 该任务所需时间
    # 打印任务倒计时 0代表打印完成
    def tick(self):
        # 如果打印机正在执行任务
        if self.currentTask != None:
            # 该任务执行时间 = 执行时间 - 1（执行时间倒计时）
            self.timeRemaining = self.timeRemaining - 1   
            if self.timeRemaining <= 0:     # 该任务执行时间 <= 0
                self.currentTask = None     # 该任务执行完毕
    # 判断打印机是否空闲
    def busy(self):
        if self.currentTask != None:
            return True
        else:
            return False
    # 打印机接受新任务
    def startNext(self, newtask):
        self.currentTask = newtask
        # 新打印任务需要时间 = 新任务页数 * (60 / 每分钟打印多少页的速度)
        # (60 / 每分钟打印多少页的速度) = 每打印一页所需要的秒数
        self.timeRemaining = newtask.getPages() * (60 / self.pagerate)

# 模拟单个任务的属性
class Task:
    # 任务初始化
    def __init__(self, time):
        self.timestamp = time                # 创建任务的时间点
        self.pages = random.randrange(1, 21) # 任务页数 在 1~20 间随机生成
    def getStamp(self):
        return self.timestamp  # 获取任务创建的时间点
    def getPages(self):
        return self.pages      # 获取任务的页数
    def waitTime(self, currenttime):
        # 任务的等待时间 = 当前时间 - 任务创建的时间点
        return currenttime - self.timestamp   

# 模拟学生创建的新打印请求
def newPrintTask():
    # 打印请求是一个随机事件
    # 通过1~180之间的一个随机数来模拟每秒内产生打印请求的概率
    # 如果随机数正好是180，那么就认为有一个打印请求被创建。
    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("平均等待 %6.2f 秒，还有 %3D 个任务等待处理"
          % (averageWait, printQueue.size()))

def simulation(numSeconds, pagesPerMinute):
    # 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("平均等待 %6.2f 秒，还有 %3d 个任务等待处理" % (averageWait, printQueue.size()))