データ構造シリーズ-キューとダブルエンドキュー(javascriptタスクキュー)

隊列は先入先出(FIFO、先着順サービスともいう)の原則に従って、順序正しい項目の一つです.
キューに新しい要素を追加し、上から要素を削除します.新しく追加した要素は列の最後に並べなければなりません.

  class Queue {
      constructor() {
        this.count = 0; // {1}
        this.lowestCount = 0; // {2}
        this.items = {}; // {3}
      } 
  }

要素を取得する際により効率的なデータ構造を作成するために、私たちの要素(行｛3｝)を記憶するためのオブジェクトを使用します.
Queue類はStock類と非常に似ていますが、添加と除去の原則は違っています.
キューの使い方:

 enqueue(element(s):列の最後に新しい項目を追加します.

 dequeue():列の一番前の項目を削除し、削除された要素を返します.

 peek():キューの最初の要素に戻ります.最初に追加されても、最初に削除された要素になります.列は作らない

です.
        任意の変更(要素を除去せずに、要素情報のみを返します.Stck類のpeek方法と非常に似ています.)
        この0法は他の言語でもfront方といいます.   法

 isEmpty():列に要素が含まれていない場合、trueに戻ります.そうでなければfalseに戻ります.

 size():キューに含まれる要素の個数を返します.配列のlength属性と似ています.

具体的な実現方法はここでは実現しません.具体的には「javascriptデータ構造とアルゴリズムを勉強する」を参照してください.
ここでは一つの除去方法を紹介します.dequeue()

dequeue() {
      if (this.isEmpty()) {
        return undefined;
      }
      const result = this.items[this.lowestCount]; // {1}
      delete this.items[this.lowestCount]; // {2}
      this.lowestCount++; // {3}
      return result; // {4}
}

queueはkey値としてcountを採用していますので、各要素にアクセスするにはそのkey値を知っていなければなりません.列の一番前の要素を除去するたびに、lowestCountは次のkey値を指すので、+1を要します.
二端子キューデータ構造
デュアルエンド・キュー(deque、またはdoub-ended queue)は、フロントエンドとバックエンドから要素を追加して除去することができる特殊なキューです.
コンピュータ科学では、二重端列の一般的な応用は一連の取消し操作を記憶することである.ユーザがソフトウェアで動作するたびに、スタックのような二重端キューが存在する.キャンセルボタンをクリックすると、操作は二重端キューからイジェクトされ、後から削除されたことを表します.予め定められた一定数の操作を行うと、最初に行った操作は双端列の先端から取り除かれます.二重端行列は先進先出しと後進先出しの原則を同時に遵守しているので、行列とスタックを結合したデータ構造と言える.

class Deque {
    constructor() {
        this.count = 0;
        this.lowestCount = 0;
        this.items = {}; 
    } 
}

二重端列が特殊なキューである以上、その構造関数のコードの一部はキューと同じで、同じ内部属性と以下の方法を含むことができます.isEmpty、clear、size、tostring.
両端に要素の追加と除去を可能にするため、以下のいくつかの方法があります.
addFront(element):この方法は二重端列の先端に新しい要素を追加する.
addBack(element):この方法は、2つのエンド列の後端に新しい要素を追加する(実装方法はQueクラスのenqueue方法と同じ).
removeFront():この方法は、最初の要素を双端列の先端から除去します.
removeBack():この方法は、最初の要素を二重端キューの後端から除去します.peekFront():この方法は、2つのエンド列の先頭の最初の要素を返します.peekBack():この方法は、デュアルエンドのキューバックエンドの最初の要素を返す(実装方法は、Stckクラスのpeek方法と同じ).
ここでは二重端列の要素追加方法を紹介します.

 addFront(element) {
      if (this.isEmpty()) { // {1}
        this.addBack(element);
      } else if (this.lowestCount > 0) { // {2}
        this.lowestCount--;
        this.items[this.lowestCount] = element;
      } else {
        for (let i = this.count; i > 0; i--) { // {3}
          this.items[i] = this.items[i - 1];
        }
        this.count++;
        this.lowestCount = 0;
        this.items[0] = element; // {4}
      } 
}

説明:要素を二重端キューの先端に追加するには、3つのシーンがあります.
第一のシーンはこの二重端行列が空いています.この場合、addBack法を実行することができます.要素は二重端キューの後端に追加され、本例では二重端キューの先端でもある.addBack法は、count属性値を増加させる論理を持っていますので、コードの重複作成を避けるために多重化できます.
第二のシーンは、要素が二重端キューの先端から取り除かれています.つまり、lowestCount属性は1より大きいです.この場合、私達はlowestCount属性を1つ減らして、新しい元素の値をここに置くだけです.
三つ目も最後のシーンはlowestCountが0の場合です.私たちは負の値のキーを設定しながら、ダブルエンドの列の長さを計算するためのロジックを更新し、負のキーの値も含めることができます.この場合、新しい要素を追加する動作は依然として最低の計算コストを維持することができる.プレゼンテーションを容易にするために、このシーンを行列を使用していると見なします.最初のビットに新しい要素を追加するには、すべての要素を後のビットに移動して最初の位置を空けておく必要があります.私たちは既存の値を失いたくないので、最後のビットからすべての値を反復し、要素にインデックス値を付けて1つの位置の値を減らす必要があります.すべての要素7が移動を完了すると、最初のビットが空き状態になります.このようにして、追加すべき新しい要素で上書きすることができます.
例:
循環行列——ドラムを叩いて花を伝えるゲーム
行列はよくコンピュータの領域と私達の現実生活に応用されていますので、いくつかの列の修正バージョンが出てきました.私達はこの章でそれらを実現します.この中の一つは循環行列といいます.循環行列の一例としては、打鼓伝花ゲーム(hot potato)です.このゲームでは子供たちが輪になって、花を早く隣の人に伝えます.ある時花が止まって、この時は誰の手にかかって、誰が丸を消して、ゲームを終了します.この過程を繰り返します.子供が一人しかいないまで.

function hotPotato(elementsList, num) {
    const queue = new Queue(); // {1}
    const elimitatedList = [];
    for (let i = 0; i < elementsList.length; i++) {
        queue.enqueue(elementsList[i]); // {2}
    }
    while (queue.size() > 1) {
        for (let i = 0; i < num; i++) {
            queue.enqueue(queue.dequeue()); // {3}
        }
        elimitatedList.push(queue.dequeue()); // {4}
    }
    return {
        eliminated: elimitatedList,
        winner: queue.dequeue() // {5}
    }; 
}

もう一つの例は回文判定であり、原理は双端列を使って、隊頭と隊尾から除去された要素が等しいかどうかを判断することである.
 
列はjavascriptの中の体現です:JavaScript任務の隊列
ブラウザで新しいタブを開くと、タスクのキューが作成されます.
これは各ラベルが単一スレッドで全てのタスクを処理するためであり、イベントサイクルと呼ばれる.
ブラウザは、HTMLの描画、JavaScriptコードの実行、ユーザのインタラクション(ユーザ入力、マウスクリックなど)の処理、非同期要求の実行、処理などの複数のタスクを担当します.イベントのサイクルをもっと知りたいなら、アクセスできます.https://jakearchibald.com/2015/tasks-microtasks-queues-and-schedules/.