深入解析js中實作佇列（程式碼分享）

在

之前的文章《淺析Vue中入口快取的問題（程式碼分享）》中，跟大家介紹了解Vue中入口快取的問題。以下這篇文章跟大家介紹js中實作佇列，夥伴們來看看吧。

佇列定義

佇列（Queue）是一種遵從先進先出（First in,first out。簡稱FIFO）原則的有序集合。它和棧的不同點是棧是先進後出來的，隊列是先進先出的，棧都是在一端進與出，而隊列是在一端進在另一端出。堆疊的刪除操作在表尾進行，佇列的刪除操作在表頭進行。順序棧能夠實現多棧空間共享，而順序佇列不能。共同點是只允許在端點處插入和刪除元素。多鏈棧和多鏈佇列的管理模式可以相同。

堆疊（stack）定義

JavaScript是單執行緒語言，主執行緒執行同步程式碼。函數呼叫時， 便會在記憶體形成了一個“呼叫記錄”，又稱“呼叫幀”，保存呼叫位置和內部變數等資訊。如果函數內部也呼叫了其他函數，那麼在呼叫記錄上方又會形成一個呼叫記錄， 所有的呼叫記錄就形成一個「呼叫堆疊」。 （尾呼叫、尾遞歸最佳化）

堆（heap）定義

物件被分配在一個堆中，一個用以表示一個記憶體中大的未被組織的區域。

所以

JS是單線程， 主執行緒執行同步程式碼，事件、I/O 操作等非同步任務，將會進入任務佇列執行，非同步執行有結果之後，就會變成等待狀態， 形成一個先進先出的執行棧，主執行緒的同步程式碼執行完之後，再從」任務佇列」讀取事件， 執行事件非同步任務的回呼。這就是為什麼執行順序是， 同步> 非同步> 回呼更簡單的說：只要主執行緒空了（同步），就會去讀取」任務佇列」（非同步），這就是 JavaScript的運作機制。

本文將實作基本佇列、優先權佇列與循環佇列

訊息佇列與事件循環Event Loop

一個JavaScript運行時包含了一個待處理的訊息佇列（非同步任務），（內部是不進入主線程，而進入」任務佇列」（task queue）的任務。例如UI事件、ajax網路請求、計時器setTimeout和setInterval#等。每個訊息都與一個函數（回呼函數callback）相關聯。當堆疊為空時，從佇列中取出一個訊息進行處理。這個處理過程包含了呼叫與這個訊息相關聯的函數（以及因而創建了一個初始堆疊幀）。當棧再次為空的時候，也意味著訊息處理結束。

這個過程是循環不斷的，所以整個的這種運行機制又稱為Event Loop（事件循環）。

基本佇列

基本佇列的方法中，包含了一下6個方法

① 向佇列（尾部）中新增元素（enqueue）

②（從隊列頭部）刪除元素（dequeue）

③ 查看隊列頭部的元素（front）

④ 查看隊列是否為空（isEmpty）

⑤ 查看佇列的長度（size）

⑥ 查看佇列（print）

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

優先佇列的實作

在優先佇列中，元素的添加或刪除是基於優先權的。實作優先佇列有兩種方式：① 優先添加，正常出列；② 正常添加，優先出列

優先添加，正常出列的（最小優先隊列）例子（這個例子在實現隊列的基礎上，把添加進隊列的元素從普通數據改為對象（數組）類型，該對象包含需要添加進隊列的元素的值和優先順序）：

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 個數，停下來時手裡拿花的孩子被淘汰，直到隊伍中只剩下一個孩子，即勝利者。

循環隊列，每次循環的時候（從隊列頭部）彈出一個孩子，再把這個孩子加入到隊列的尾部，循環n 次，循環停止時彈出隊列頭部的孩子（被淘汰），直到隊列中只剩下一個孩子。

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中文網其他相關文章！