js でのキュー実装の詳細な分析 (コード共有)

前回の記事「Vue のエントリ キャッシュ問題の簡単な分析 (コード共有)」では、Vue のエントリ キャッシュの問題について紹介しました。次の記事ではjsでのキューの実装について紹介していますので見ていきましょう。

キュー定義

キュー (Queue) は先入れ先出し (First) in,first out。FIFO と呼ばれます) 原則に基づいた順序付きセット。スタックとの違いは、スタックは先入れ先出しであり、キューは先入れ先出しであることです。スタックは一方の端で出入りし、キューはもう一方の端で出入りします。スタックの削除操作はテーブルの最後で実行され、キューの削除操作はテーブルの先頭で実行されます。シーケンシャルスタックはマルチスタックのスペース共有を実現できますが、シーケンシャルキューは実現できません。共通点は、エンドポイントでは要素の挿入と削除のみが許可されていることです。マルチチェーン スタックとマルチチェーン キューの管理モードは同じにすることができます。

スタック定義

JavaScript はシングルスレッド言語であり、メインスレッドは同期コードを実行します。関数が呼び出されると、呼び出し位置や内部変数などの情報を保存するために、「呼び出しフレーム」とも呼ばれる「呼び出し記録」がメモリ内に形成されます。関数内で他の関数が呼び出される場合、呼び出しレコードの上に別の呼び出しレコードが形成され、すべての呼び出しレコードが「呼び出しスタック」を形成します。 (末尾呼び出し、末尾再帰最適化)

ヒープ (ヒープ) 定義

オブジェクトはヒープに割り当てられ、メモリ内の大きな未編成領域を表すために使用されます。

So

JS はシングル スレッドです。メイン スレッドは同期コードを実行します。イベントや I/O 操作などの非同期タスクは、実行のためにタスク キューに入ります。非同期実行は結果後待機状態に移行し、先入れ先出し実行スタックを形成し、メインスレッドの同期コードが実行された後、「タスクキュー」からイベントを読み込んでコールバックを行います。イベントの非同期タスクが実行されます。実行順序が同期 > 非同期 > コールバックになるのはこのためです。もっと簡単に言うと、メインスレッドが空 (同期) である限り、メインスレッドは「タスク キュー」を読み取ります (非同期)。これは JavaScript です。 操作メカニズム。

この記事では、基本キュー、優先キュー、循環キューを実装します

メッセージ キューとイベント ループイベント ループ

AJavaScriptランタイムには、処理されるメッセージ キュー (非同期タスク ) が含まれています (内部的には、メイン スレッドには入らず、「タスク キュー」 (タスク キュー ) に入るタスクです。例: UIEvents、ajaxネットワーク リクエスト、タイマー setTimeout および setInterval など。各メッセージは関数 ( コールバック関数 callback)。スタックが空の場合、メッセージは処理のためにキューから取得されます。この処理には、メッセージに関連付けられた関数の呼び出しが含まれます (したがって、初期スタックが作成されます)。スタックが再び空になると、メッセージ処理が終了したことを意味します。

このプロセスは周期的であるため、動作メカニズム全体はイベント ループ (イベント ループ ) とも呼ばれます。 .

基本的なキュー

基本的なキューのメソッドには以下の6つのメソッドがあります。

① キューへ(tail) 要素を追加(enqueue)

② (キューの先頭から) 要素を削除 (デキュー)

③ キューの先頭(前方)の要素を確認

④ キューが空かどうかを確認(isEmpty)

⑤ キューの長さ(サイズ)を表示

⑥ キューを表示(印刷)

function Queue() {
  //初始化队列（使用数组实现）
  var items = [];

  //入队
  this.enqueue = function (ele) {
    items.push(ele);
  };

  //出队
  this.dequeue = function () {
    return items.shift();
  };

  //返回首元素
  this.front = function () {
    return items[0];
  };

  //队列是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };

  //清空队列
  this.clear = function () {
    items = [];
  };

  //返回队列长度
  this.size = function () {
    return items.length;
  };

  //查看列队
  this.show = function () {
    return items;
  };
}

var queue = new Queue();
queue.enqueue("hello");
queue.enqueue("world");
queue.enqueue("css");
queue.enqueue("javascript");
queue.enqueue("node.js");
console.log(queue.isEmpty()); // false
console.log(queue.show()); //hello,world,css3,javascript,node.js
console.log(queue.size()); //5
console.log(queue.front()); //hello
console.log(queue.dequeue()); //hello
console.log(queue.show()); //'world', 'css', 'javascript', 'node.js'
console.log(queue.clear());
console.log(queue.size()); //0

優先キューの実装

プライオリティ キューでは、要素の追加または削除は優先度に基づいて行われます。プライオリティ キューの実装方法は 2 つあります: ① 最初に追加し、通常どおりにデキューする; ② 通常に追加して、最初にデキューする

通常のデキューの例 (最小優先キュー) を最初に追加します (この例はキューの実装に基づいており、キューに追加される要素を通常のデータからオブジェクト (配列) タイプに変更します。オブジェクトには の値が含まれます)キューに追加する必要がある要素と優先度):

