数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用Python作为载体简化了编程难度。最近浏览了21-27，主要内容是队列（Queue）和双端队列（Deque）作为线性结构的两种，有怎样的性质，适合怎样的问题。展示了如何使用Python编程实现这两种结构，以及怎样在示例的问题中应用它们。
代码部分存在多种实现方式，思路重点在注释中给出。
队列实现与应用
队列Queue
新添加在尾端，移除在首端。先进先出。
Queue只有一个入口一个出口，不允许数据项直接插入队中，也不允许从中间移除数据项
打印任务队列
操作系统进程调度，先到先服务-资源充分利用，双目标决策
键盘敲击并不马上显示，队列性质的缓存区保证了显示顺序不变
"""
Queue()
enqueue(item)
isEmpty()
size()
dequeue()#先输出最先存入的元素
"""
class Queue():
def __init__(self):
self.items=[]
def isEmpty(self):
return self.items==[]
def enqueue(self, item):#使用List尾端为Queue首端，则O(n);Queue尾端O(1)
self.items.insert(0,item)
def dequeue(self):
return self.items.pop()
def size(self):
return len(self.items)
q1=Queue()
q1.enqueue(4)
q1.enqueue("a")
print(q1.dequeue())
#Queue应用 1 热土豆
#队列存放所有参加游戏的人名，队首人出列再到队尾入列为一次传递，传num次后
#移除队首不放回，求最后剩的一个人
def hotPotato(namelist, num):#每轮传递num次,第num传递的剔除
simqueue=Queue()
for name in namelist:
simqueue.enqueue(name)
while simqueue.size() > 1:#考虑不知道循环次数-常用while
for i in range(num-1):
a1=simqueue.dequeue()
simqueue.enqueue(a1)
simqueue.dequeue()
return simqueue.dequeue()
#不需要计算就能解决这个问题，使用队列结构
print(hotPotato(["A","B","简书","aha"],2))
2 模拟打印任务平均等待时间
系统容量有多大？在能够接受的等待时间内，能接受多少任务？
典型的决策支持问题：快打10Pages/min，慢打5ages/min，怎么平衡速度和质量？
问题抽象-对问题建模：任务属性——提交时间、打印页数；队列属性、打印机属性——是否在工作？
过程——生成和提交打印任务。概率设为180秒一份作业，1到20页的概率均匀
模拟流程：1、创建队列对象 2、时间流逝：按概率生成文件，加入队列。若打印机空闲，则取出队列首文件
记录此文件等待时间，如果打印机忙，则按照打印速度进行1秒打印 3、统计平均等待时间
等待时间——作业生成时记录时间戳
import random
class Printer:
def __init__(self,ppm):
self.pagerate=ppm#Velocity of printer
self.currentTask=None
self.timeRemaining=0
def tick(self):#1 second printing
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): #Add new task
self.currentTask= newtask
self.timeRemaining=newtask.getPages()*60/self.pagerate
class Task:
def __init__(self,time):
self.timestamp= time#generate timestamp information
self.pages = random.randrange(1,21)# get random integer number
def getStamp(self):
return self.timestamp
def getPages(self):
return self.pages
def waitTime(self, currenttime):
return currenttime-self.timestamp#return waiting time of this task
def newPrintTask():
num=random.randrange(1,181)
if num == 180:#any integer of 1-180
return True
else:
return False
def simulation(numSeconds, pagesPerMinute):
labprinter=Printer(pagesPerMinute)#Create a printer
printQueue=Queue()
waitingtimes=[]
for currentSecond in range(numSeconds):
if newPrintTask():#generate tasks by 1/180 probability
task = Task(currentSecond)#give it timestamp
printQueue.enqueue(task)
#每一秒随机生成新任务，进入队列，计算工作用时。打印机处理上一个任务，完毕后取新任务并
#得到新任务等待时间，依次循环，直到测试时间整个结束。输出平均等待时间和未完成任务数。从而调整打印机速度优化此二目标。
if (not labprinter.busy()) and (not printQueue.isEmpty()):
nexttask=printQueue.dequeue()
waitingtimes.append(nexttask.waitTime(currentSecond))
labprinter.startNext(nexttask)
labprinter.tick()
waitTime=sum(waitingtimes)/len(waitingtimes)
print("Average waiting time: %6.2f seconds, %3d tasks remaining." %(waitTime,printQueue.size()))
for i in range(10):
simulation(3600,6)#test with 6 pages/min for 1 hour
#使用计算机模拟现实任务
双端队列实现与应用
双端队列Deque
Deque是一种有次序的数据集，数据可以从两端进入移除，集成了栈和队列的能力，但需要代码维护Lifo或FiFo特性
"""
isEmpty()
addRear()
addFront()
size()
removeRear()
removeFront()
"""
采用list实现，0作为尾端，-1作为首端，因此复杂度上addFront 和 removeFront 是O(1)
class Deque:
def __init__(self):
self.items=[]
def isEmpty(self):
return self.items==[]
def addRear(self, item):
self.items.insert(0,item)
def addFront(self, item):
self.items.append(item)
def removeRear(self):
return self.items.pop(0)
def removeFront(self):
return self.items.pop()
def size(self):
return len(self.items)
双端队列Deque应用
1 判断回文词 山东小小东山
此问题适合用双端队列解决，因为需要同时比较两端字符
def palchecker(string1):
deque=Deque()
for i in string1:
deque.addFront(i)
counts=deque.size()//2
passcounts=0
for j in range(counts):
if deque.removeRear()==deque.removeFront():
passcounts+=1
return passcounts==counts
print(palchecker("wo1w"),palchecker("yeey"))
网友评论