線性結構隊列以及應用（上）_台中搬家公司

※廣告預算用在刀口上，台北網頁設計公司幫您達到更多曝光效益

擁有後台管理系統的網站，將擁有強大的資料管理與更新功能，幫助您隨時新增網站的內容並節省網站開發的成本。

隊列Queue:什麼是隊列？

對列是一種有次序的數據集合，其特徵是新數據項的添加總發生在一端（通常稱為“尾rear”端），而現存數據項的移除總發生在另一端（通常稱為“首front”端）

當數據項加入隊列，首先出現在隊尾，隨着隊首數據項的移除，它逐漸接近隊首。新加入的數據項必須在數據集末尾等待，而等待時間最長的數據項則是隊首。這種次序安排的原則稱為：先進先出。

隊列的例子出現在我們日常生活的方方面面：水管，排隊；隊列僅有一個入口和一個出口。不允許數據項直接插入隊中，也不允許從中間移除數據項。

抽象數據類型Queue

抽象數據類型Queue是一個有次序的數據集合，數據項僅添加到“尾”端，而且僅從”首“端移除，Queue具有先進先出的操作次序。

• 抽象數據類型Queue由如下操作定義：

  Queue():創建一個空隊列對象，返回值為Queue對象；

  enqueue(item):將數據項item添加到隊尾，無返回值；

  dequeue():從隊首移除數據項，返回值為隊首數據項，隊列被修改；

  isEmpty():測試是否空隊列，返回值為bool;

  size():返回隊列中數據項的個數。

  隊列操作	隊列內容	返回值
  q=Queue()	[]	Queue object
  q.isEmpty()	[]	True
  q.enqueue(4)	[4]
  q.enqueue(“dog”)	[“dog”,4]
  q.enqueue(True)	[True,”dog”,4]
  q.size()	[True,”dog”,4]	3
  q.isEmpty()	[True,”dog”,4]	False
  q.enqueue(“dog”)	[8.4,True,”dog”,4]
  q.dequeue()	[8.4,True,”dog”]	4
  q.dequeue()	[8.4,True]	“dog”
  q.size()	[8.4,True]	2

Python實現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):
        self.items.insert(0, item)
        
    def dequeue(self):
        return self.items.pop()
    
    def size(self):
        return len(self.items)

注意：首尾倒過來的實現，複雜度也倒過來。

隊列的應用：約瑟夫問題

傳說猶太人反叛羅馬人，落到困境，約瑟夫和39人決定殉難，坐成一圈，報數1-7，報到7的人由旁邊殺死，結果略瑟夫給自己安排了個位置，最後活了下來……

模擬程序採用隊列來存放所有參加遊戲的人名，按照報數的方向從隊首排到隊尾，模擬遊戲開始，只需要將隊首的人出隊，隨機再到對尾入隊，算是一次報數完成，反覆n次后，將隊首的人移除，不再入隊，如此反覆，知道隊列中剩下一人。

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

隊列的應用：打印任務

有如下場景：多人共享一台打印機，採取“先到先服務”的策略來執行打印任務，在這種設定下，一個首要問題就是：這種打印作業系統的容量有多大？在能夠接受的等待時間內，系統能夠容納多少用戶以多高頻率提交到少打印任務？

一個具體的實例配置如下：

一個實驗室，在任意的一個小時內，大約有10名學生在場，這一個小時中，每個人發起2次左右的打印，每次1-20頁。打印機的性能是：以草稿模式打印的話，每分鐘10頁，以正常模式打印的話，打印質量好，但是速度下降，每分鐘只能打印五頁。

問題：怎麼設定打印機的模式，讓大家都不會等太久的前提下，盡量提高打印質量？這是一個典型的決策支持問題，但無法通過規則直接計算，我們要用一段程序來模擬這種打印任務場景，然後對程序運行結果進行分析，以支持對打印機模式設定的決策。

如何對問題建模：

首先對問題進行抽象，確定相關的對象和過程。拋棄那些對問題實質沒有關係的學生性別，年齡，打印機型號，打印內容，智障大小等等眾多細節。

對象：打印任務，打印隊列，打印機。

打印任務的屬性：提交事件，打印頁數

打印隊列的屬性：具有“先進先出”性質的打印任務隊列

※推薦台中搬家公司優質服務,可到府估價

台中搬鋼琴,台中金庫搬運,中部廢棄物處理,南投縣搬家公司,好幫手搬家,西屯區搬家

打印機的屬性：打印速度，是否忙

過程：生成和提交打印任務

確定生成概率：實例為每小時會有10個學生提交的20個作業，這樣概率是每180秒會有1個作業生成並提交，概率為每秒1/180。

確定打印頁數：實例是1-20頁，那麼就是1-20頁之間概率相同。

過程：實施打印

當前的打印作業：正在打印的作業

打印結束倒計時：新作業開始打印時開始倒計時，返回0表示打印完畢，可以處理下一個作業。

模擬時間：

統一的時間框架：以最小單位（秒）均勻流逝的時間，設定結束時間

同步所有過程：在一個時間單位里，對生成打印任務和實施打印兩個過程各處理一次

打印任務問題：流程模擬

創建打印隊列對象

時間按照秒的單位流逝

按照概率生成打印作業，加入打印隊列

如果打印機空閑，且隊列不空，則取出隊首作業打印，記錄此作業等待時間

如果打印機忙，則按照打印速度進行1秒打印

如果當前作業打印完成，則打印機進入空閑

時間用盡，開始統計平均等待時間

作業的等待時間

生成作業時，記錄生成的時間戳

開始打印時，當前時間減去生成時間即可

作業的打印時間

生成作業時，記錄作業的頁數

開始打印時，頁數除以打印速度即可

import random

class Printer:
    def __init__(self, ppm):
        self.pagerate = ppm  # 打印速度
        self.currentTask = None  # 打印任務
        self.timeRemaining = 0  # 任務倒計時

    def tick(self):  # 打印1秒
        if self.currentTask != None:
            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()
    waittingtimes = []

    for currentSecond in range(numSeconds):
        if newPrintTask():
            task = Task(currentSecond)
            printQueue.enqueue(task)

        if not labprinter.busy() and not printQueue.isEmpty():
            nexttask = printQueue.dequeue()
            waittingtimes.append(nexttask.waitTime(currentSecond))
            labprinter.startNext(nexttask)

        labprinter.tick()

    averageWait = sum(waittingtimes) / len(waittingtimes)
    print("Average Wait %6.2f secs %3d tasks remaining" %(averageWait,printQueue.size()))

本站聲明:網站內容來源於博客園,如有侵權,請聯繫我們,我們將及時處理

※台中搬家公司教你幾個打包小技巧,輕鬆整理裝箱!

還在煩惱搬家費用要多少哪？台中大展搬家線上試算搬家費用，從此不再擔心「物品怎麼計費」、「多少車才能裝完」