基本数据结构——线性结构（队列、双端队列）

1. 什么是队列？

队列是一种有次序的数据集合，其特征是新数据项的添加总发生在一端（通常称为“尾端”），而现存数据项的移除总发生在另一端（通常称为“首front”端）。 新加入的数据项必须在数据集末尾等待，而等待时间最长的数据项则是队首。这种次序安排的原则称为先进先出(FIFO:First-in-first-on) 队列仅有一个入口和一个出口。不允许数据项直接插入队中，也不允许从中间移除数据项。

2.抽象数据类型Queue

抽象数据类型Queue是一个有次序的数据集合。数据项仅添加到尾端，而且仅从首端移除。Queue具有FIFO的操作次序

2.1 抽象数据类型Queue定义的操作

2.2操作样例

2.3用python实现ADT Queue

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

#队列 class Queue: def __init__(self): self.items=[]#产生一个对列 def isEmpty(self): return self.items==[] #判断对列是否为空 def enqueue(self,item): return self.items.insert(0,item)#将数据项item添加到队尾 def dequeue(self): return self.items.pop()#从队首移除数据项 def size(self): return len(self.items)#返回对列的大小

2.4 Queue的应用：打印任务

一个具体的实例配置如下：

一个实验室，在任意的一小时内，大约有10名学生在场。这一小时中，没人会发起两次左右的打印，每次1~20页

打印机的性能：

以草稿模式打印的话，每分钟10页；以正常模式打印的话，打印质量好，但速度降为每分钟5页。

问题是：

怎么设定打印机的模式，让大家都不会等太久的前提下尽量提高打印质量？

2.4.1 如何对问题建模

对问题进行抽象，确定相关的对象和过程。抛弃那些对问题是指没有关系的学生性别、年龄、打印机型号、打印内容、纸张大小等等众多细节。

2.4.1.1 对象：打印任务、打印队列、打印页数

打印任务的属性：提交时间、打印页数 打印队列的属性：具有FIFO性质的打印任务队列 打印机属性：打印速度、是否忙

2.4.1.2 过程:

生成和提交打印任务 确定生成概率：实例为每小时会有10个学术提交20个作业，这样，概率是每180秒会有一个作业生成并提交，概率为每秒1/180 确定打印页数：实例是1-20页，那么就是1-20页之间的概率相同 实施打印 当前的打印作业：正在打印的作业打印结束倒计时：新作业开始打印时开始倒计时，回0表示打印完毕，可以处理下一个作业。

2.4.1.3 模拟时间

统一的时间框架：以最小单位（秒）均匀流逝的时间，设定结束时间同步所有过程：在一个时间单位里，对生成打印任务和实施打印两个过程各处理一次。

2.4.2 模拟流程

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

2.4.3 python实现

#队列 import random class Queue: def __init__(self): self.items=[]#产生一个对列 def isEmpty(self): return self.items==[] #判断对列是否为空 def enqueue(self,item): return self.items.insert(0,item)#将数据项item添加到队尾 def dequeue(self): return self.items.pop()#从队首移除数据项 def size(self): return len(self.items)#返回对列的大小 #打印机 class Printer: def __init__(self,ppm):#ppm打印速度 self.pagerate=ppm self.currentTask=None#当前打印任务 self.timeRemaining=0#任务倒计时 def tick(self):#打印1秒 if self.currentTask !=None: self.timeRemaining=self.timeRemaining-1 if self.timeRemaining<=0:#倒计时小于等于0 self.currentTask=None#当前没有打印任务 def busy(self):#判断打印机是否正忙 if self.currentTask !=None:#当currentTask不为None,表示打印机正忙，返回True 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 #1/180概率生成作业 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("Average Wait %6.2f secs = tasks remaining"%(averageWait,printQueue.size())) for i in range(10): simulation(3600,5)

按照5ppm、1小时的设定，模拟运行10次。结果如下： 上述结果中，总平均等待时间为133.603秒，最长的平均等待为586.28秒，最短的平均等待14.60秒。还有两次模拟中有作业没有开始打印。 按照10ppm、1小时的设定，模拟运行10次。结果如下： 上述结果中，总平均等待时间为23.535秒，最长的平均等待为56.58秒，最短的平均等待9.37秒。而且所有的作业都打印了。

3.双端队列（Deque）

双端队列Deque是一种有次序的数据集。跟队列相似，其两端可以称作“首”“尾”端，但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。某种意义上说，双端队列继承了栈和队列的能力。但双端队列并不具有内在的LIFO或者FIFO特性。如果用双端队列来模拟栈或者队列，需要由使用者自行维护操作的一致性。

3.1 抽象数据类型Deque定义的操作：

3.2 操作样例

3.3 python实现ADT Deque

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

class Deque: def __init__(self): self.items=[]#建立空的双端队列 def isEmpty(self): return self.items==[]#判断双端队列是否为空 def addFront(self,item):#将item加入队首 self.items.append(item) def addRear(self,item):#将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)#返回双端队列中包含数据项的个数

3.4 双端队列的应用——“回文词”判定

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

利用双端队列解决“回文词”判断问题

首先将需要判定的词从队尾加入deque，再从两端同时移除字符判定是否相同，直到deque中剩下0个或一个字符

python实现代码

class Deque: def __init__(self): self.items=[]#建立空的双端队列 def isEmpty(self): return self.items==[]#判断双端队列是否为空 def addFront(self,item):#将item加入队首 self.items.append(item) def addRear(self,item):#将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)#返回双端队列中包含数据项的个数 #回文词判定 def palchecker(aString): adeque=Deque()#创建一个空的双端队列 #将需要判定的词从队尾加入到deque for ch in aString: adeque.addRear(ch) isHuiWen=True #从两端同时移除字符判定是否相同 while adeque.size()>1 and isHuiWen: left=adeque.removeFront()#移除队首的数据项 right=adeque.removeRear()#移除队尾的数据项 if left!=right: isHuiWen=False return isHuiWen print(palchecker('radar')) print(palchecker('raddarb'))