待ち行列

プログラム

キュー(queue)とは

キュー(queue)

キューとは、データ構造の一つ(データを格納する入れ物)で、入ってきたデータを順番に格納し、先に格納したデータから順に取り出す、 先入れ先出しFIFO:First-In First-Out)方式のデータ構造です。

キューとは

上記図は、キューのイメージです。お店などに並ぶ待ち行列と似ていることから「待ち行列」とも呼ばれています。

キューに追加する(enqueue)

キューに追加する操作ことを、エンキュー(enqueue)といいます。

以下は、エンキュー(enqueue)の動作イメージです。

「データ1」をキューに追加

まず「データ1」をキューに追加します。

キューに追加 手順1

キューに「データ1」が格納されました。

キューに追加 手順2

「データ2」をキューに追加

次に「データ2」をキューに追加します。

キューに追加 手順3

「データ2」は「データ1」の後に格納されます。後から追加したデータは、待ち行列と同じように先に追加したデータの後に格納されます。

キューに追加 手順4

キューから取り出す(dequeue)

キューから取り出すことを、デキュー (dequeue)といいます。

以下は、デキュー (dequeue)の動作イメージです。

キューからデータを取り出す

キューに「データ1」と「データ2」が格納されているとします。先に格納したのが「データ1」、後に格納したので「データ2」です。

キューに追加 手順4

このキューからデータを取り出すと、先に格納した「データ1」が取得できます。

キューから取り出す 手順1

再びキューからデータを取り出す

再びキューからデータを取り出すと、後に追加した「データ2」が取得できます。

キューから取り出す 手順2

このようにデキュー (dequeue)では、先に格納されたデータから順番に取り出されます。

キュー(queue)とスタック(stack)の違い

キューと似たようなデータ構造に スタック(stack)があります。

キューは、先に格納したデータから順に取り出す 先入れ先出し(FIFO:First-In First-Out)の方式のデータ構造です。

それに比べて、スタックは、後に格納したデータから取り出す 後入れ先出し(Last-In First-Out)の方式のデータ構造です。

ポイント

キュー:先に格納したデータから取り出す(先入れ先出し)

スタック:後に格納したデータから取り出す(後入れ先出し)

よろしければ記事の評価をお願いします

© 2020 ITを分かりやすく解説