队列抽象数据类型

队列是元素的有序集合，添加操作发生在其尾部，移除操作则发生在头部。队列的操作顺序是 FIFO（first-in first-out），它支持以下操作：

• Queue() 创建一个空队列。它不需要参数，且会返回一个空队列。
• enqueue(item) 在队列的尾部添加一个元素。它需要一个元素作为参数，不返回任何值。
• dequeue() 从队列的头部移除一个元素。它不需要参数，且会返回一个元素，并修改队列的内容。
• isEmpty() 检查队列是否为空。它不需要参数，且会返回一个布尔值。
• size() 返回队列中元素的数目。它不需要参数，且会返回一个整数。

队列操作示例

队列操作	队列内容	返回值
q.isEmpty()	[]	True
q.enqueue(4)	[4]
q.enqueue('dog')	['dog', 4]
q.enqueue(True)	[True, 'dog', 4]
q.size()	[True, 'dog', 4]	3
q.isEmpty()	[True, 'dog', 4]	False
q.enqueue(8.4)	[8.4, True, 'dog', 4]
q.dequeue()	[8.4, True, 'dog']	4
q.dequeue()	[8.4, True]	'dog'
q.size()	[8.4, True]	2

用 Python 实现队

像之前一样，我们利用简洁强大的列表来实现队列。

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)

假设队列的尾部在列表的位置 0 处。如此一来，便可以使用 insert 函数向队列的尾部添加新元素。 pop 则可用于移除队列头部的元素（列表中的最后一个元素）。这意味着添加操作的时间复杂度是 O(n) ，移除操作则是 O(1)。

模拟：传土豆

考虑这样一个儿童游戏：传土豆。在这个游戏中，孩子们围成一圈，并依次尽可能快地传递一个土豆。在某个时刻，大家停止传递，此时手里有土豆的孩子就得退出游戏。重复上述过程，直到只剩下一个孩子。

我们使用队列来模拟一个环，如下图所示。假设握着土豆的孩子位于队列的头部。在模拟传土豆的过程中，程序将这个孩子的名字移出队列，然后立刻将其插入队列的尾部。随后，这个孩子会一直等待，直到再次到达队列的头部。在出列和入列 num 次之后，此时位于队列头部的孩子出局，新一轮游戏开始。如此反复，直到队列中只剩下一个名字（队列的大小为 1）。

from pythonds.basic 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.enqueue(simqueue.dequeue())

        simqueue.dequeue()

    return simqueue.dequeue()

模拟：打印任务

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

可以通过构建一个实验室模型来解决该问题。我们需要为学生、打印任务和打印机构建对象。当学生提交打印任务时，我们需要将它们加入等待列表中，该列表是打印机上的打印任务队列。当打印机执行完一个任务后，它会检查该队列，看看其中是否还有需要处理的任务。我们感兴趣的是学生平均需要等待多久才能拿到打印好的文章。这个时间等于打印任务在队列中的平均等待时间。

如果实验室里有 10 个学生，并且在一小时内每个人都打印两次，那么每小时平均就有 20 个
打印任务。每小时 20 个任务相当于每 180 秒 1 个任务。可以通过 1~180 的一个随机数来模拟每秒内产生打印任务的概率。如果随机数正好是 180，那么就认为有一个打印任务被创建。注意，可能会出现多个任务接连被创建的情况，也可能很长一段时间内都没有任务。

模拟步骤：

1. 创建一个打印任务队列。每一个任务到来时都会有一个时间戳。一开始，队列是空的。
2. 针对每一秒（currentSecond），执行以下操作。
   • 是否有新创建的打印任务？如果是，以 currentSecond 作为其时间戳并将该任务加入
     到队列中。
   • 如果打印机空闲，并且有正在等待执行的任务，执行以下操作：
     • 从队列中取出第一个任务并提交给打印机；
     • 用 currentSecond 减去该任务的时间戳，以此计算其等待时间；
     • 将该任务的等待时间存入一个列表，以备后用；
     • 根据该任务的页数，计算执行时间。
   • 打印机进行一秒的打印，同时从该任务的执行时间中减去一秒。
   • 如果打印任务执行完毕，或者说任务需要的时间减为 0，则说明打印机回到空闲状态。
3. 当模拟完成之后，根据等待时间列表中的值计算平均等待时间。

Python 实现

我们创建 3 个类： Printer、 Task 和 PrintQueue。它们分别模拟打印机、打印任务和队列。

Printer 类需要检查当前是否有待完成的任务。如果有，那么打印机就处于工作状态，并且其工作所需的时间可以通过要打印的页数来计算。其构造方法会初始化打印速度，即每分钟打印多少页。tick 方法会减量计时，并且在执行完任务之后将打印机设置成空闲状态。

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

Task 类代表单个打印任务。当任务被创建时，随机数生成器会随机提供页数，取值范围是 1~20。我们使用 random 模块中的 randrange 函数来生成随机数。

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

每一个任务都需要保存一个时间戳，用于计算等待时间。这个时间戳代表任务被创建并放入打印任务队列的时间。 waitTime 方法可以获得任务在队列中等待的时间。

主模拟程序实现了之前描述的算法。printQueue 对象是队列抽象数据类型的实例。布尔辅助函数 newPrintTask 判断是否有新创建的打印任务。我们再一次使用 random 模块中的 randrange 函数来生成随机数，不过这一次的取值范围是 1~180。平均每 180 秒有一个打印任务。通过从随机数中选取 180，可以模拟这个随机事件。该模拟程序允许设置总时间和打印机每分钟打印多少页。

from pythonds.basic import Queue

import random

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("Average Wait %6.2f secs %3d tasks remaining."\
        %(averageWait, printQueue.size()))



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

每次模拟的结果不一定相同。对此，我们不需要在意。这是由于随机数的本质导致的。我们感兴趣的是当参数改变时结果出现的趋势。

---

双端队列抽象数据类型

双端队列是元素的有序集合，其任何一端都允许添加或移除元素。双端队列支持以下操作：

• Deque() 创建一个空的双端队列。它不需要参数，且会返回一个空的双端队列。
• addFront(item) 将一个元素添加到双端队列的前端。它接受一个元素作为参数，没有返回值。
• addRear(item) 将一个元素添加到双端队列的后端。它接受一个元素作为参数，没有返回值。
• removeFront() 从双端队列的前端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
• removeRear() 从双端队列的后端移除一个元素。它不需要参数，且会返回一个元素，并修改双端队列的内容。
• isEmpty() 检查双端队列是否为空。它不需要参数，且会返回一个布尔值。
• size() 返回双端队列中元素的数目。它不需要参数，且会返回一个整数。

双端队列操作示例

双端队列操作	双端队列内容	返回值
d.isEmpty()	[]	True
d.addRear(4)	[4]
d.addRear('dog')	['dog', 4]
d.addFront('cat')	['dog', 4, 'cat']
d.addFront(True)	['dog', 4, 'cat', True]
d.size()	['dog', 4, 'cat', True]	4
d.isEmpty()	['dog', 4, 'cat', True]	False
d.addRear(8.4)	[8.4, 'dog', 4, 'cat', True]
d.removeRear()	['dog', 4, 'cat', True]	8.4
d.removeFront()	['dog', 4, 'cat']	True

注意，前端在列表的右端。记住前端和后端的位置可以防止混淆。

用 Python 实现双端队列

和前面一样，我们通过创建一个新类来实现双端队列抽象数据类型。

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

    def isEmpty(self):
        return self.items == []

    def addFront(self, item):
        self.items.append(item)

    def addRear(self, item):
        self.items.insert(0, item)

    def removeFront(self):
        return self.items.pop()

    def removeRear(self):
        return self.items.pop(0)

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

在双端队列的 Python 实现中，在前端进行的添加操作和移除操作的时间复杂度是 O(1) ，在后端的则是 O(n)。

回文检测器

回文问题：回文是指从前往后读和从后往前读都一样的字符串，例如 radar、 toot，以及 madam。我们将构建一个程序，它接受一个字符串并且检测其是否为回文。

我们使用一个双端队列来存储字符串中的字符。按从左往右的顺序将字符串中的字符添加到双端队列的后端。此时，该双端队列类似于一个普通的队列。然而，可以利用双端队列的双重性，其前端是字符串的第一个字符，后端是字符串的最后一个字符。

由于可以从前后两端移除元素，因此我们能够比较两个元素，并且只有在二者相等时才继续。如果一直匹配第一个和最后一个元素，最终会处理完所有的字符（如果字符数是偶数），或者剩下只有一个元素的双端队列（如果字符数是奇数）。任意一种结果都表明输入字符串是回文。

from pythonds.basic 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

---