function PriorityQueue() {
    //初始化队列（使用数组实现）
    var items = []
    //因为存在优先级，所以插入的列队应该有一个优先级属性
    function queueEle(ele, priority) {
        this.ele = ele
        this.priority = priority
    }
    //入队
    this.enqueue = function (ele, priority) {
        let element = new queueEle(ele, priority)
        //为空直接入队
        if (this.isEmpty()) {
            items.push(element)
        }
        else {
            var qeueued = false; //是否满足优先级要求，并且已经入队
            for (let i = 0; i < this.size(); i++) {
                if (element.priority < items[i].priority) {
                    items.splice(i, 0, element)
                    qeueued = true
                    break;
                }
            }
            //如果不满足要求，没有按要求入队，那么就直接从尾部入队
            if (!qeueued) items.push(element)
        }
    }

    //出队
    this.dequeue = function () {
        return items.shift()
    }

    //返回首元素
    this.front = function () {
        return items[0]
    }

    //队列是否为空
    this.isEmpty = function () {
        return items.length == 0
    }

    //清空队列
    this.clear = function () {
        items = []
    }

    //返回队列长度
    this.size = function () {
        return items.length
    }

    //查看列队
    this.show = function () {
        return items
    }
}

var priorityQueue = new PriorityQueue();
priorityQueue.enqueue(&#39;优先级2-1&#39;, 2);
priorityQueue.enqueue(&#39;优先级1-1&#39;, 1);
priorityQueue.enqueue(&#39;优先级1-2&#39;, 1);
priorityQueue.enqueue(&#39;优先级3-1&#39;, 3);
priorityQueue.enqueue(&#39;优先级2-2&#39;, 2);
priorityQueue.enqueue(&#39;优先级1-3&#39;, 1);
priorityQueue.show(); // 按优先级顺序输出

//输出
[
0:queueEle {ele: "优先级1-1", priority: 1},
1:queueEle {ele: "优先级1-2", priority: 1},
2:queueEle {ele: "优先级1-3", priority: 1},
3:queueEle {ele: "优先级2-1", priority: 2},
4:queueEle {ele: "优先级2-2", priority: 2},
5:queueEle {ele: "优先级3-1", priority: 3}
]

循環キュー

循環キューを使用して、太鼓を叩いたり花を渡したりするゲームをシミュレートできます。 (ジョセフ・リング問題): 子供たちのグループが輪になって座り、n 回通過するたびに、立ち止まったときに手に花を持っている子供が排除され、チームに 1 人の子供だけが残り、勝者になります。

ループキュー、子をループするたびに(キューの先頭から)ポップアップし、この子をキューの最後に追加し、n回ループし、ループが停止すると子が先頭に配置されます。キューに子が 1 つだけ残るまで、キューがポップアップ (削除) されます。

function Queue() {
  //初始化队列（使用数组实现）
  var items = [];

  //入队
  this.enqueue = function (ele) {
    items.push(ele);
  };

  //出队
  this.dequeue = function () {
    return items.shift();
  };

  //返回首元素
  this.front = function () {
    return items[0];
  };

  //队列是否为空
  this.isEmpty = function () {
    return items.length == 0;
  };

  //清空队列
  this.clear = function () {
    items = [];
  };

  //返回队列长度
  this.size = function () {
    return items.length;
  };

  //查看列队
  this.show = function () {
    return items;
  };
}

/**
 *
 * @param {名单} names
 * @param {指定传递次数} num
 */
function onlyOne(names, num) {
  var queue = new Queue();
  //所有名单入队
  names.forEach((name) => {
    queue.enqueue(name);
  });

  //淘汰的人名
  var loser = "";
  //只要还有一个以上的人在，就一直持续
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      //把每次出队的人，再次入队 ，这样一共循环了num 次（击鼓传花一共传了num次）
      queue.enqueue(queue.dequeue());
    }
    //到这就次数就用完了，下一个就要出队了
    loser = queue.dequeue();
    console.log(loser + "被淘汰了");
  }
  //到这就剩下一个人了
  return queue.dequeue();
}

var names = ["文科", "张凡", "覃军", "邱秋", "黄景"];
var winner = onlyOne(names, 99);
console.log("金马奖影帝最终获得者是：" + winner);

推奨学習:

JavaScript ビデオ チュートリアル

以上がjs でのキュー実装の詳細な分析 (コード共有)の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。