edubun
日本語
English한국어EspañolPortuguêsFrançaisDeutschItalianoРусский日本語
ホーム›プログラミング›データ構造

キュー

1,000個の値を持つJavaScriptの配列から shift で先頭を取り出すと、残りの999個が動きます。リングバッファなら同じことが1ステップでできます。

先入れ先出し

キューは店のレジに並ぶ列です。人は列の後ろに並び、前から順に対応されるので、先に来た人が先に出ていきます。この決まりを先入れ先出し（FIFO）といいます。操作は2つです。エンキューは値を後ろに加え、デキューは先頭の値を取り除きます。MITの6.006の講義資料では、キューは列のインターフェースを insert last(x) と delete first() だけに絞ったものです。

届いた順に仕事を片づけなければならない場所には、どこにでもキューがあります。プリンターを待つ文書、プログラムを待つキー入力、サーバーを待つメッセージなどです。アルゴリズムの講座で学んだ幅優先探索は、まだ訪ねていないマスをキューに入れておきます。だからこそ、同じ距離の輪を順に広げるように探索するのです。

かんたんな方法と、隠れた費用

JavaScriptでいちばん思いつきやすいキューは配列です。push で後ろにエンキューし、shift で先頭からデキューします。これで動きますし、短いキューなら問題ありません。でも、shift が何をしているかを見てください。MDNには「すべての値を左に1つずらす」とあり、ECMAScriptの仕様では、すべての k について要素 k を位置 k − 1 に写すループとして書かれています。最初のユニットで見たように、配列の先頭は費用のかかる側です。n個の値を持つキューからのデキューは、読み取り1回と n − 1 回の移動で、1,000個の値のキューならデキュー1回に1,000ステップかかります（エンジンが内部で近道を使うこともありますが、仕様は何も約束していません）。

空の配列に5個の値をエンキューし、そのあと5個ともデキューすると、エンキューは5ステップ、デキューは 5 + 4 + 3 + 2 + 1 = 15 ステップで、合わせて20ステップです。そのほとんどは、取り除かれもしない値を動かす仕事です。

値ではなく先頭を動かす

解決策は、値を動かすのをやめて、先頭がどこかを覚えておくことです。head というインデックスを持ちます。デキューは head の位置の値を読み、head に1を足すだけで、ほかには何も動きません。ただし、head より前のマスはむだになります。リングバッファ（循環バッファ）はそのマスを使い直します。配列のマスの数を決めておき（たとえば8個）、位置が一周するようにします。つまり7の次のマスは0です。head と size を覚えておきます。次のエンキューはマス (head + size) mod 8 に入り、デキューはマス head の値を取って head を (head + 1) mod 8 に進めます。どちらの操作も1ステップです。その代わり容量は決まっています。size が8になるとキューは満杯で、動的配列のようにすべてを大きなリングに写さない限り、それ以上は入りません。

読み込み中

ドラッグで回転、スクロールまたはピンチで拡大・縮小。

4個の値を持つキューです。「shiftを使う配列」では、デキューのたびに列の残りが動きます。種類を「リングバッファ」に切りかえると、値はその場にとどまり、head と tail がリングを回ります。
ラボで試してみましょう。リングバッファに切りかえ、4回エンキューして8個のマスをすべて埋め、もう1回エンキューします。決まった大きさのリングには9番目のマスがないので、ラボは受けつけません。次に2回デキューしてからエンキューすると、新しい値は一周してマス0に入ります。
n個の値のキューエンキューデキュー
push と shift を使う配列1（償却）読み1回 + 移動 (n − 1) 回
head インデックスを使う配列1（償却）1。ただし先頭のマスはむだになる
決まった大きさのリングバッファ1。または満杯1

どれを使えばよいでしょうか。せいぜい数十個の値しか入らないキューなら、push と shift は短くてわかりやすく、移動の費用もほとんどかかりません。大きな幅優先探索のマスのように何千もの項目が通るキューなら、head インデックスかリングバッファを使うとデキューはいつも1ステップで済み、その差は列が長いほど大きくなります。

