数据结构与算法学习_Python_队列与双端队列

数据结构和算法是计算机技术的基本功之一，北京大学的课程深入浅出，使用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"))