兄貴の伝説 - hatena edition -

ソフトウェア職人を目指してます

4.3 キュー(手動編)

queue も書いてみます。初めはランタイムエラーが出て「?」となりましたが、head とtail の初期化をサボってたからでした。AIZU のコンパイラはきっちりと不定値を入れてくるのですね。なお初期化については下記の記事が参考になります。

プログラミングの教科書を置いておくところ:C++ の初期化

#include <iostream>
#include <array>

using namespace std;

struct Process {
    string name;
    int time;
};

class ProcessQueue {
public:
  // ★初期化をサボらないこと!
  ProcessQueue() : head(), tail(), queue() {};
  virtual ~ProcessQueue() {};

  bool push(Process& process) {
    if (isFull()) {
      return false;
    }
    queue[head] = process;
    head++;
    if (head == MAX) {
      head = 0;
    }
    return true;
  }

  Process& pop() {
    if (isEmpty()) {
      // TODO: throw exception.
    }
    Process& value = queue[tail];
    tail++;
    if (tail == MAX) {
      tail = 0;
    }
    return value;
  }

  bool isEmpty() {
    return head == tail;
  }

  bool isFull() {
    return (head + tail) == MAX;
  }
private:
  static const int MAX = 100000;
  array<Process, MAX> queue;
  int head;
  int tail;
};

static void inputProcess(ProcessQueue& processQueue, int n) {
  Process in;
  for (int i = 0; i < n; i++) {
    cin >> in.name  >> in.time;
    processQueue.push(in);
   }
}

int main() {
  int n, q;
  cin >> n >> q;

  ProcessQueue processQueue;
  inputProcess(processQueue, n);

  int total = 0;
  while (!processQueue.isEmpty()) {
    Process now = processQueue.pop();
    if (now.time <= q) {
      total += now.time;
      cout << now.name << ' ' << total << endl;
    } else {
      now.time -= q;
      total += q;
      processQueue.push(now);
    }
  }
  
  return 0;
}