Help us understand the problem. What is going on with this article?

Queue

Pythonで「キュー(Queue)」

はじめに

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

問題詳細

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

考え方

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

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()を使用します

まとめ

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

mcla
Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした