概要: このチュートリアルでは、キューデータ構造と、JavaScript キューの実装方法について学習します。
キューデータ構造の紹介
キューは、要素がキューの最後に挿入され、キューの先頭から削除される、要素の順序付けられたリストです。
キューは、先入れ先出し (FIFO) の原則に基づいて動作します。これは、後入れ先出し (LIFO) の原則に基づいて動作するスタックとは異なります。
キューには2つの主要な操作があります
- キューの最後に新しい要素を挿入する操作で、エンキューと呼ばれます。
- キューの先頭から要素を削除する操作で、デキューと呼ばれます。
次の図はキューを示しています。
キューのもう1つの重要な操作は、先頭の要素を取得するピークです。デキュー操作とは異なり、ピーク操作はキューを変更せずに先頭の要素を返します。
キューという名前は、銀行の顧客の待ち行列になぞらえて付けられています。最初に来た顧客が最初にサービスを受け、後で来た顧客はキューの最後に並んで、後でサービスを受けます。
オブジェクトを使用したJavaScriptキューの実装
以下は、オブジェクトを使用してキューデータ構造を実装する方法を示しています。
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
peek() {
return this.elements[this.head];
}
get length() {
return this.tail - this.head;
}
get isEmpty() {
return this.length === 0;
}
}Code language: JavaScript (javascript)動作方法。
まず、キューの要素(elements)を格納するオブジェクトと、コンストラクタで先頭と末尾を追跡するための2つの変数を初期化します。
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
//...
}Code language: JavaScript (javascript)次に、要素をelementsオブジェクトにキューの最後に追加することで、エンキューします。
class Queue {
//...
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
//...
}Code language: JavaScript (javascript)3番目に、キューの先頭から要素を削除します。
class Queue {
// ...
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
//...
}Code language: JavaScript (javascript)4番目に、キューの先頭の要素にアクセスするpeek()メソッドを定義します。
class Queue {
//...
peek() {
return this.elements[this.head];
}
//...
}Code language: JavaScript (javascript)5番目に、キューの長さを取得します。
class Queue {
//...
get length() {
return this.tail - this.head;
}
//...
}Code language: JavaScript (javascript)キューの長さがゼロの場合、キューは空です。
最後に、キューが空の場合はtrueを返すisEmpty()メソッドを定義します。
class Queue {
// ...
get isEmpty() {
return this.tail - this.head;
}
// ...
}Code language: JavaScript (javascript)Queue()コンストラクタ関数から新しいキューを作成するには、次のようにnewキーワードを使用します。
let q = new Queue();Code language: JavaScript (javascript)1から7までの数値をエンキューするには、次のコードを使用します。
for (let i = 1; i <= 7; i++) {
q.enqueue(i);
}Code language: JavaScript (javascript)キューの先頭にある数値を取得するには、peek()メソッドを使用します。
console.log(q.peek()); // 1Code language: JavaScript (javascript)キューの現在の長さを取得するには、次の例のようにlength()メソッドを使用します。
console.log(q.length); // 7Code language: JavaScript (javascript)キューの先頭の要素を削除するには、次のようにdequeue()メソッドを使用します。
// dequeue all elements
while (!q.isEmpty()) {
console.log(q.dequeue());
}Code language: JavaScript (javascript)すべてをまとめる
class Queue {
constructor() {
this.elements = {};
this.head = 0;
this.tail = 0;
}
enqueue(element) {
this.elements[this.tail] = element;
this.tail++;
}
dequeue() {
const item = this.elements[this.head];
delete this.elements[this.head];
this.head++;
return item;
}
peek() {
return this.elements[this.head];
}
get length() {
return this.tail - this.head;
}
get isEmpty() {
return this.length === 0;
}
}
let q = new Queue();
for (let i = 1; i <= 7; i++) {
q.enqueue(i);
}
// get the current item at the front of the queue
console.log(q.peek()); // 1
// get the current length of queue
console.log(q.length); // 7
// dequeue all elements
while (!q.isEmpty) {
console.log(q.dequeue());
}Code language: JavaScript (javascript)まとめ
- キューは、FIFOの原則に基づいて動作するデータ構造です。
