今回は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についてシェアします。