queueは先入れ先出し(FIFO)のデータ構造であり、データを管理する必要のあるプログラミングにおいて非常に便利です。
本記事では、queueの基本的な使い方から応用的な使い方まで、サンプルコードを交えてわかりやすく解説していきます。
queueとは
queueは、STL(Standard Template Library)に含まれるデータ構造の一つで、先入れ先出し(FIFO：First-In-First-Out)の仕組みを持ちます。
つまり、最初に追加された要素が最初に取り出されるという特徴があります。
C++のqueueは、ヘッダーファイル<queue>で定義されています。
また、queueはテンプレートクラスなので、任意の型のデータを扱うことができます。
queueの基本的な使い方
queueの宣言
queueを宣言するには、以下のように記述します。
#include <queue>
std::queue<int> q; // int型の要素を持つ空のqueueを宣言
上記の例では、int型の要素を持つ空のqueueが宣言されています。
queueに要素を追加する
queueに要素を追加するには、push()メソッドを使用します。以下は、3つの整数値を追加する例です。
q.push(1);
q.push(2);
q.push(3);
上記の例では、1, 2, 3という3つの整数値が順番に追加されます。
queueから要素を取り出す
queueから要素を取り出すには、pop()メソッドを使用します。以下は、先頭から2つ目までの整数値(2)を取り出す例です。
q.pop(); // 先頭(1)が削除される
int x = q.front(); // 先頭(2)がxに代入される
上記の例では、pop()メソッドで先頭(1)が削除された後、front()メソッドで先頭(2)が変数xに代入されます。
要素をすべて取り出したい場合、キューが空になるまでループすることですべての要素を取り出せます。
#include <iostream>
#include <queue>
int main() {
std::queue<int> q; // int型の要素を持つ空のqueueを宣言
q.push(1);
q.push(2);
q.push(3);
while (q.empty() == false) {
int x = q.front(); // 先頭がxに代入される
q.pop(); // 先頭が削除される
std::cout << x << std::endl;
}
}
1
2
3queueの要素数を取得する
queue内部にある要素数(サイズ)を取得する場合は、size()メソッドを使用します。
以下は、現在格納されている整数値の総数(3)を取得する例です。
#include <iostream>
#include <queue>
int main() {
std::queue<int> q; // int型の要素を持つ空のqueueを宣言
q.push(1);
q.push(2);
q.push(3);
std::cout << q.size() << std::endl;
}
3上記の例では、size()メソッドで現在格納されている整数値の総数(3)が変数sizeに代入されます。
queueが空かどうかを判定する
先程も登場しましたが、queueが空かどうか判定する場合はempty()メソッドを使用します。
以下は、現在格納されている整数値がある場合とない場合でempty()メソッド結果が異なる例です。
if (q.empty()) {
std::cout << "キューは空です." << std::endl;
} else {
std::cout << "キューには要素が含まれています" << std::endl;
}
queueの応用的な使い方
queueは、先入れ先出し(FIFO)のデータ構造であるため、基本的には先頭から順番に要素を取り出すことが多いです。
しかし、STLのqueueには便利な機能が多数あります。以下では、その中でも特に重要なものを紹介します。
queueの要素を逆順に取り出す
queueから逆順に要素を取り出す方法もあります。
やり方は、queueから全ての要素をstackに移し替え、その後、stackからpopしながら表示します。
#include <iostream>
#include <queue>
#include <stack>
using namespace std;
int main() {
std::queue<int> q; // int型の要素を持つ空のqueueを宣言
q.push(1);
q.push(2);
q.push(3);
stack<int> s;
while (!q.empty()) {
s.push(q.front());
q.pop();
}
while (!s.empty()) {
cout << s.top() << endl;
s.pop();
}
return 0;
}
3
2
1この方法で逆順に取り出すことができますが、そもそもqueueを使っているにも関わらず逆順に取得するのは処理速度の面から見てもおすすめできません。
この場合は、双方向からアクセスできるキューであるdequeを使用しましょう。
queueの要素をソートする
queue自体にソート機能はありませんが、STLアルゴリズムライブラリであるsort関数やstable_sort関数と組み合わせることでソートすることができます。
// 昇順ソート
vector<int> v;
while (!q.empty()) {
v.push_back(q.front());
q.pop();
}
sort(v.begin(), v.end());
for (auto x : v) {
q.push(x);
}
// 降順ソート
vector<int> v;
while (!q.empty()) {
v.push_back(q.front());
q.pop();
}
sort(v.rbegin(), v.rend());
for (auto x : v) {
q.push(x);
}
キューはソートする前提で使用するコンテナクラスではないため、ソートの必要性があるならstd::sortで簡単にソートできるdequeを使うのがおすすめです。