1.队列的概念

一种有序列的数据集合，数据项的加入和移除发生在两端，遵循先进先出原则。

2.队列的python实现

# 队列的python实现
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)

3.队列的应用

（1）烫土豆问题

问题描述：一群人按顺序排列好，从第一个人开始拿到烫土豆，然后将土豆传递给下一个人。拿到土豆的人需要喊数，第一个拿到土豆的人喊一，后面的人依次加一，直到喊的数为设定的数则游戏结束，最后拿到土豆的人出列。

烫土豆的问题是经典的进出在不同两端的问题，下面是python实现。

def hotpotato(namelist,num):
    # 热土豆问题
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)
    for i in range(num):
        if i != num-1:
            simqueue.enqueue(simqueue.dequeue())
        elif i == num-1:
            return simqueue.dequeue()
print(hotpotato(['a','b','c','d','e','f'],11))

（2）打印任务问题

问题描述：一个实验室中，在任意的一个小数内大约有10名学生在场，这一个小数内每人会发起2次的打印，每次打印1~20页。实验室只有一台打印机，该打印机有两种模式：一个是草稿模式，每分钟可以打印10页，但其打印质量一般；第二种是正常模式，每分钟可以打印5页，其打印质量好。现在需要判断怎样设计打印机的打印模式可以使得学生的平均等待时间最少且打印质量也很好。

逐步拆分问题：

1）‘一小时内有10名学生来打印，每一位学生会发起两次打印’→总打印任务生成效率为每小时20次，将时间单位转化为秒→每秒生成的1/180个任务，将每秒1/180个任务转化为概率事件→每秒1/180的概率生成一个任务→调用range生成1~180个数，当出现确定数时生成打印任务---打印任务的生成

2）‘每次打印1~20页’，每次打印的页数不确定→调用random生成1~20随机数来表示单次打印任务需要打印的页数---打印任务的任务量

3）‘实验室只有一台打印机，该打印机有两种模式’，打印机有快慢模式，如何选择打印机的打印模式相当重要→设定打印机的两种状态‘空闲’和‘忙碌’→‘打印机在打印任务队列中取到打印任务后判断任务队列中是否有其他任务，若无则执行慢模式，相反则执行快模式---规定打印机切换模式的条件

4）‘使得学生的平均等待时间最少且打印质量也很好’，只有在快慢模式交替的情况下才能满足条件→生成两个时间戳：进入打印任务队列的时间和离开打印任务开始打印的时间→两个时间戳相减得到一个任务的等待时间→统计总的等待时间---记录并计算等待时间

python实现如下：

import random
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)

class Printer:
    # 打印机
    def __init__(self):
        self.page_fast_rate = 10  # 快模式打印速度
        self.page_slow_rate = 5  # 慢模式打印速度
        self.currentTask = None  # 运行状态
        self.time_remaining = 0  # 剩余打印时间
    def tick(self):
        # 每秒倒计时
        if self.currentTask != None:
            self.time_remaining -= 1
            if self.time_remaining <= 0:
                self.currentTask = None
    def operating_status(self):
        # 查看运行状态
        if self.currentTask != None :
            return  True
        else:
            return  False
    def add_task(self,task):
        # 添加打印任务到打印机中
        if self.currentTask == None:
            self.currentTask = task
        else:
            return False  #  打印机正在打印无法添加新任务
    def print_time(self,print_queue):
        # 计算当前任务的打印时间
        if print_queue.isEmpty() and self.currentTask != None:
            self.time_remaining = self.currentTask.getPages()*60/self.page_slow_rate
        elif (not print_queue.isEmpty()) and self.currentTask != None:
            self.time_remaining = self.currentTask.getPages()*60/self.page_fast_rate
        else:
            self.time_remaining = 0
        return self.time_remaining


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)
    if num == 180:
        return True
    else:
        return False

def simulation(num_seconds):
    # 模拟函数
    lab_printer = Printer()
    print_queue = Queue()
    waitting_times = []
    for currentSecond in range(num_seconds):
        if newPrintTask():
            task = Task(currentSecond)
            print_queue.enqueue(task)
        if (not lab_printer.operating_status()) and (not print_queue.isEmpty()):
            next_task = print_queue.dequeue()
            waitting_times.append(next_task.waitTime(currentSecond))
            lab_printer.add_task(next_task)
            lab_printer.print_time(print_queue)
        lab_printer.tick()
    averageWait = sum(waitting_times)/len(waitting_times)
    print('Average waiting %6.2f secs %3d tasks remaining.'%(averageWait,print_queue.size()))
for i in range(10):
    simulation(3600)