はじめに: キューは「先に入れたものを先に取り出す」データ構造
前回の記事では、最後に入れたデータを先に取り出すスタックをJavaScriptで実装しました。スタックは、積み重ねた本を上から取るような「後入れ先出し」のデータ構造でした。
今回扱うキューは、その反対に近い考え方です。
キューは、先に入れたデータを先に取り出すデータ構造です。レジの行列のように、先に並んだ人から順番に処理されるイメージです。
基本情報処理技術者試験では、スタックとキューは対比して問われやすいテーマです。この記事では、JavaScriptの配列を使ってキューを実装しながら、試験に出る知識を実務につなげて理解していきます。
キューとは何か
キューは、データを順番待ちの列のように扱うデータ構造です。
たとえば、レジに人が並んでいる場面を考えてみます。先に並んだ人が先に会計を済ませ、後から来た人は列の後ろに並びます。途中の人を飛ばして処理するのではなく、基本的には並んだ順番に処理します。
このように、先に入れたものを先に取り出す仕組みを FIFO と呼びます。FIFO は First In, First Out の略で、日本語では「先入れ先出し」と説明されます。
キューは、順番を守って処理したい場面で使われます。印刷待ち、タスク待ち、メッセージ処理などをイメージすると分かりやすいです。
キューの基本操作: enqueue と dequeue
キューの基本操作は、主に enqueue と dequeue です。
enqueue は、キューにデータを追加する操作です。行列の最後尾に新しい人が並ぶイメージです。
dequeue は、キューからデータを取り出す操作です。行列の先頭にいる人から順番に取り出します。
また、先頭のデータを見るだけの操作を peek や front と呼ぶことがあります。これは確認するだけなので、データを取り出しません。
空のキューから dequeue しようとした場合は、取り出すものがありません。実装によっては undefined が返ったり、エラーとして扱ったりします。
JavaScriptの配列でキューを実装する
JavaScriptの配列を使うと、キューの動きを簡単に確認できます。
配列の末尾に追加するには push()、先頭から取り出すには shift() を使います。
const queue = [];
queue.push('A');
queue.push('B');
queue.push('C');
console.log(queue);
console.log(queue.shift());
console.log(queue.shift());
console.log(queue.shift());このコードでは、A、B、C の順にデータを追加しています。
取り出すときは、最初に追加した A から取り出されます。続いて B、最後に C が取り出されます。
追加した順番: A -> B -> C
取り出す順番: A -> B -> Cこの順番が、キューの大事な特徴です。スタックでは取り出す順番が逆になりましたが、キューでは入れた順番のまま取り出されます。
キューをクラスとしてまとめる
配列をそのまま使ってもキューの動きは確認できます。ただ、操作の意味を分かりやすくするために、Queue クラスとしてまとめてみます。
class Queue {
constructor() {
this.items = [];
}
enqueue(item) {
this.items.push(item);
}
dequeue() {
return this.items.shift();
}
peek() {
return this.items[0];
}
isEmpty() {
return this.items.length === 0;
}
}
const queue = new Queue();
queue.enqueue('task1');
queue.enqueue('task2');
queue.enqueue('task3');
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.isEmpty());enqueue() はデータを追加し、dequeue() は先頭のデータを取り出します。peek() は先頭のデータを見るだけです。isEmpty() は、キューが空かどうかを確認します。
なお、JavaScriptの shift() は配列の先頭を取り出すため、要素数が多い場合は効率に注意が必要です。この記事では基本情報レベルの理解を優先して、まずは動きが分かりやすい実装にしています。
スタックとの違いを整理する
キューを理解するときは、スタックとの違いをセットで押さえると分かりやすくなります。
スタックは LIFO、つまり後入れ先出しです。最後に入れたものを先に取り出します。本や皿を積み重ねるイメージです。
キューは FIFO、つまり先入れ先出しです。先に入れたものを先に取り出します。行列に並ぶイメージです。
スタック: A -> B -> C と入れると、C -> B -> A と取り出す
キュー: A -> B -> C と入れると、A -> B -> C と取り出す
基本情報処理技術者試験では、操作後にどの値が取り出されるかを問われることがあります。スタックなのかキューなのかを見分けるだけで、答えが大きく変わります。
キューはどこで使われるか
キューの考え方は、順番に処理したい場面でよく使われます。
たとえば、印刷待ちのデータは、先に送られたものから順に処理されるのが自然です。タスク処理やジョブキューでも、順番に処理したい仕事をキューに入れておく考え方があります。
Web開発では、通知、メッセージ処理、非同期処理の理解にもつながります。JavaScriptのイベントループを学ぶときにも、「処理待ちのものがキューに並ぶ」という説明が出てきます。
もちろん、実務では専用のライブラリやメッセージキューサービスを使うこともあります。ただし、その土台には「先に入れたものから処理する」というキューの考え方があります。
試験ではどう問われるか
試験では、キューの操作を順番に追う問題が出てきます。
たとえば、enqueue A、enqueue B、enqueue C のあとに dequeue したら、取り出されるのは A です。さらに dequeue すると B が取り出されます。
問われやすいポイントは、次のようなものです。
enqueueとdequeueの意味- 操作後のキューの中身
- 次に取り出される値
- FIFO の意味
- スタックとの違い
- 待ち行列やタスク処理の例
スタックと同じように、操作の順番を落ち着いて追うことが大切です。行列の先頭から取り出す、と考えるとイメージしやすくなります。
実務ではどう使われるか
実務では、キューという名前を直接使わなくても、考え方として登場することがあります。
JavaScriptの配列で push() と shift() を使う処理は、キュー的な使い方です。小さなデータであれば、これだけでも順番待ちの処理を表現できます。
一方、大量のデータを扱う場合は、shift() の効率やデータ構造を考える必要があります。実務では、配列だけでなく、専用のキュー実装、ジョブキュー、メッセージキュー、データベースなどを使うこともあります。
まずは、キューが「順番に処理するための考え方」だと理解しておくと、非同期処理やタスク処理の説明も読みやすくなります。
まとめ: キューは「並んだ順に処理する」基本のデータ構造
キューは、先に入れたデータを先に取り出すデータ構造です。この性質を FIFO、または先入れ先出しと呼びます。
JavaScriptでは、配列の push() と shift() を使うことで、キューの動きを簡単に確認できます。必要に応じて enqueue()、dequeue()、peek()、isEmpty() のような操作をまとめると、キューとして扱いやすくなります。
基本情報処理技術者試験では、操作後の状態、次に取り出される値、スタックとの違いが重要です。実務でも、タスク処理、ジョブキュー、メッセージ処理、非同期処理の理解につながります。
次に学ぶなら、配列とは違うデータのつなぎ方をする連結リストや、優先度に応じて取り出す優先度付きキューに進むと、データ構造の見方がさらに広がります。
コメント