JavaScript でキューを実装するための画像とテキストを含む詳細な例

この記事では、javascript に関する関連知識を提供します。主に JavaScript でのキューの実装に関連する問題を紹介し、キューのデータ構造とその操作について説明し、JavaScript でのキューの実装を示します。助けなければなりません。

関連する推奨事項: javascript チュートリアル

1. キューのデータ構造

• キュー「先入れ先出し」(FIFO) データ構造の一種です。最初にキューに入れられた項目 (入力) が、最初にデキューされた項目 (出力) になります。
• キューには、先頭と末尾の 2 つのポインターがあります。キュー内で最も古いキュー項目が先頭にあり、最も新しいキュー項目が末尾になります。
• この列は地下鉄の列に似ており、ドア付近の乗客が列の先頭となり、列に入ったばかりの乗客が列の最後尾になります。

#高レベルの観点から見ると、キューは、データの各項目をその順序で順番に処理できるようにするデータ構造です。保管されています。

2. キュー上の操作

キューは、エンキューとデキューという 2 つの主要な操作をサポートします。さらに、キューに対してピーク操作と長さ操作を実行すると便利な場合があります。

• エンキュー操作
  エンキュー操作はキューの最後に項目を挿入することであり、挿入された項目がキューの最後になります。

上の図のエンキュー操作では項目 8 が末尾に挿入され、8 がキューの末尾になります。

queue.enqueue(8);

• デキュー操作
  デキュー操作では、キューの先頭にある項目が抽出され、キュー内の次の項目が先頭項目になります。 。

上の図では、デキュー操作により項目 7 が返され、キューから削除されます。デキュー後、項目 2 が新しい先頭項目になります。

queue.dequeue(); // => 7

• 検査操作
  検査操作では、キューを変更せずにキューの先頭を読み取ります。

項目 7 は、上の図のキューの先頭であり、検査操作はキューを変更せずにヘッダー (項目) 7 のみを返します。

queue.peek(); // => 7

• キューの長さ
  長さの操作は、キューに含まれるアイテムの数を計算します。

図のキューには 4 つのアイテム (4、6、2、7) があります。その結果、キューの長さは 4 になります。

queue.length; // => 4

• キュー操作の時間の複雑さ
  すべてのキュー操作 (エンキュー、デキュー、ビュー、長さ) について重要なのは、これらの操作はすべて固定時間 O (1) で実行する必要があることです。

一定時間 O(1) は、キューのサイズ (1,000 または 100 万の項目が存在する可能性があります) に関係なく、エンキュー、デキュー、ピーク、および長さの操作をすべて同時に実行する必要があることを意味します。

3. JavaScript でのキューの実装

すべての操作を定数時間 O(1) で実行する必要があるという要件を維持しながら、キュー データ構造の可能な実装を見てみましょう。

class Queue {
  constructor() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  enqueue(item) {
    this.items[this.tailIndex] = item;
    this.tailIndex++;
  }

  dequeue() {
    const item = this.items[this.headIndex];
    delete this.items[this.headIndex];
    this.headIndex++;
    return item;
  }

  peek() {
    return this.items[this.headIndex];
  }

  get length() {
    return this.tailIndex - this.headIndex;
  }
}

const queue = new Queue();

queue.enqueue(7);
queue.enqueue(2);
queue.enqueue(6);
queue.enqueue(4);

queue.dequeue(); // => 7

queue.peek();    // => 2

queue.length;    // => 3

const queue = new Queue() は、キューのインスタンスを作成する方法です。

queue.enqueue(7) メソッドを呼び出して項目 7 をキューに入れます。

queue.dequeue() はキューから先頭項目を取り出しますが、queue.peek() はそれを再度チェックするだけです。

最後に、queue.length はキューに残っている項目の数を示します。

実装について: Queue クラス内の通常のオブジェクト this.items は、数値インデックスによってキュー内の項目を保持します。先頭項目のインデックスは this.headIndex によって追跡され、末尾項目のインデックスは this.tailIndex によって追跡されます。

• キュー メソッドの複雑さ

クラス Queue のメソッド queue()、dequeue()、peek()、および length() は、使用エラー:

属性访问（例如this.items[this.headIndex]），

或执行算术操作（例如this.headIndex++）

したがって、これらのメソッドの時間計算量は定数時間 O(1) です。

4. 概要

キューのデータ構造は「先入れ先出し」(FIFO) の一種で、キューに入れられた最も早い項目がキューから取り出される最も早い項目です。

キューには、エンキューとデキューという 2 つの主な操作があります。さらに、キューにはビューや長さなどの補助操作を含めることができます。

すべてのキュー操作は O(1) を一定時間で実行する必要があります。

関連する推奨事項: JavaScript 学習チュートリアル

以上がJavaScript でキューを実装するための画像とテキストを含む詳細な例の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。