ALDS1_3_B キューをC++で解いてみた[AIZU ONLINE JUDGE]

こんにちは！ mnbd（@mnbbbbbd）です。

AIZU ONLINE JUDGEの「ALDS1_3_B キュー」を解いてみましたので、その回答と解説をご紹介いたします。

プログラミング初心者なので、もっといい回答があるに違いありません。

あくまでも「動作はする」サンプルとしてご覧ください。

問題文
解答
感想
まとめ

問題文

名前 namei と必要な処理時間 timei を持つ n 個のプロセスが順番に一列に並んでいます。ラウンドロビンスケジューリングと呼ばれる処理方法では、CPU がプロセスを順番に処理します。各プロセスは最大 q ms（これをクオンタムと呼びます）だけ処理が実行されます。q ms だけ処理を行っても、まだそのプロセスが完了しなければ、そのプロセスは列の最後尾に移動し、CPU は次のプロセスに割り当てられます。
例えば、クオンタムを 100 msとし、次のようなプロセスキューを考えます。
A(150) - B(80) - C(200) - D(200)
まずプロセス A が 100 ms だけ処理され残りの必要時間 50 ms を保持しキューの末尾に移動します。
B(80) - C(200) - D(200) - A(50)
次にプロセス B が 80 ms だけ処理され、時刻 180 ms で終了し、キューから削除されます。
C(200) - D(200) - A(50)
次にプロセス C が 100 ms だけ処理され、残りの必要時間 100 ms を保持し列の末尾に移動します。
D(200) - A(50) - C(100)
このように、全てのプロセスが終了するまで処理を繰り返します。
ラウンドロビンスケジューリングをシミュレートするプログラムを作成してください。
入力
入力の形式は以下の通りです。
n q
name1 time1
name2 time2
...
namen timen
最初の行に、プロセス数を表す整数 n とクオンタムを表す整数 q が１つの空白区切りで与えられます。
続く n 行で、各プロセスの情報が順番に与えられます。文字列 namei と整数 timei は１つの空白で区切られています。
出力
プロセスが完了した順に、各プロセスの名前と終了時刻を空白で区切って１行に出力してください。
https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/3/ALDS1_3_B

解答

#include <bits/stdc++.h>
using namespace std;

int const p_max = 100001;

struct process {
    string name;
    int time;
};

class Queue {
  private:
    process prc[p_max];
    int head;
    int tail;

  public:
    Queue() {
        head = 0;
        tail = 0;
    }

    void queue_print() {
        cout << endl;

        cout << "head:" << head << " tail:" << tail << endl;
        for(int i = head; i < tail; i++) {
            cout << "prc[" << i << "] " << prc[i].name << " " << setw(3)
                 << prc[i].time << endl;
        }
        cout << endl;
    }

    bool is_empty() {
        if(head == tail) {
            return true;
        } else {
            return false;
        }
    }
    bool is_full() {
        if(head >= p_max) {
            return true;
        } else {
            return false;
        }
    }
    void enqueue(process p) {
        if(is_full()) {
            cout << "Error:this queue is full.";
        }
        prc[tail] = p;
        if(tail + 1 == p_max) {
            tail = 0;
        } else {
            tail++;
        }
    }

    process dequeue() {
        if(is_empty()) {
            cout << "Error:this queue is empty.";
        }
        process p = prc[head];
        if(head + 1 == p_max) {
            head = 0;
        } else {
            head++;
        }
        return p;
    }
};

int main() {
    int n;
    int quant;
    cin >> n >> quant;
    int count = 0;
    process p[n];
    //process p[n] = {
    //    {"p1", 150}, {"p2", 80}, {"p3", 200}, {"p4", 350}, {"p5", 20}};
    for (int i = 0; i < n; i++) {
        cin >> p[i].name >> p[i].time;
    }
    Queue q;
    for(int i = 0; i < n; i++) {
        q.enqueue(p[i]);
    }

    int i = 0;
    while(!q.is_empty()) {
        process tmp = q.dequeue();
        if(quant < tmp.time) {
            q.enqueue({tmp.name, tmp.time - quant});
            count += quant;
        } else {
            count += tmp.time;
            cout << tmp.name << " " << count << endl;
        }
    }

    return 0;
}