队列

我们为了实现队列抽象数据类型创建一个新类。和前面一样，我们将使用列表集合来作为构建队列的内部表示。

我们需要确定列表的哪一端作为队首，哪一端作为队尾。
如下所示的实现假定队尾在列表中的位置为 0。
这允许我们使用列表上的插入函数向队尾添加新元素。弹出操作可用于删除队首的元素（列表的最后一个元素）。回想一下，这也意味着入队为 O(n)，出队为 O(1)。

1
2
3
4
5
6
7
8
9
10
11
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)

初始化队列以及基础应用

1
2
q = Queue()
q.isEmpty()
1
True
1
2
q.enqueue(1)
q.dequeue()
1
1
1
2
for i in range(10):
    q.enqueue(i)
1
q.isEmpty()
1
False
1
q.size()
1
10
1
2
while not q.isEmpty():
    print(q.dequeue())
1
2
3
4
5
6
7
8
9
10
0
1
2
3
4
5
6
7
8
9

队列的应用

烫手山芋

队列的典型应用之一是模拟需要以 FIFO 方式管理数据的真实场景。首先，让我们看看孩子们的游戏烫手山芋，在这个游戏中，孩子们围成一个圈，并尽可能快的将一个山芋递给旁边的孩子。在某一个时间，动作结束，有山芋的孩子从圈中移除。游戏继续开始直到剩下最后一个孩子。

为了模拟这个圈，我们使用队列。假设拿着山芋的孩子在队列的前面。当拿到山芋的时候，这个孩子将先出列再入队列，把他放在队列的最后。经过 num 次的出队入队后，前面的孩子将被永久移除队列。并且另一个周期开始，继续此过程，直到只剩下一个名字（队列的大小为 1）

1
2
3
4
5
6
7
8
9
10
11
12
13
14
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))

请注意，在此示例中，计数常数的值大于列表中的名称数。这不是一个问题，因为队列像一个圈，计数会重新回到开始，直到达到计数值。另外，请注意，列表加载到队列中以使列表上的名字位于队列的前面。在这种情况下，Bill 是列表中的第一个项，因此他在队列的前面。

打印机

主要模拟步骤

  1. 创建打印任务的队列，每个任务都有个时间戳。队列启动的时候为空。
  2. 每秒（currentSecond）：
    • 是否创建新的打印任务？如果是，将 currentSecond 作为时间戳添加到队列。
    • 如果打印机不忙并且有任务在等待
      • 从打印机队列中删除一个任务并将其分配给打印机
      • 从 currentSecond 中减去时间戳，以计算该任务的等待时间。
      • 将该任务的等待时间附件到列表中稍后处理。
      • 根据打印任务的页数，确定需要多少时间。
    • 打印机需要一秒打印，所以得从该任务的所需的等待时间减去一秒。
    • 如果任务已经完成，换句话说，所需的时间已经达到零，打印机空闲。
  3. 模拟完成后，从生成的等待时间列表中计算平均等待时间。

为了设计此模拟，我们将为上述三个真实世界对象创建类：Printer, Task, PrintQueue

Printer 类需要跟踪它当前是否有任务。

如果有，则它处于忙碌状态（13-17 行），并且可以从任务的页数计算所需的时间。

构造函数允许初始化每分钟页面的配置，tick 方法将内部定时器递减直到打印机设置为空闲(11 行)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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 页的长度。我们选择使用随机模块中的 randrange 函数
每个任务还需要保存一个时间戳用于计算等待时间。此时间戳将表示任务被创建并放置到打印机队列中的时间。可以使用 waitTime 方法来检索在打印开始之前队列中花费的时间。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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

以下代码实现了上述算法。PrintQueue 对象是我们现有队列 ADT 的一个实例。
newPrintTask 决定是否创建一个新的打印任务。我们再次选择使用随机模块的 randrange 函数返回 1 到 180 之间的随机整数。
打印任务每 180 秒到达一次。通过从随机整数（32 行）的范围中任意选择，我们可以模拟这个随机事件。
模拟功能允许我们设置打印机的总时间和每分钟的页数。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
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

当我们运行模拟时，我们不应该担心每次的结果不同。这是由于随机数的概率性质决定的。 因为模拟的参数可以被调整，我们对调整后可能发生的趋势感兴趣。 这里有一些结果。
首先，我们将使用每分钟五页的页面速率运行模拟 60 分钟（3,600秒）。 此外，我们将进行 10 次独立试验。记住，因为模拟使用随机数，每次运行将返回不同的结果。

1
2
for i in range(10):
    simulation(3600,5)
1
2
3
4
5
6
7
8
9
10
Average Wait 133.21 secs   0 tasks remaining.
Average Wait  69.95 secs   1 tasks remaining.
Average Wait  18.21 secs   0 tasks remaining.
Average Wait 156.15 secs   1 tasks remaining.
Average Wait 124.05 secs   1 tasks remaining.
Average Wait 194.70 secs   4 tasks remaining.
Average Wait  48.24 secs   1 tasks remaining.
Average Wait  80.65 secs   0 tasks remaining.
Average Wait  62.31 secs   0 tasks remaining.
Average Wait  85.43 secs   2 tasks remaining.