1、队列(Python实现)

assastor 2020-05-01

# -*- coding:utf-8 -*-#@Time : 2020/5/1 22:15#@Author: Aluosen#@File : Queue.py#队列的基本方法class Queue:    def __init__(self):        self.items = []    def isEmpty(self):        return self.items == []    def enqueue(self):        self.items.insert((0,item))    def dequeue(self):        return self.items.pop()    def size(self):        return len(self.items)#热土豆问题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()#打印机任务实现import random#打印机class Printer:    def __init__(self,ppm):        self.pagerate = ppm             #打印速度        self.currentTask = None         #打印任务        self.timeRemaining = 0          #任务倒计时    #打印1秒    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#作业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         #等待时间def newPrintTask()    num = random.randrange(1,181)                   #新生成打印作业概率为1/180    if num == 190:        return True    else:        return False#模拟def simulation(numSeconds,pagesPerMinute)    labprinter = Printer(pagesPerMinute)    printQueue = Queue()    waintingtimes = []    #时间流逝    for currentSecond in range(numSeconds):        if newPrintTask():            task = Task(currentSecond)            printQueue.enqueue(task)        if (not labprinter.busy()) and (not printQueue.isEmpty())            nexttask = printQueue.dequeue()            waintingtimes.append(nexttask.waitTime(currentSecond))            labprinter.startNext(nexttask)        labprinter.tick()    averageWait = sum(waintingtimes)/len(waintingtimes)    print(‘Average Wait %6.2f secs %3d task remaining.‘ %(averageWait,printQueue.size()))
#双端队列class Deque:    def __init__(self):        self.items = []    def isEmpty(self):        return self.items == []    def addFront(self,item):        self.items.append(item)    def addRear(self,item):        self.items.insert(0,item)    def removeFront(self):        return self.items.pop()    def removeRear(self):        return self.items.pop(0)    def size(self):        return len(self.items)#回文词判断def palchecker(sString):    chardeque = Deque()    for ch in aString:        chardeque.addRear(ch)    stillEqual = True    while chardeque.size() > 1 and stillEqual:        first = chardeque.removeFront()        last = chardeque.removeRear()        if first != last:            stillEqual = False    return stillEqual

相关推荐