基本数据结构 — — 队列

先进先出（左进右出）

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)
    
    # 打印队列
    def __repr__(self):
        return str(self.items)

【实例】约瑟夫环

q = Queue()


def yuesefu(list_, num):
    # 遍历列表，把列表中的元素都添加到队列中
    for name in list_:
        q.enqueue(name)

    # 当队列中的元素大于1时
    while q.size() > 1:
        print(q)
        for i in range(num - 1):
            q.enqueue(q.dequeue())
            print(q)

        print(f'本次淘汰的是：{q.dequeue()}')

    return f'最后剩下的人是：{q.dequeue()}'


list_ = ['a', 'b', 'c', 'd', 'e', 'f']
num = 7

result = yuesefu(list_, num)
print(result)

【实例】打印任务
考虑计算机科学实验室里的这样一个场景：在任何给定的一小时内，实验室里都有约 10 个
学生。他们在这一小时内最多打印 2 次，并且打印的页数从 1 到 20 不等。实验室的打印机比较
老旧，每分钟只能以低质量打印 10 页。可以将打印质量调高，但是这样做会导致打印机每分钟
只能打印 5页。降低打印速度可能导致学生等待过长时间。那么，应该如何设置打印速度呢？

import random


# 模拟任务
class Task:
    def __init__(self, time):
        # 当前任务被创建的时间
        self.create_time = time
        # 打印的页数
        self.pages_to_print = random.randrange(1, 21)

    # currentTime：当前任务开始被服务的时间
    # waitTime()返回的是当前任务在队列里等待了多久
    def waitTime(self, currentTime):
        return currentTime - self.create_time

# 模拟打印机
class Printer:
    # 打印机每分钟能打印pagePerMinute页
    def __init__(self, pagePerMinute):
        self.pagePerMinute = pagePerMinute
        self.task = None
        self.timeRemaining = 0    # 当前服务的任务还需多少时间才能完成

    def getTask(self, newTask):
        self.task = newTask
        self.timeRemaining = (newTask.pages_to_print / self.pagePerMinute) * 60

    def tick(self):
        if self.task != None:
            self.timeRemaining -= 1

        if self.timeRemaining <= 0:
            self.task = None

    def isBusy(self):
        if self.task == None:
            return False
        else:
            return True


# numSeconds：模拟的时间
# pagesPerMin：模拟每秒打印多少页
def simulation(numSeconds, pagesPerMin):
    printer = Printer(pagesPerMin)
    queue = Queue()
    waitTimeList = []

    # 遍历一遍当作过了一秒
    for currendSecond in range(numSeconds):
        # 检查是否有新的打印任务产生
        num = random.randrange(1, 181)
        if num == 180:
            newTask = Task(currendSecond)
            queue.enqueue(newTask)

        # 判断打印机是否空闲
        if not printer.isBusy() and not queue.isEmpty():
            # 从队列里取出一个新任务给打印机
            nextTask = queue.dequeue()
            printer.getTask(nextTask)
            # 将该任务的等待时间加入到列表里
            waitTime = currendSecond - nextTask.create_time
            waitTimeList.append(waitTime)

        printer.tick()

    avgWaitTime = sum(waitTimeList) / len(waitTimeList)
    print(f'平均等待时间为：{avgWaitTime}秒，任务队列中剩余{queue.size()}个任务未完成。')


for i in range(10):
    simulation(3600, 5)

最后编辑于：2019.12.17 20:26:28