前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >队列实现

队列实现

作者头像
多云转晴
发布2019-11-18 21:57:48
4310
发布2019-11-18 21:57:48
举报
文章被收录于专栏:webTower

队列 —— Queue

一种先进先出的数据结构。即:先入队的元素出去时也是先出的。

队列

队列的操作方法:

  • enqueue(item) 添加一个元素到;
  • dequeue() 一个元素出队;
  • size() 返回队列长度;
  • print() 打印出队列中的元素;
  • first() 返回队列的第一个元素;

具体实现:

代码语言:javascript
复制
const Queue = (function(){  var map = new WeakMap();  class Queue{    constructor(...item){      map.set(this,[]);      map.get(this).push(...item);    }    enqueue(item){      map.get(this).push(item);    }    dequeue(){        // 注意,这里是 shift 方法,与栈的不同之处      return map.get(this).shift();    }    size(){      return map.get(this).length;    }    print(){      return map.get(this).toString();    }    first(){      return map.get(this)[0];    }  }  return Queue;})();

 使用 ES6 中的 Symbol 类型来实现类属性私有化也可以。这里不再介绍。

队列优先级

有时候,队列会有优先级。比如 VIP 用户总是比普通用户服务优先一些,头等舱总比经济舱要好。实现这样一功能需要在原来的队列基础上加上优先级:当 push 操作时,我们可以传入两个参数,第一个为数据,第二个是优先级大小(数字类型),传入的数值越大优先级越高。

代码实现如下:

代码语言:javascript
复制
const Queue = (function(){  var map = new WeakMap();  class Queue{    constructor(...item){      map.set(this,[]);      item.forEach(i => {        this.enqueue(i,0);      });    }    enqueue(data,level){      if(!level){        map.get(this).push({data,level: 0});      }else{        if(isNaN(level)){        // 你应该是个能成功转化成数值的类型(比如 Boolean、字符数字)          throw Error("level must not be a NaN");        }else{          var ary = map.get(this);          for(let i = 0,len = ary.length;i < len;i ++){            if(ary[i].level < level){            // 注意这里,新项应放在同等级别的末尾              ary.splice(i,0,{                data,                level: Number(level)            // 同一转换成数值              });              break;            // 不能少了 break 语句            }          }        }      }    }    print(){      return map.get(this).map(item => {        return item.data;      });    }    first(){      return map.get(this)[0].data;    }    // ..... 其它方法都一样  }  return Queue;})();

上代码中 constructor 函数只接受数据,当然也可以接收级别。使用对象来当参数,使用 for-in 进行遍历。在 enqueue() 函数中有这么一行:

代码语言:javascript
复制
map.get(this).push({data,level: 0});

这里使用了 ES6 中的对象简写。当属性名和属性值的变量名相同时可以只写一个,{data,level: 0}; 相当于:

代码语言:javascript
复制
{  data: data,  level: 0};

循环队列

循环队列就像手拉手围成一个圈的人群,最后一个人与第一个人拉手构成一个闭环。当第一个元素出队时,他不会直接去除,而是跑到队列的末尾,原来最后一个元素出队后也跑到队尾,再出队就又轮到第一个。就这样循环往复,因此叫“循环队列”。

只需要在原来的基础上在 dequeue(element) 中进行改动:

代码语言:javascript
复制
dequeue(data){  var ary = map.get(this);  var temp = ary.shift();  ary.push(temp);                // 把第一项添加到数组最后一项  return temp;}

击鼓传花

击鼓传花是一个游戏。在这个游戏中,参与者围成一圈,把花尽快地传递给旁边的人。某一时刻传花停止,这个时候花在谁手上,谁就退出圆圈结束游戏。重复这个过程,直到只剩下一个人,这个人就是胜利者。

程序

代码语言:javascript
复制
function hotPotato(nameList,num){  var queue = new Queue(nameList);
  var el = '';  // 循环到还剩一个人  while(queue.size() > 1){      // 每循环 num,就让一个人结束游戏      for(var i = 0;i < num;i ++){          // 那个人传过花后,将他再添加到队列的尾部          // 传完一圈后,又会轮到他          queue.enqueue(queue.dequeue());      }      // 获取被淘汰的人      el = queue.dequeue();      console.log(el + "被淘汰了!");  }  // 返回还剩下的那个人  return queue.dequeue();}

Test

代码语言:javascript
复制
var names = [    "John",    "Jack",    "Camila",    "Ingrid",    "Carl"];
var winner = hotPotato(names,7);
console.log("胜利者 —— ",winner);/* 结果:  Camila被淘汰了!  Jack被淘汰了!  Carl被淘汰了!  Ingrid被淘汰了!  胜利者 ——  John*/

约瑟夫环

据说著名犹太历史学家 Josephus 有过以下的故事:在罗马人占领乔塔帕特后,39 个犹太人与 Josephus 及他的朋友躲到一个洞中,39 个犹太人决定宁愿死也不要被敌人抓到,于是决定了一个自杀方式,41 个人排成一个圆圈,由第 1 个人开始报数,每报数到第 3 人该人就必须自杀,然后再由下一个重新报数,直到所有人都自杀身亡为止。然而 Josephus 和他的朋友并不想遵从,于是他将朋友与自己安排在第 16 个与第 31 个位置,于是逃过了这场死亡游戏。

约瑟夫环

约瑟夫环可以使用队列求解,当然也可以用别的方法求解,比如链表或者数组。

实现源码

代码语言:javascript
复制
// 参数 n 表示间隔几个人之后的那个人要自杀function josephLoop(arr,n = 2){    // 将数组变成 {name: 'xxx',position: number} 的形式    var per = arr.map((item,index) => ({        name: item,        position: index + 1,    }));
    var queue = new Queue(per),        k = n;
    // 当队列中还剩两个人时,退出循环    while(queue.size() > 2){        // n 前面的那几个人不用自杀        while(k --){            // 将报过数的人添加到队列尾部            queue.enqueue(queue.dequeue());        }        // 循环完后别忘了将 k 再还原回 n,进行下一轮的循环        k = n;        var del = queue.dequeue();        console.log("已经删除:",del);    }    // 将剩下的那两个人返回    return queue.values();}

原理

Test

代码语言:javascript
复制
const persons = [  'a','b','c','d','e','f','g','h','i','j',  'k','l','m','n','o','p','q','r','s','t',  'u','v','x','y','z','A','B','C','D','E',  'F','G','H','I','J','K','O','P','Q','S','T'];
console.log("最终结果:",josephLoop(persons));

源码

1. ES6 WeakMap 方式实现

代码语言:javascript
复制
var Queue = (function(){    var map = new WeakMap();
    class Queue{        constructor(item){            map.set(this,[]);            item.forEach(i => {                this.enqueue(i);            });        }
        enqueue(item){            map.get(this).push(item);        }
        dequeue(){            return map.get(this).shift();        }
        print(){            return map.get(this).toString();        }
        first(){            return map.get(this)[0];        }
        size(){            return map.get(this).length;        }
        values(){            return map.get(this);        }    }    return Queue;})();

2. ES5 实现

代码语言:javascript
复制
function Queue(arr){    var q = arr || [];    this.enqueue = function(item){        q.push(item);    }    this.dequeue = function(){        return q.shift();    }    this.print = function(){        return q.toString();    }    this.size = function(){        return q.length;    }    this.values = function(){        return q;    }    this.first = function(){      return q[0];    }}

最后写个实例:

代码语言:javascript
复制
<head>  <style>      .box {      height: 40px;      width: 40px;      border: 2px solid #000;      margin: 20px;      font: 600 24px 'consoles';      text-align: center;      line-height: 40px;      color: green;    }    .on {      background-color: red;      box-shadow: 2px 2px 4px #969696;    }</style></head><body>  <script>      const Queue = (function(){      // ......             循环队列实现源码    })();
    var queue = new Queue();    var count = 0;
    for (let i = 0; i < 10; i++) {      var div = document.createElement('div');      div.className = 'box';      if (count === 0) {        div.classList.add('on');      }      div.textContent = count;      queue.enqueue(div);      document.body.appendChild(div);      count ++;    }
    var timer = setInterval(function () {      document.body.appendChild(queue.dequeue());    },200);</script></body>

效果如下:

本文参与 腾讯云自媒体同步曝光计划,分享自微信公众号。
原始发表:2019-11-17,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 WebTower 微信公众号,前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 队列 —— Queue
    • 队列的操作方法:
      • 具体实现:
        • 队列优先级
          • 循环队列
            • 击鼓传花
              • 程序
              • Test
            • 约瑟夫环
              • 实现源码
              • Test
            • 源码
              • 1. ES6 WeakMap 方式实现
              • 2. ES5 实现
            • 最后写个实例:
            领券
            问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档