FIFO先入れ先出し：値は届いた順に出ていきます。
エンキュー / デキュー後ろに加える / 先頭から取り除く。
shift配列の最初の値を取り除き、ほかのすべての値を1マス左に動かします。
リングバッファ輪のように使う決まった大きさの配列。次の空きマスは (head + size) mod capacity。
  1. キューはどの順番で値を返しますか？
    • 先入れ先出し
    • 後入れ先出し
    • 大きいものから
    • ランダムな順番
  2. A、B、Cをエンキューし、1回デキューします。Dをエンキューし、空になるまでデキューします。出てきた値を順に並べましょう。
  3. push と shift を使うとき、4個の値のキューからのデキュー1回は何ステップですか（読み取り1回と移動）？
  4. 同じ方法で、1,000個の値のキューからのデキュー1回は何ステップですか？
  5. 空の配列から始めます。push で5個の値をエンキューし、shift で5個ともデキューします。合わせて何ステップですか？
  6. リングバッファに8個のマス（0から7）があり、head = 6、size = 3 です。次のエンキューはどのマスを使いますか？
  7. リングバッファからのデキューは、値がいくつ入っていても何ステップですか？
  8. 8マスの決まった大きさのリングに8個の値が入っています。エンキューするとどうなりますか？
    • 先頭の値を上書きする
    • キューが満杯で、値は受けつけられない
    • すべての値を左に動かす
    • 値を並べかえる
  9. アルゴリズムの講座で学んだ探索のうち、待っているマスをキューに入れておくのはどれですか？
    • 二分探索
    • 幅優先探索
    • 深さ優先探索
    • 線形探索
  10. MIT 6.006の言葉でいうと、キューは列のどの2つの操作を使いますか？
    • insert last と delete last
    • insert last と delete first
    • insert first と delete first
    • get at と set at
ポイント
  • キューは先入れ先出しです。後ろにエンキューし、先頭からデキューします。
  • shift は残りの値をすべて動かすので、n個の値からのデキューは n ステップかかります。
  • head インデックスかリングバッファを使えば、デキューは1ステップになります。
  • 大きさ c のリングでは、次の空きマスは (head + size) mod c です。
このコースの出典 (11)
  • MIT OpenCourseWare 6.006 Introduction to Algorithms, Spring 2020 (Demaine, Ku, Solomon)
  • lecture notes 2 Data Structures (interface vs data structure, Sequence and Set interfaces, stack = insert_last/delete_last, queue = insert_last/delete_first, array, linked list, dynamic array, amortized Θ(1) append)
  • 4 Hashing (chaining, pigeonhole collisions, chain length n/m)
  • 6 Binary Trees Part 1 (height, traversal order, O(h) operations) and 7 Binary Trees Part 2: AVL (Adelson-Velsky and Landis, 1962) at ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/pages/lecture-notes
  • MDN Web Docs, Array.prototype.shift (shifts all values left by 1)
  • Array.prototype.unshift, Map (insertion order, Map vs Object, spec requires sublinear average access) and Set (developer.mozilla.org/en-US/docs/Web/JavaScript/Reference/Global_Objects)
  • ECMAScript 2025 Language Specification (tc39.es/ecma262)
  • 24.1 Map Objects and 24.2 Set Objects ("must be implemented using either hash tables or other mechanisms that, on average, provide access times that are sublinear on the number of elements")
  • Array.prototype.shift steps (Repeat, while k < len: move element k to k - 1)
  • D. E. Knuth, The Art of Computer Programming vol. 3 (2nd ed. 1998) section 6.4 History (H. P. Luhn, IBM internal memorandum January 1953, hashing with chaining; digit pairs added mod 10, 31415926 -> 4548) via gwern.net copy, and IEEE Spectrum, "Hans Peter Luhn and the Birth of the Hashing Algorithm" (2018)
  • "A brief history of the stack", SIGCIS (sigcis.org/files/A brief history.pdf: Bauer and Samelson applied for the patent in 1957, US 3,047,228 granted July 31, 1962; IPL list processing by Newell, Simon and Shaw at RAND 1956) and Wikipedia, Information Processing Language (Newell, Shaw, Simon, RAND and Carnegie Institute of Technology, about 1956).

確認日: 2026-10-18