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

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

1. キューのデータ構造

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

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

2. キュー上の操作 キュー

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

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

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

queue.enqueue(8);

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

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

queue.dequeue(); // => 7

• 検査オペレーション<br/> 検査オペレーションは、キューを変更せずにキューの先頭を読み取ります。

上の図では項目 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) で実行する必要があるという要件を維持しながら、キュー データ構造の可能な実装を見てみましょう。

クラスキュー{
  コンストラクター() {
    this.items = {};
    this.headIndex = 0;
    this.tailIndex = 0;
  }

  エンキュー(アイテム) {
    this.items[this.tailIndex] = アイテム;
    this.tailIndex++;
  }

  デキュー() {
    const item = this.items[this.headIndex];
    this.items[this.headIndex] を削除します。
    this.headIndex++;
    返品品。
  }

  ピーク() {
    this.items[this.headIndex] を返します。
  }

  長さを取得() {
    this.tailIndex - this.headIndex を返します。
  }
}

const queue = new Queue();

キュー.エンキュー(7);
キュー.エンキュー(2);
キュー.エンキュー(6);
キュー.エンキュー(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 サイトの他の関連記事を参照してください。