先頭へ戻る

キュー | Programming Place Plus 用語集

Programming Place Plus トップページ -- 用語集

先頭へ戻る

名称


解説

先に追加したデータから取り出されるという特徴をもつデータ構造の一種です。

「先に追加したデータから取り出されるという特徴」は、先入れ先出し(FIFO: First-In First-Out)と呼ばれます。また、キューにデータを追加することをエンキュー(enqueue)、取り出すことをデキュー(dequeue)と呼びます。

先入れ先出しという特徴はよく、順番待ちで並んでいる人間の列に例えられます。先に列に並んだ人から、用を済ませて列を抜けます。実際、キューは待ち行列とも呼ばれます。

現実の人間の列であれば、先頭の人が列を抜けたら、ほかの人たちが1つずつ前に進み出ることになるでしょう。しかし、コンピュータ上で実現する場合、位置を詰める作業は、データの総量によっては非効率です(配列の要素を1つずつ手前にずらす作業と同じ)。そのため、キューを効率的に実現するためには、リングバッファを用いるなどの工夫を要します。

キューを実装する方法については、アルゴリズムとデータ構造編【データ構造】第6章で解説しています。

C++標準ライブラリには、キューを実装した std::queue があります(C++編【標準ライブラリ】第11章


参考リンク


更新履歴


用語集のトップページへ

Programming Place Plus のトップページへ



はてなブックマーク に保存 Pocket に保存 Facebook でシェア
Twitter でツイート Twitter をフォロー LINE で送る
rss1.0 取得ボタン RSS 管理者情報 プライバシーポリシー