先に追加したデータから取り出されるという特徴をもつデータ構造の一種です。
「先に追加したデータから取り出されるという特徴」は、先入れ先出し(FIFO: First-In First-Out)と呼ばれます。また、キューにデータを追加することをエンキュー(enqueue)、取り出すことをデキュー(dequeue)と呼びます。
先入れ先出しという特徴はよく、順番待ちで並んでいる人間の列に例えられます。先に列に並んだ人から、用を済ませて列を抜けます。実際、キューは待ち行列とも呼ばれます。
現実の人間の列であれば、先頭の人が列を抜けたら、ほかの人たちが1つずつ前に進み出ることになるでしょう。しかし、コンピュータ上で実現する場合、位置を詰める作業は、データの総量によっては非効率です(配列の要素を1つずつ手前にずらす作業と同じ)。そのため、キューを効率的に実現するためには、リングバッファを用いるなどの工夫を要します。
キューを実装する方法については、アルゴリズムとデータ構造編【データ構造】第6章で解説しています。
C++ の標準ライブラリには、キューを実装した std::queue があります(C++編【標準ライブラリ】第11章)。
Programming Place Plus のトップページへ
はてなブックマーク に保存 | Pocket に保存 | Facebook でシェア |
X で ポスト/フォロー | LINE で送る | noteで書く |
RSS | 管理者情報 | プライバシーポリシー |