深入解析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());
     // falseconsole.log(queue.show());
     //hello,world,css3,javascript,node.jsconsole.log(queue.size());
     //5console.log(queue.front());
     //helloconsole.log(queue.dequeue());
     //helloconsole.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('优先级2-1', 2);
    priorityQueue.enqueue('优先级1-1', 1);
    priorityQueue.enqueue('优先级1-2', 1);
    priorityQueue.enqueue('优先级3-1', 3);
    priorityQueue.enqueue('优先级2-2', 2);
    priorityQueue.enqueue('优先级1-3', 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中实现队列（代码分享）的详细内容，更多请关注其它相关文章！

声明：本文内容由网友自发贡献，本站不承担相应法律责任。对本内容有异议或投诉，请联系2913721942#qq.com核实处理，我们将尽快回复您，谢谢合作！