Queue

Pythonで「キュー（Queue）」

はじめに

ここでは「プログラミングコンテスト攻略のためのアルゴリズムとデータ構造」の中で取り上げられている「AOJ (Aizu Online Judge」)の問題を自分で解いた際に学んだことや、こう考えれば分かりやすいと感じたことなどを自分への整理も兼ねてまとめています。
このテキストはC++で書かれているので、私のようにpythonで勉強をされている初学者の方の参考になれば幸いです。また私自身も初学者ゆえ、至らない点が多々あると思いますので、ご指摘・ご助言頂ければ喜びます。よろしくお願いします。

問題詳細

ALDS 1_3_B: Queue
キューを使ってラウンドロビンスケジューリングをシミュレートする問題です。
問題詳細は上記リンクをご参考ください

考え方

・ラウンドロビンスケジューリングと呼ばれる処理方法ではCPUがプロセスを順番に処理していくのですが、各プロセスの所要時間がクオンタム（１回の制限時間みたいなもの）を越える場合、そのプロセスは待ち行列の最後尾に移動させられ、次のプロセスの処理が始まります。これはキューの先入先出しが利用できます。

pythonコード

from collections import deque

n, q = map(int, input().split())
listA = []
t=1
while t <=n:  # 変な書き方をしていると思います、、、
    try:
        listA.append(input().split())
        t +=1
    except:
        break

result=[]
qu = deque()
for i in range(n):
    qu.append(listA[i]) # プロセスを順番にキューに入れる

time = 0    # 処理を開始してからの経過時間を入れる
while True:
    try:
        task = qu.popleft()     # 今処理するプロセスを取り出す
        if int(task[1]) <= q:   # クオンタム内で処理が完了するかを判断
            time += int(task[1]) # 処理時間を加える
            result.append([task[0], time]) 
        else:
            time += q # クオンタム目一杯処理を行ったのでクオンタム分を加える
            task[1] = int(task[1]) - q # 残りの処理時間
            qu.append(task) # 待ち行列の最後尾に追加
    except:
        break

for i in range(n):
    print(*result[i])

ポイント

・キューとしてdequeを扱う場合には、先入先出しなので、popleft()とappend()を使用します

まとめ

以上となります。間違いや改善点などございましたら、よろしくお願いいたします。