数据结构与算法python版本之线性结构之队列Quene

什么是队列？

队列是一种有次序的数据集合，其特征是：新数据项的添加总发生在一端（通常称为“尾rear”端），而现存数据项的移除总发生在另一端（通常称为“首front”端）；当数据项加入队列，首先出现在队尾，随着队首数据项的移除，它逐渐接近队首。
新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首；
这种次序安排的原则称为**（FIFO：First-in-first-out）先进先出；**
队列的列子出现在我们日常生活的方方面面：排队
计算机科学中队列的例子：打印机、进程调度、键盘缓冲。
抽象数据类型Quene是一个有次序的数据集合

队列数据类型的操作定义：
Queue(）：创建一个空队列对象，返回值为Queue对象;
enqueue(item)：将数据项item添加到队尾，无返回值;
dequeue(）：从队首移除数据项，返回值为队首数据项，队列被修改;
isEmpty(）：测试是否空队列，返回值为布尔值；
size(）：返回队列中数据项的个数。

在这里插入图片描述

队列的应用：热土豆

热土豆的原理跟“击鼓传花”的原理相似，当鼓声停的时候，手里有土豆的小孩就要出列；
我们用队列来实现热土豆问题的算法，参加游戏的人名列表以及传土豆次数，算法返回最后剩下的人名；
主要就是
模拟程序采用队列来存放所有参加游戏的人名，按照传递土豆方向从队首排列到队尾，游戏时，队首始终是持有土豆的人；
模拟游戏开始，只需要将队首的人出列，随即再到队尾入队，算是土豆的一次传递，传递了num次后，将队首的人移除，不再入队，如此反复，直到队列中剩余1人，具体代码如下：

# 队列的应用：热土豆问题
from pythonds.basic.queue import Queue

def hotPotato(namelist, num):
    simqueue = Queue()
    for name in namelist:
        #添加数据到队列里面
        simqueue.enqueue(name)
    while simqueue.size() > 1:
        for i in range(num):
            #simqueue.dequeue()返回队尾
            simqueue.enqueue(simqueue.dequeue())
        simqueue.dequeue()
    return simqueue.dequeue()

print(hotPotato(["A", "B", "C", "D", "E", "F", "G"], 7))

运行后的结果如下：
在这里插入图片描述

打印任务

我们再看队列的另一个应用，打印任务
多人共享一台打印机，采取“先到先服务”的队列策略来执行打印任务；在这种设定下，一个首要的问题就是：
这种打印作业系统的容量有多大？
在能够接受的等待时间内，系统能容纳多少用户？
以多高频率提交多少打印任务？

一个具体的实例配置如下：一个实验室，在任意一小时内，大约有10名学生在场，这一小时中，每人会发起2次左右的打印，每次1-20页；
打印机的性能是：以草稿模式打印的话，每分钟10页，以正常模式打印的话，打印质量好，但速度下降为每分钟5页。

现在的问题是：怎么设定打印机的模式，让大家都不会等太久的前提下尽量打印高质量？
这是一个典型的决策支持问题，但无法通过规则直接计算
我们要用一段程序来模拟这种打印任务场景，然后对程序运行结果进行分析，以支持对打印模式设定的决策。

那么如何对问题进行建模呢？

首先对问题进行抽象，确定相关的对象和过程，摒弃那些对问题实质没有关系的学生性别、年龄、打印机型号、打印内容、纸张大小等等众多细节；
对象：打印任务、打印队列、打印机
打印任务的属性：提交时间、打印页数
打印队列的属性：具有FIFO性质的打印任务队列
打印机的属性：打印速度、是否忙
过程：生成和提交打印任务，确定生成概率：实例为每小时会有10个学生提交的20个作业，这样，概率是每180秒会有1个作业生成并提交，概率为每秒1/180，确定打印页数：实例是1~20页，那么就是1-20页之间概率相同。
过程：实施打印
当前的打印作业：正在打印的作业
打印结束倒计时：新作业开始打印时开始倒计时，回复标识表示打印完毕，可以处理下一个作业
模拟时间:
统一的时间框架：以最小单位（秒）均匀流逝的时间，设定结束时间
同步所有过程：在一个时间单位里，对生成打印任务和实施打印两个过程各处理一次

打印任务问题：如何模拟流程
创建打印队列对象
时间按照秒的单位流逝
按照概率生成打印作业，加入打印队列
如果打印机空闲，且队列不为空，则取出队首作业打印，记录此作业等待时间
如果打印机忙，则按照打印速度进行1秒打印
如果当前作业打印完成，则打印机进入空闲
时间用尽，开始统计平均等待时间
作业的等待时间
生成作业时，记录生成的时间戳
开始打印时，当前时间减去生成时间即可
作业的打印时间
生成作业时，记录作业的页数
开始打印时，页数除以打印速度即可

那么基本运行程序如下：

# 队列的应用：打印机
from pythonds.basic.queue import Queue
import random

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


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(numSecond, pagesPerMinute):
    #模拟任务
    labprinter = Printer(pagesPerMinute)
    printQuene = Queue()
    waitingtimes = []
    for currentSecond in range(numSecond):
        if newPrintTask():
            task = Task(currentSecond)
            printQuene.enqueue(task)
        if (not labprinter.busy()) and (not printQuene.isEmpty()):
            nexttask = printQuene.dequeue()
            waitingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startNext(nexttask)
        labprinter.tick()
    averageWait = sum(waitingtimes)/len(waitingtimes)
    print("Average Wait %6.2f secs %3d tasks remaining." %(averageWait, printQuene.size()))

双端队列Deque

双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作首尾端，但deque中数据项既可以从队首加，也可以从队尾加；数据项也可以从两端移除。从某种意义上来说，双端队列集成了栈和队列的能力。

但是双端队列并不具有内在的LIFO或者FIFO特性，如果用双端队列来模拟栈或者队列，需要由使用者自行维护操作的一致性。
双端队列的操作如下：
在这里插入图片描述
举例来说：

双端队列比较常见的应用就是回文词的判定。
回文词指的是正读和反读都是一样的此。
比如说radar madam toot等等
具体代码实现逻辑如下：


from pythonds.basic.deque import Deque

def palchecker(aString):
    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

print(palchecker("llldssa"))
print(palchecker("radar"))