【キュー】

スタックと対になる構造、キューです。この章も新しい文法はゼロです。配列の使い方に制限をかけて、名前をつけたもの、という点はスタックと同じです。違うのはどちらの端から取り出すか、それだけです。ただしその一点が、まったく別の用途を生みます。

キューとは(FIFO)

キュー(queue)は、後ろに並んで、先頭から順に出ていく構造です。レジの行列を想像してください。新しく来た人は列の最後尾に並ぶ。呼ばれるのは先頭の人。最初に並んだ人が、最初に出ていく、この性質を FIFO(First In, First Out: 先入れ先出し)と呼びます。

操作は2つです。

enqueue(エンキュー): 最後尾に並べる

dequeue(デキュー): 先頭から取り出す

JavaScriptの配列では、enqueueは push(末尾に追加)、dequeueは shift(先頭から取り出す)で実現できます。

▶ 実行してみよう

shiftが返すのは "1人目"。最初に並んだ人です。スタックの実験とコードはほぼ同じで、popがshiftに変わっただけ。それだけで、出てくる順番が逆になりました。

スタックとキュー、並べて見る

入れる操作は同じで、出す端だけが違います。2つの構造は、この表の通り鏡写しの関係です。

身の回りのキュー

キューの仕事は「順番の公平さを守る」ことです。例を3つ挙げます。

①処理の待ち行列。 プリンタに5人が同時に印刷を送ったら、到着順に1枚ずつ処理されます。Webサーバーへのリクエスト、メッセージの配送、予約の処理も同様です。「来た順にさばく」仕組みの裏には、ほぼ必ずキューがいます。