Algorithmためのデータ構造をPythonで実現しましょう。ーその２[Queueの実現]

今回はLinear Structure(今後LSと書きます)のQueueについてまとめていきます。

Queueはなんでしょうか

最初はQueueのイメージを掴んでいきます。

QueueはStackと違って、配列の一番左(rearの部分)を入り口とします。出口(データを取り出したい場合)はfrontのところ。一方、Stackはfrontのところを入り口、そして同時に出口としています。

では、今回もPythonのlistを使い、[1,2,3,4,5]、1は入り口5は出口のデータ構造をclassで実現しましょう！

PythonによるQueueの実現

class Queue(object):  
    def __init__(self):  
        self.item = []  
  
    def isEmpty(self):  
        return self.item == []  
  
    def enqueue(self, item):  
        self.item.insert(0, item)  
  
    def dequeue(self):  
        return self.item.pop()  
  
    def size(self):  
        return len(self.item)  

メソッドについて、enqueueはlist[0]に追加、dequeueはlist[-1]の値を取り出す。前回と同じく、応用問題のために、それぞれisEmpty, sizeメソッドを追加しました。
では、今回の応用問題はかなり難しいので、コードのみ載せます()

queueの応用問題-Printer

皆さんは大学時代の時図書館や資料室でプリントした経験があると思います。試験直近日になりますと、プリンターの需要は増え、私の場合、5分や10分ほど自分の資料を待ち続けた記憶がありました。

じゃ、プリンターの基本的な働き型はなんでしょう？

その通りです！プリンターは一個一個のジョブ(job)あるいはミッションをqueueに入れて、先方にあるジョブを完成しないと次のジョブは取り出さないのです。

では、問題です、queueにあるジョブの平均時間帯を計算しなさい。→シミュレーションみたいなプログラムと考えてもいいです。

シミュレーションコード：
Printer class:

class Printer(object):  
    def __init__(self, ppm):  
        self.ppm = ppm  
        self.currentTask = None  
    self.timeRemain = 0  
  
    def tick(self):  
        if self.currentTask:  
            self.timeRemain = self.timeRemain - 1  
        if self.timeRemain <= 0:  
            self.currentTask = None  
    print('over')  
  
  
    def busy(self):  
        return True if self.currentTask else False  
  
    def startNext(self, nextTask):  
        self.currentTask = nextTask  
        self.timeRemain = nextTask.getPages() * 60 / self.ppm  

Task class　→　ジョブのクラス

import random  
class Task(object):  
    def __init__(self, time):  
        self.time = time  
        self.pages = random.randrange(1,20)  
  
    def getTime(self):  
        return self.time  
  
    def getPages(self):  
        return self.pages  
  
    def waitTime(self, currentTime):  
        return currentTime - self.time  
  
    def newPrintTask():  
        num = random.randrange(1, 181)  
        return True if num == 150 else False 

Simulation:

 def simulation(numSecond, ppm):  
        print_obj = Printer(ppm)  
        queue_obj = Queue()  
        waitingTime_list = []  
        for i in range(numSecond):  
  
            if newPrintTask():  
                task_obj = Task(i)  
                queue_obj.enqueue(task_obj)  
    
            if not print_obj.currentTask and not queue_obj.isEmpty():  
                nextTask = queue_obj.dequeue()  
                waitingTime_list.append(nextTask.waitTime(i))  
                print_obj.startNext(nextTask)  
            print_obj.tick()  
        return waitingTime_list  
  
print(simulation(3000, 5))

時間があれば、説明も追加したいと考えていますが、今回はここまでです。

次回はUnorderedListについてシェアします。