JavaScriptでキュー構造を実装する方法を詳しく解説

この記事では、キューのデータ構造を理解し、その操作と JavaScript でキュー構造を実装する方法を詳しく紹介します。一定の参考値があるので、困っている友達が参考になれば幸いです。

#1. キューのデータ構造

キューは、「先入れ先出し」(FIFO) データ構造の一種です。 。最初にキューに入れられた項目 (入力) が、最初にデキューされた項目 (出力) になります。

キューには、先頭と末尾の 2 つのポインターがあります。キュー内で最も古いキュー項目が先頭にあり、最も新しいキュー項目が末尾になります。

この列は地下鉄の列に似ており、ドア付近の乗客が列の先頭となり、列に入ったばかりの乗客が列の最後尾になります。

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

2. キュー操作

キューは、Enqueue (エンキュー) と Dequeue (デキュー) という 2 つの主要な操作をサポートします。 、ピーク操作と長さ操作もあります。

2.1 エンキュー操作

エンキュー操作は、キューの最後に項目を挿入し、それをキューの最後にします。

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

queue.enqueue(8);

2.2 デキュー操作

デキュー操作では、キュー内の最初のアイテムが取り出されます。この時点で、キュー内の次のアイテムがキューのリーダーになります。 。

上の図では、デキュー操作により項目 7 が返され、キューから削除されます。チームを離れた後、プロジェクト 2 が新しいチーム リーダーになります。

queue.dequeue(); // => 7

2.3 ピーク操作

ピーク操作はキューの先頭にある項目を読み取りますが、キューは変更しません。上の写真の

7 はチームのリーダーです。ピーク操作では、キューの先頭 7 を返すだけでよく、キューは変更されません。

queue.peek(); // => 7

2.4 length

length 操作は、キューに含まれるアイテムの数を返します。

上の図のキューには、4、6、2 という 4 つの項目があります。 ＃＃＃7＃＃＃。結果のキューの長さは 4 になります。 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">queue.length; // =&gt; 4</pre><div class="contentsignin">ログイン後にコピー</div></div>

2.5 キュー操作の時間計算量

キュー上のすべての操作に関する重要な点: エンキュー、デキュー、ピークおよび長さは一定の時間計算量である必要があります

O (1)

実行します。 一定の時間計算量

O(1)

は、キューのサイズ (アイテム数が 1,000 個か 100 万個か) に関係なく、これらの操作を比較的一貫した時間内で実行する必要があることを意味します。

3. JavaScript を使用してキューを実装する

すべての操作を一定の時間計算量で実装する必要があることを確認する方法を見てみましょう

O(1)

要件 キューはデータ構造です。 <div class="code" style="position:relative; padding:0px; margin:0px;"><pre class="brush:php;toolbar:false">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(); // =&gt; 7 queue.peek(); // => 2 queue.length; // => 3</pre><div class="contentsignin">ログイン後にコピー</div></div>const queue = new Queue()<p> はキューを作成するインスタンスです。 <code>

queue.enqueue(7)

メソッドは 7 をキューに保存します。

queue.dequeue()

キューから先頭項目を削除しますが、queue.peek() はキューの先頭項目のみを読み取ります。 最後の

Queue.Length

は、キューに残っている項目の数を示します。 実装について:

Queue

クラスでは、通常のオブジェクト this.Items が数値インデックスを通じてキューの項目を維持します。キュー内の最初の項目のインデックスは Where.HeadInex によって追跡され、キュー内の最後の項目のインデックスは this.tailIndex によって追跡されます。

キュー メソッドの複雑さは、

Queue の queue() と

dequeue()## にあります。

#、peek() および length() メソッドが存在します: 属性アクセサー (例: this.items[this .headIndex ])、

算術演算の実行 (例:

this.headidex
• )
これらのメソッドの時間計算量は定数時間です
• お(1)。

4. 概要

キューは、先入れ先出し (FIFO) ルールに従うデータ構造です。

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

O(1)

で実行する必要があります。

課題:

dequeue() メソッドと peek()

メソッドを改善して、空のキューで実行されたときにエラーをスローするようにします。

プログラミング関連の知識について詳しくは、プログラミング入門をご覧ください。 ！

以上がJavaScriptでキュー構造を実装する方法を詳しく解説の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。