js中如何實現(xiàn)隊列

這篇文章主要介紹了js中如何實現(xiàn)隊列，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

隊列定義

隊列（Queue）是一種遵從先進先出（First in,first out。簡稱FIFO）原則的有序集合。 它和棧的不同點是棧是先進后出的，隊列是先進先出的，棧都是在一端進與出，而隊列是在一端進在另一端出。棧的刪除操作在表尾進行，隊列的刪除操作在表頭進行。順序棧能夠?qū)崿F(xiàn)多?？臻g共享，而順序隊列不能。 共同點是只允許在端點處插入和刪除元素。多鏈棧和多鏈隊列的管理模式可以相同。

棧（stack）定義

JavaScript是單線程語言，主線程執(zhí)行同步代碼。 函數(shù)調(diào)用時， 便會在內(nèi)存形成了一個“調(diào)用記錄”，又稱“調(diào)用幀”，保存調(diào)用位置和內(nèi)部變量等信息。如果函數(shù)內(nèi)部還調(diào)用了其他函數(shù)，那么在調(diào)用記錄上方又會形成一個調(diào)用記錄， 所有的調(diào)用記錄就形成一個“調(diào)用?！薄＃ㄎ舱{(diào)用、尾遞歸優(yōu)化）

堆（heap）定義

對象被分配在一個堆中，一個用以表示一個內(nèi)存中大的未被組織的區(qū)域。

所以

JS是單線程， 主線程執(zhí)行同步代碼， 事件、I/O 操作等異步任務，將會進入任務隊列執(zhí)行，異步執(zhí)行有結(jié)果之后，就會變?yōu)榈却隣顟B(tài)， 形成一個先進先出的執(zhí)行棧，主線程的同步代碼執(zhí)行完之后，再從”任務隊列”中讀取事件， 執(zhí)行事件異步任務的回調(diào)。 這就是為什么執(zhí)行順序是， 同步 > 異步 > 回調(diào) 更簡單的說：只要主線程空了（同步），就會去讀取”任務隊列”（異步），這就是JavaScript的運行機制。

本文將實現(xiàn) 基本隊列、優(yōu)先隊列和循環(huán)隊列

消息隊列與事件循環(huán)Event Loop

一個JavaScript運行時包含了一個待處理的消息隊列（異步任務），（內(nèi)部是不進入主線程，而進入”任務隊列”（task queue）的任務。比如UI事件、ajax網(wǎng)絡(luò)請求、定時器setTimeout和setInterval等。 每一個消息都與一個函數(shù)（回調(diào)函數(shù)callback）相關(guān)聯(lián)。當棧為空時，從隊列中取出一個消息進行處理。這個處理過程包含了調(diào)用與這個消息相關(guān)聯(lián)的函數(shù)（以及因而創(chuàng)建了一個初始堆棧幀）。當棧再次為空的時候，也就意味著消息處理結(jié)束。

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

基本隊列

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

① 向隊列（尾部）中添加元素（enqueue）

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

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

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

⑤ 查看隊列的長度（size）

⑥ 查看隊列（print）

function Queue() {
  //初始化隊列（使用數(shù)組實現(xiàn)）
  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

優(yōu)先隊列的實現(xiàn)

在優(yōu)先隊列中，元素的添加或者刪除是基于優(yōu)先級的。實現(xiàn)優(yōu)先隊列有兩種方式：① 優(yōu)先添加，正常出列；② 正常添加，優(yōu)先出列

優(yōu)先添加，正常出列的（最小優(yōu)先隊列）例子（這個例子在實現(xiàn)隊列的基礎(chǔ)上，把添加進隊列的元素從普通數(shù)據(jù)改為對象（數(shù)組）類型，該對象包含需要添加進隊列的元素的值和優(yōu)先級）：

function PriorityQueue() {
    //初始化隊列（使用數(shù)組實現(xiàn)）
    var items = []
    //因為存在優(yōu)先級，所以插入的列隊應該有一個優(yōu)先級屬性
    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; //是否滿足優(yōu)先級要求，并且已經(jīng)入隊
            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('優(yōu)先級2-1', 2);
priorityQueue.enqueue('優(yōu)先級1-1', 1);
priorityQueue.enqueue('優(yōu)先級1-2', 1);
priorityQueue.enqueue('優(yōu)先級3-1', 3);
priorityQueue.enqueue('優(yōu)先級2-2', 2);
priorityQueue.enqueue('優(yōu)先級1-3', 1);
priorityQueue.show(); // 按優(yōu)先級順序輸出

//輸出
[
0:queueEle {ele: "優(yōu)先級1-1", priority: 1},
1:queueEle {ele: "優(yōu)先級1-2", priority: 1},
2:queueEle {ele: "優(yōu)先級1-3", priority: 1},
3:queueEle {ele: "優(yōu)先級2-1", priority: 2},
4:queueEle {ele: "優(yōu)先級2-2", priority: 2},
5:queueEle {ele: "優(yōu)先級3-1", priority: 3}
]

循環(huán)隊列

可以使用循環(huán)隊列來模擬擊鼓傳花的游戲（約瑟夫環(huán)問題）：一群孩子圍成一圈，每次傳遞 n 個數(shù)，停下來時手里拿花的孩子被淘汰，直到隊伍中只剩下一個孩子，即勝利者。

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

function Queue() {
  //初始化隊列（使用數(shù)組實現(xiàn)）
  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 {指定傳遞次數(shù)} num
 */
function onlyOne(names, num) {
  var queue = new Queue();
  //所有名單入隊
  names.forEach((name) => {
    queue.enqueue(name);
  });

  //淘汰的人名
  var loser = "";
  //只要還有一個以上的人在，就一直持續(xù)
  while (queue.size() > 1) {
    for (let i = 0; i < num; i++) {
      //把每次出隊的人，再次入隊 ，這樣一共循環(huán)了num 次（擊鼓傳花一共傳了num次）
      queue.enqueue(queue.dequeue());
    }
    //到這就次數(shù)就用完了，下一個就要出隊了
    loser = queue.dequeue();
    console.log(loser + "被淘汰了");
  }
  //到這就剩下一個人了
  return queue.dequeue();
}

var names = ["文科", "張凡", "覃軍", "邱秋", "黃景"];
var winner = onlyOne(names, 99);
console.log("金馬獎影帝最終獲得者是：" + winner);

感謝你能夠認真閱讀完這篇文章，希望小編分享的“js中如何實現(xiàn)隊列”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學習!