AIZU ONLINE JUDGE

AOJ ITP2 2_B(Queue)を解く

AOJ_ITP2_2_B

Aizu Online Judge(AOJ)が提供している「プログラミング応用」(ITP2)の2_B問題をC++で解いてみました。

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#2では、基本データ構造を学びます。

問題(2_B: Queue)

問題はリンク先をご覧ください。

AOJ ITP2 2_B問題: Queue

Queue について学びます。

Queue について

以下は、cpprefjp 様の記事を参考にさせていただきました。

概略

一般的にキューと呼ばれる「入れ物」は、FIFO(First-In First-Out)で動作します。C++ が提供している queue も FIFO で動作するコンテナを提供します。

ただし、queue は正確にはコンテナアダプタです。実際にアクセスするコンテナは標準のコンテナ(deque や list)、独自に実装したコンテナを選ぶことができます。デフォルトでは、deque が使われます。

主なメソッド

よく使われるメソッドを紹介します。stack の top が、queue では、front になります。

名前説明
push要素を追加する。
pop次の要素を削除する。
front次の要素を返す
size要素数を返す。
empty要素が空なら true を、そうでなければ false を返す。

注意として、pop は値を返しません。次の要素を front で得てから、pop で次の要素を削除します。

C++ プログラム例(ITP2 2_B)

問題で与えられるクエリに従い、以下の操作を行います。なお、Vector コンテナの要素を queue<int> として、複数の queue を用意します。

  • クエリ0 push により、Q[t] に、与えられた x を挿入する。
  • クエリ1 front により、Q[t] の次の要素を出力する。ただし、空の場合は何もしない。
  • クエリ2 pop により、Q[t] の次の要素を削除する。ただし、空の場合は何もしない。

以下は、C++のプログラムです。

#include <iostream>
#include <queue>

#include <vector>

using namespace std;

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

	vector<queue<int>> Q(n);

	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 0) {
			int t, x;
			cin >> t >> x;
			Q[t].push(x);
		} else if (command == 1) {
			int t;
			cin >> t;
			if (!Q[t].empty()) {
				cout << Q[t].front() << endl;
			}
		} else if (command == 2) {
			int t;
			cin >> t;
			if (!Q[t].empty()) {
				Q[t].pop();
			}
		}
	}

	return 0;
}

上記プログラムは、AOJ で「AC(Accepted=正解)」と判定されました。

最後に

Queue は、BFS(幅優先探索:Breadth-First search)でよく使われるコンテナです。いまのところグラフの探索は、DFS(深さ優先探索:Depth-First Search)を使うようにしています。DFS に慣れてきたら、BFS で queue も使いこなしたいと思います。

引き続き、ITP2 の問題を紹介していきます。

COMMENT

メールアドレスが公開されることはありません。 が付いている欄は必須項目です

CAPTCHA