队列Queue 定义与实例

队列Queue 定义：

  • 队列是一种有次序的数据集合， 其特征是 新数据项的添加总发生在一端（通常称为“尾
    rear”端） 而现存数据项的移除总发生在另一端（通常称为 “首front”端）

  • 当数据项加入队列， 首先出现在队尾， 随 着队首数据项的移除， 它逐渐接近队首。

  • 新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首,这种次序安排的原则称为（FIFO:First-in first-out） 先进先出或“先到先服务first-come first-served”

  • 队列的例子出现在我们日常生活的方方面面：排队
  • 队列仅有一个入口和一个出口,不允许数据项直接插入队中，也不允许从中间移 除数据项

抽象数据类型Queue由如下操作定义：

  • Queue()：创建一个空队列对象，返回值为Queue对象；
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
class Queue:
    def __init__(self):
        self.items = []
#isEmpty()：测试是否空队列，返回值为布尔值
    def isEmpty(self):
        return self.items == []
#enqueue(item)：将数据项item添加到队尾，无返回值；
    def enqueue(self, item):
        self.items.insert(0,item)
#dequeue()：从队首移除数据项，返回值为队首数据项，队列被修改；
    def dequeue(self):
        return self.items.pop()
#size()：返回队列中数据项的个数。 
    def size(self):
        return len(self.items)

采 用 List 来 容 纳Queue的数据项，将List首端作为队列尾端，List的末端作为队列首端，enqueue()复杂度为O(n)，dequeue()复杂度为O(1)，首尾倒过来的实现， 复杂度也倒过来 。

算法实例

热土豆问题：算法

  • 模拟程序采用队列来存放所有参加游戏的人名，按照传递土豆方向从队首排到队尾游戏时，队首始终是持有土豆的人

  • 模拟游戏开始， 只需要将队首的人出队， 随即再到队尾入队， 算是土豆的一次传递传递了num次后，将队首的人移除，不再入队如此反复，直到队列中剩余1人 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
from pythonds.basic.queue import Queue

def hotPoatato(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()

def main():

    print(hotPoatato(["bill","david","susam","Jane","Kent","Brand"],7))
打印任务问题：模拟流程

  • 创建打印队列对象，

  • 时间按照秒的单位流逝，按照概率生成打印作业，加入打印队列，如果打印机空闲，且队列不空，则取出队首作业打印，记录此作业等待时间，如果打印机忙，则按照打印速度进行1秒打印，如果当前作业打印完成，则打印机进入空闲，

  • 时间用尽， 开始统计平均等待时间

  • 作业的等待时间,生成作业时，记录生成的时间戳，开始打印时，当前时间减去生成时间即可

  • 作业的打印时间，生成作业时，记录作业的页数，开始打印时，页数除以打印速度即可 
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
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
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(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("Auerage Wait %6.2f secs %3d tasks remaining"%(averageWait,printQueue.size()))


for i in range(10):

    simulation(600,5)

双端队列Queue 定义与实例

双端队列Queue 定义

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

  • 但双端队列并不具有内在的LIFO或者FIFO特性，如果用双端队列来模拟栈或队列，需要由使用者自行维护操作的一致性

deque定义的操作如下：

  • Deque()：创建一个空双端队列
  • addFront(item)：将item加入队首
  • addRear(item)：将item加入队尾
  • removeFront()：从队首移除数据项，返回值为移除的数据项
  • removeRear()：从队尾移除数据项，返回值为移除的数据项
  • isEmpty()：返回deque是否为空
  • size()：返回deque中包含数据项的个数

采用List实现，List下标0作为，deque的尾端，List下标-1作为，deque的首端
操作复杂度，addFront/removeFront O(1)，addRear/removeRear O(n) 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
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)

算法实例：

回文词判定：

“回文词”指正读和反读都一样的词，如radar、 madam、 toot，中文 “上海自来水来自海上”，“山东落花生花落东山 “

用双端队列很容易解决“回文词”问题，先将需要判定的词从队尾加入deque，再从两端同时移除字符判定是否相同，直到deque中剩下0个或1个字符 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
from pythonds.basic.deque import Deque

def plachecker(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(plachecker("sldkfjaldlka"))
print(plachecker("reaaer"))