Aizu Online Judge（AOJ）が提供している「アルゴリズムとデータ構造入門」（ALDS1）の3_B問題をC++で解いてみました。
ALDS1では、「アルゴリズムとデータ構造の基礎を体得します。」とあります。トピック#3「基本データ構造」では、スタック、キュー、リストを学びます。
問題（3_B: Queue）
問題はリンク先をご覧ください。
キューについて学びます。
キューについて
先入れ先出し（FIFO: First-In First-Out）ができるデータ構造です。値を格納する enqueue と値を取り出す dequeue の典型的な実装は以下となります。
#define N 2000
int que[N];
int head = 0;
int tail = 0;
void enqueue(int n)
{
que[tail] = n;
++tail;
tail %= N;
}
int dequeue(void)
{
int ret_val = que[head];
++head;
head %= N;
return ret_val;
}配列 que と、次に値を格納する場所を tail で値を取り出す場所を head で管理します。FIFO を使っていくとバッファが足りなくなるため、上限に達したら添え字を 0 に戻します。つまり循環的に配列を使っています。このように配列を使うとき、配列をリングバッファと呼びます。
上記の実装では、キューが空のときに dequeue したり、すでにキューに格納する余裕がないときに enqueue することがあります。多くの実装では、isEmpty や isFull のような関数を実装します。この実装例では、文字列を出力しています。実際には、例外を発生させたり、エラー値を返すなどします。
#include <queue>
#define N 200000
int que[N];
int head = 0;
int tail = 0;
bool isFull()
{
return head == (tail + 1) % N;
}
bool isEmpty()
{
return head == tail;
}
void enqueue(int n)
{
if (isFull()) {
cout << "Queue is full." << endl;
return;
}
que[tail] = n;
++tail;
tail %= N;
}
int dequeue(void)
{
if (isEmpty()) {
cout << "Queue is empty." << endl;
return -1;
}
int ret_val = que[head];
++head;
head %= N;
return ret_val;
}C++ プログラム例（ALDS1 3_B）
キューを使ってラウンドロビンスケジュールをシミュレーションします。
以下は、プログラムの解説です。
- キューで管理するデータを int から、string と int の pair に変更しました。
- 初期タスクをすべてキューに格納します（54行目）。
- キューが空になるまで以下を繰り返します（59ー67行目）。
- キューから値 p をとりだす。
- 計算時間 q と残り計算時間（p.second）を比較する。
- q 以下であれば、タスクの名前と開始からの時間（current_time）を出力する。
- そうでなければ、残り計算時間から q を引いて、再度キューに格納する。
以下が、C++プログラムとなります。
#include <iostream>
#include <string>
using namespace std;
#define N 200000
pair<string, int> que[N];
int head = 0;
int tail = 0;
bool isFull()
{
return head == (tail + 1) % N;
}
bool isEmpty()
{
return head == tail;
}
void enqueue(pair<string, int> n)
{
if (isFull()) {
cout << "Queue is full." << endl;
return;
}
que[tail] = n;
++tail;
tail %= N;
}
pair<string, int> dequeue(void)
{
if (isEmpty()) {
cout << "Queue is empty." << endl;
return make_pair("Empty", -1);
}
pair<string, int> ret_val = que[head];
++head;
head %= N;
return ret_val;
}
int main()
{
int n, q;
cin >> n >> q;
for (int i = 0; i < n; ++i) {
string name;
int time;
cin >> name >> time;
enqueue(make_pair(name, time));
}
int current_time = 0;
while (!isEmpty()) {
pair<string, int> p = dequeue();
if (p.second <= q) {
current_time += p.second;
cout << p.first << " " << current_time << endl;
} else {
p.second -= q;
enqueue(p);
current_time += q;
}
}
return 0;
}標準ライブラリ queue を使う。
「プログラミング応用」（ITP2）の2_B問題で、標準ライブラリとして実装されている queue を紹介しました。
標準ライブラリの実装と異なるのは、インターフェイス関数の名前が enqueue/dequeue ではなく，push/pop となります。また pop は値を破棄するだけです。値を取得するためには、front を呼び出します。その後で pop を呼び出しています。より詳しい解説は参照先の記事を読んでください。
標準ライブラリ queue を使ったプログラムは以下となります。
#include <iostream>
#include <string>
#include <queue>
using namespace std;
int main()
{
int n, q;
cin >> n >> q;
queue<pair<string, int>> que;
for (int i = 0; i < n; ++i) {
string name;
int time;
cin >> name >> time;
que.push(make_pair(name, time));
}
int current_time = 0;
while (!que.empty()) {
pair<string, int> p = que.front();
que.pop();
if (p.second <= q) {
current_time += p.second;
cout << p.first << " " << current_time << endl;
} else {
p.second -= q;
que.push(p);
current_time += q;
}
}
return 0;
}上記プログラムはどちらも、AOJ で「AC（Accepted＝正解）」と判定されました。
最後に
キューは、標準ライブラリを通して使っていました。この問題を通して、リングバッファの仕組みを理解することができました。
引き続き、ALDS1 の問題を紹介していきます。
