欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

Queue队列

程序员文章站 2024-03-18 08:15:34
...
  • 介绍队列的Python实现方式

  • 使用队列模拟打印机任务

  • 先进后出(FIFO)

  • 其中新添加的元素进入队列的【后端】,删除元素从【前端】开始

  • 主要的方法:

    • Queue() 创建一个新的队列
    • enqueue(item) 将item添加进入队列
    • dequeue() 将前端第一个元素移除队列并返回。
    • isEmpty() 测试队列是否为空
    • size()返回队列的长度,即队列中元素的个数。
class Queue:
    def __init__(self):
        self.items = []
    def enqueue(self, item):
        self.items.insert(0, item)
    def dequeue(self):
        return self.items.pop()
    def isEmpty(self):
        return self.items == []
    def size(self):
        return len(self.items)
q = Queue()
q.enqueue(4)
q.enqueue('dog')
q.enqueue(True)
print(q.size())
3
q.dequeue()
4
print(q.size())
2
q.isEmpty()
False

2、使用队列模拟“烫手的山芋”游戏

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))
Susan

3、使用队列模拟打印机任务

  • 问题的具体描述参见【这里
  • 需要创建三个对象:Printer、Task、PrinterQueue
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
    
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 newPrintTask():
    num = random.randrange(1,181)
    if num == 180:
        return True
    else:
        return False
    
for i in range(10):
    simulation(3600, 5)
平均等待时间为 232.09 秒,  还剩下  0 个打印任务
平均等待时间为  93.11 秒,  还剩下  0 个打印任务
平均等待时间为 195.80 秒,  还剩下  3 个打印任务
平均等待时间为  22.08 秒,  还剩下  0 个打印任务
平均等待时间为 177.91 秒,  还剩下  0 个打印任务
平均等待时间为  56.52 秒,  还剩下  0 个打印任务
平均等待时间为 504.95 秒,  还剩下  0 个打印任务
平均等待时间为 306.19 秒,  还剩下  1 个打印任务
平均等待时间为 412.62 秒,  还剩下  5 个打印任务
平均等待时间为  90.12 秒,  还剩下  4 个打印任务
for i in range(10):
    simulation(3600, 10)
平均等待时间为  66.30 秒,  还剩下  0 个打印任务
平均等待时间为  21.45 秒,  还剩下  0 个打印任务
平均等待时间为  38.29 秒,  还剩下  0 个打印任务
平均等待时间为   1.86 秒,  还剩下  0 个打印任务
平均等待时间为  26.72 秒,  还剩下  0 个打印任务
平均等待时间为  12.33 秒,  还剩下  0 个打印任务
平均等待时间为  32.88 秒,  还剩下  1 个打印任务
平均等待时间为  10.81 秒,  还剩下  0 个打印任务
平均等待时间为  31.17 秒,  还剩下  0 个打印任务
平均等待时间为  22.32 秒,  还剩下  0 个打印任务