Python数据结构—队列

​ Python实现队列，以及两个应用：1.约瑟夫斯问题 2.打印机任务问题 队列在实际的开发编程和系统编程中用的非常多，以后还需要继续学习。

# python实现简单队列
import random

class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []
    #入队用insert,复杂度为O(n)
    def enqueue(self,item):
        self.items.insert(0,item)
    #出队列用pop,复杂度为O(1)
    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)

# 队列应用一: 约瑟夫斯问题
def hotPatato(namelist,num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

    while simqueue.size() > 1:
        for i in range(num):
            simqueue.enqueue(simqueue.dequeue())
    #入列和出列num次以后，队列头的名字出局
            simqueue.dequeue()

    return simqueue.dequeue()

# 队列应用二:打印任务
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.getpage() * 60 /self.pagerate

class Task:
# 任务类,每个新的打印任务的初始化设定,比如任务建立时的时间戳等
    def __init__(self,time):
        self.timestamp = time
        self.pages = random.random(1,21)

    def getStamp(self):
        return self.timestamp

    def getPages(self):
        return self.pages
    # 等待时间为开始处理时的时间减去任务建立时的时间
    def waitTime(self,currenttime):
        return currenttime - self.timestamp

def simulation(numSeconds,pagesPerMin):

    labprinter = Printer(pagesPerMin)
    printQueue = Queue()
    waitingtimes = [] #用一个列表来保存每个任务的等待时间，最后汇总

    for currentSecond in range(numSeconds):

        if newPrintTask():
            task = Task()
            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 seconds %3d tasks remaining."%(averageWait,printQueue.size()))

def newPrintTask():
    num = random.randrange(1,181)
    if num == 180:
        return True
    else:
        return False