C++には、データを順番に処理するためのデータ構造として queue（キュー） が用意されています。
これは STL（Standard Template Library） に含まれており、アルゴリズムやデータ処理、システム開発などさまざまな場面で使われます。
特に、グラフ探索アルゴリズムやシミュレーション処理では非常に重要な役割を持っています。
queueとは何か
queueは FIFO（First In First Out） という仕組みで動作するデータ構造です。
これは次の意味を持ちます。
- 最初に入れたデータが最初に取り出される
つまり、データは 順番通りに処理される という特徴があります。
イメージとしては、次のようなものが近いです。
- レジの待ち行列
- チケット売り場の列
- 電車の乗車待ち列
先に並んだ人が先に処理されるため、queueは「待ち行列」のような構造と言われます。
queueの基本的な仕組み
queueでは、データの追加と取り出しに明確なルールがあります。
- データは 末尾に追加される
- データは 先頭から取り出される
そのため、常に「追加する場所」と「取り出す場所」が固定されています。
この特徴によって、データが 入った順番のまま処理される ようになっています。
queueの基本操作
C++のqueueでは、主に次のような操作が用意されています。
| 操作 | 意味 |
|---|---|
| push | 要素を末尾に追加 |
| pop | 先頭の要素を削除 |
| front | 先頭の要素を取得 |
| back | 末尾の要素を取得 |
| empty | queueが空かどうか判定 |
| size | 要素数を取得 |
それぞれの意味を理解することが、queueを使う上での基本になります。
要素の追加
queueでは、新しい要素は常に 末尾（最後） に追加されます。
たとえば、順番にデータを追加していくと、queueの中では次のような状態になります。
1番目に入れたデータ
2番目に入れたデータ
3番目に入れたデータ
この順番がそのまま保持されます。
先頭要素の取得
queueでは、現在処理されるべき要素は 先頭にあるデータ です。
先頭要素を確認する操作では、データを取得するだけで 削除は行われません。
つまり、
- 内容を見る
- queueの状態は変わらない
という動作になります。
末尾要素の取得
queueでは、末尾の要素も取得できます。
これは
- 最後に追加された要素を確認したい場合
- 現在のqueueの状態を確認したい場合
などに利用されます。
要素の削除
queueでは、削除できるのは 先頭の要素のみ です。
つまり、queueの途中にある要素や末尾の要素を直接削除することはできません。
この制限は、FIFO構造を保つために重要です。
queueが空かどうかの確認
queueを処理する際には、現在データが存在するかどうかを確認する必要があります。
そのために、queueには 空かどうかを判定する機能 が用意されています。
この判定は、次のような場面で使われます。
- データがなくなったら処理を終了する
- 空のqueueからデータを取り出さないようにする
queueを扱うプログラムでは、ほぼ必ず使われる操作です。
要素数の取得
queueには、現在格納されているデータの数を取得する機能もあります。
これによって
- 現在のデータ量を確認する
- 処理状況を管理する
といった用途に利用できます。
queueの処理の基本パターン
queueでは、一般的に次のような流れでデータ処理が行われます。
- queueが空でないか確認
- 先頭要素を取得
- 必要な処理を行う
- 先頭要素を削除
この手順を繰り返すことで、queueのデータを順番に処理できます。
queueに格納できるデータ
queueには、さまざまな型のデータを格納できます。
例えば次のようなものです。
- 整数
- 文字列
- 構造体
- クラス
- ペア型
特に、複数の値をまとめて扱う場合には、構造体やペア型がよく使われます。
queueの代表的な用途
queueは多くのアルゴリズムで使用されます。
特に有名なのが 幅優先探索（BFS） です。
BFS（幅優先探索）
BFSは、グラフや迷路を探索するアルゴリズムです。
この探索では、次のルールで探索が行われます。
- 近い場所から順番に探索する
queueは「入った順に処理する」構造なので、このアルゴリズムと非常に相性が良いです。
そのため、BFSでは必ずと言っていいほどqueueが使用されます。
queueの内部構造
C++のqueueは、実は コンテナそのものではありません。
正確には コンテナアダプタ と呼ばれる仕組みです。
これはどういう意味かというと、既存のコンテナを内部で利用して、queueとしての操作だけを提供しているクラスです。
標準のqueueでは、内部コンテナとして deque が使用されます。
つまり、queueは内部的にはdequeを利用して動作しています。
queueの計算量
queueの基本操作は非常に高速です。
主な操作の計算量は次の通りです。
| 操作 | 計算量 |
|---|---|
| 要素追加 | 定数時間 |
| 要素削除 | 定数時間 |
| 先頭取得 | 定数時間 |
| 末尾取得 | 定数時間 |
| 空判定 | 定数時間 |
| 要素数取得 | 定数時間 |
そのため、queueは大量データを扱う場合でも効率よく処理できます。
queueの注意点
queueにはいくつか重要な制限があります。
ランダムアクセスができない
queueでは、配列のように
- 2番目の要素
- 3番目の要素
のようなアクセスはできません。
アクセスできるのは
- 先頭
- 末尾
のみです。
途中の要素を削除できない
queueでは、削除できるのは 先頭の要素だけ です。
途中の要素を直接削除することはできません。
popは値を返さない
queueの削除操作は、削除するだけで 削除した値は返しません。
そのため、値を使いたい場合は
- 先頭の値を取得
- その後に削除
という順序で処理する必要があります。
queueとpriority_queueの違い
queueとよく似たデータ構造に priority_queue（優先度付きキュー） があります。
違いは次の通りです。
| データ構造 | 取り出し順 |
|---|---|
| queue | 入れた順 |
| priority_queue | 優先度順 |
priority_queueでは、デフォルトでは 値が大きい要素が先に取り出されます。
まとめ
C++のqueueの重要なポイントを整理すると、次のようになります。
- FIFO（先入れ先出し）のデータ構造
- データは末尾に追加される
- データは先頭から取り出される
- 途中の要素にはアクセスできない
- 内部ではdequeが使用されるコンテナアダプタ
- BFSなどの探索アルゴリズムでよく利用される
queueはC++のデータ構造の中でも非常に基本的でありながら、実務やアルゴリズムで頻繁に使われる重要なコンテナです。
以上、C++のqueueの使い方についてでした。
最後までお読みいただき、ありがとうございました。
