キューのデータ構造の詳しい説明、jsでの実装方法は？

優秀なプログラマーになるには、幅広い知識が必要です。まず最初に、選択したプログラミング言語を理解する必要があります。この記事を読んでいるということは、おそらく 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 になります。 <pre class="brush:js;toolbar:false;">queue.length; // =&gt; 4</pre>

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

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

O (1)

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

O(1)

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

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

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

O(1)

要件 キューはデータ構造です。 <pre class="brush:js;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>

const queue = new Queue()

はキューを作成するインスタンスです。

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() メソッドを改善して、空のキューで実行されたときにエラーをスローするようにします。

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

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