數(shù)據(jù)結(jié)構(gòu)和算法是計算機技術(shù)的基本功之一，北京大學(xué)的課程深入淺出，使用Python作為載體簡化了編程難度。最近瀏覽了21-27，主要內(nèi)容是隊列（Queue）和雙端隊列（Deque）作為線性結(jié)構(gòu)的兩種，有怎樣的性質(zhì)，適合怎樣的問題。展示了如何使用Python編程實現(xiàn)這兩種結(jié)構(gòu)，以及怎樣在示例的問題中應(yīng)用它們。
代碼部分存在多種實現(xiàn)方式，思路重點在注釋中給出。

隊列實現(xiàn)與應(yīng)用

隊列Queue
新添加在尾端，移除在首端。先進(jìn)先出。
Queue只有一個入口一個出口，不允許數(shù)據(jù)項直接插入隊中，也不允許從中間移除數(shù)據(jù)項
打印任務(wù)隊列
操作系統(tǒng)進(jìn)程調(diào)度，先到先服務(wù)-資源充分利用，雙目標(biāo)決策
鍵盤敲擊并不馬上顯示，隊列性質(zhì)的緩存區(qū)保證了顯示順序不變

"""
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應(yīng)用 1 熱土豆
#隊列存放所有參加游戲的人名，隊首人出列再到隊尾入列為一次傳遞，傳num次后
#移除隊首不放回，求最后剩的一個人
def hotPotato(namelist, num):#每輪傳遞num次,第num傳遞的剔除
    simqueue=Queue()
    for name in namelist:
        simqueue.enqueue(name)
    
    while simqueue.size() > 1:#考慮不知道循環(huán)次數(shù)-常用while
        for i in range(num-1):
            a1=simqueue.dequeue()
            simqueue.enqueue(a1)
        simqueue.dequeue()
    return simqueue.dequeue()
#不需要計算就能解決這個問題，使用隊列結(jié)構(gòu)
print(hotPotato(["A","B","簡書","aha"],2))

2 模擬打印任務(wù)平均等待時間
系統(tǒng)容量有多大？在能夠接受的等待時間內(nèi)，能接受多少任務(wù)？
典型的決策支持問題：快打10Pages/min，慢打5ages/min，怎么平衡速度和質(zhì)量？
問題抽象-對問題建模：任務(wù)屬性——提交時間、打印頁數(shù)；隊列屬性、打印機屬性——是否在工作？
過程——生成和提交打印任務(wù)。概率設(shè)為180秒一份作業(yè)，1到20頁的概率均勻
模擬流程：1、創(chuàng)建隊列對象 2、時間流逝：按概率生成文件，加入隊列。若打印機空閑，則取出隊列首文件
記錄此文件等待時間，如果打印機忙，則按照打印速度進(jìn)行1秒打印 3、統(tǒng)計平均等待時間
等待時間——作業(yè)生成時記錄時間戳

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)
        #每一秒隨機生成新任務(wù)，進(jìn)入隊列，計算工作用時。打印機處理上一個任務(wù)，完畢后取新任務(wù)并
        #得到新任務(wù)等待時間，依次循環(huán)，直到測試時間整個結(jié)束。輸出平均等待時間和未完成任務(wù)數(shù)。從而調(diào)整打印機速度優(yōu)化此二目標(biāo)。
        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
#使用計算機模擬現(xiàn)實任務(wù)

雙端隊列實現(xiàn)與應(yīng)用

雙端隊列Deque
Deque是一種有次序的數(shù)據(jù)集，數(shù)據(jù)可以從兩端進(jìn)入移除，集成了棧和隊列的能力，但需要代碼維護(hù)Lifo或FiFo特性

"""
isEmpty()
addRear()
addFront()
size()
removeRear()
removeFront()
"""

采用list實現(xiàn)，0作為尾端，-1作為首端，因此復(fù)雜度上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應(yīng)用
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"))