AOJ ITP2 1_B（Deque）を解く

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

ITP2では、「プログラミングのための基礎ライブラリを獲得します」とあります。トピック#1では、動的配列とリストを学びます。

問題（1_B: Deque）

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

AOJ ITP2 1_B問題: Deque

Deque（Double-Ended QUEue）コンテナについて学びます。

Deque コンテナについて

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

概略

Deque は、Vector に近い機能を提供します。

• 配列と同じく、添え字によって要素にアクセスできる。
• 可変長で、自動的に領域の拡張が行われる。
• （Vector と異なり）先頭の要素の追加と削除が効率よくできる。

主なメソッド

よく使われるメソッドを紹介します。

Vector と同じで、途中の要素に挿入したり、削除する操作は速くはありません。これは、影響がある要素以降の要素すべてについて波及的に操作をする必要があるためです。

ただし、Vector と異なり、先頭要素への追加と削除は、速く動作します。

C++ プログラム例（ITP2 1_B）

問題で与えられるクエリに従い、以下の操作を行います。

• クエリ0　push_front/push_back により、与えられた x を先頭/末尾に挿入する。
• クエリ1　与えられた p に対して、A[p] を出力する。
• クエリ2　pop_front/pop_back により先頭/末尾の要素を削除する。

Deque コンテナで提供されているメソッドを、クエリに従い呼び出します。以下が、C++プログラムとなります。

#include <iostream>
#include <deque>

using namespace std;

int main()
{
	deque<int> A;

	int q;
	cin >> q;

	for (int i = 0; i < q; ++i) {
		int command;
		cin >> command;
		if (command == 0) {
			int d, x;
			cin >> d >> x;
			if (d == 0) {
				A.push_front(x);
			} else if (d == 1) 
				A.push_back(x);{
			}
		} else if (command == 1) {
			int p;
			cin >> p;
			cout << A[p] << endl;
		} else if (command == 2) {
			int d;
			cin >> d;
			if (d == 0) {
				A.pop_front();
			} else if (d == 1) {
				A.pop_back();
			}
		}
	}

	return 0;
}

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

最後に

Deque は使ったことがありませんでした。この演習によって、このコンテナの特徴を学ぶことができました。

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