Javascript数据结构详解-队列

Javascript数据结构详解-队列

技术杂谈小彩虹2021-07-08 15:12:2470A+A-

一、概念(Queue)

与前面提到的栈的数据结构相同,队列中的数据也呈线性排列。虽然与栈有些相似,但队列中 添加和删除数据的操作分别是在两端进行的。就和“队列”这个名字一样,把它想象成排成一 队的人更容易理解。在队列中,处理总是从第一名开始往后进行,而新来的人只能排在队尾。

二、特点

  • LIFO(First In First Out),即最先添加的数据最先被取出
  • 线性结构排列

需要注意的是:与栈类似,队列中可以操作数据的位置也有一定的限制。在栈中,数据的添加和删 除都在同一端进行,而在队列中则分别是在两端进行的。队列也不能直接访问位于中间 的数据,必须通过出队操作将目标数据变成首位后才能访问。

三、javascript 简单实现

首先列举一个队列需要实现的基本方法:

  • enqueue 入队,添加到队列尾部;
  • dequeue 出队,队列最前面的数据移除;
  • peek 获取队列最前面的数据(仅获取查看,不改变队列数据)
  • size 返回队列元素的个数
  • isEmpty 返回队列是否为空
  • clear 清除队列
  • toArray 将queue转换成数组

与前面提到的栈的数据结构思路相同,我们用WeakMap和闭包来实现方法私有化:

export let Queue = (function(){
  const items = new WeakMap();
  class Que {
    constructor(){
      items.set(this,[]);
    }
    enqueue(item){
      let q = items.get(this);
      q.push(item)
    }
    dequeue(){
      let q = items.get(this);
      return q.shift();
    }
    peek(){
      let q = items.get(this);
      return q.length > 0 ? q[q.length -1] : undefined;
    }
    size(){
      let q = items.get(this);
      return q.length;
    }
    clear(){
      let q = items.get(this);
       q = [];
    }
    isEmpty(){
      let q = items.get(this);
      return q.length <= 0; 
    }
    toArray(){
      return items.get(this);
    }
  }
  return Que;
})()

四、队列Queue的实际运用

1、击鼓传花游戏

一群人围成一个圈传递花,喊停的时花在谁手上就将被淘汰(每个人都可能在前端,每个参与者在队列位置会不断变化),最后只剩下一个时就是赢者。跟小时候一群人围在一个圆圈玩丢手绢的游戏一样。

const getWinner = (arr,num) => {
  let len = arr.length;
  let out = [];
  const queue = new Queue();
  for(let i=0;i<len;i++){
    queue.enqueue(arr[i]); // 将数组放入队列
  }
  while(queue.size() >1){
    for(let j=0;j<num -1;j++){
      // 每次逃过一劫的人先出队,再加入队列,实现围成一个圆的效果
      queue.enqueue(queue.dequeue());
      console.log(queue.toArray());// 打印当前队列情况
    }
    // num - 1 位置的人逃过一劫,那么num就是当前在队列最顶端的,就是被淘汰的
    out.push(queue.dequeue());
    console.log('本轮已经出局的为:',out);
  }
  const winner = queue.dequeue();
  console.log('winner is ' + winner);
  return winner;
}

getWinner([1,2,4,5,6,7,9],2);// 每次将第2个人淘汰

2、进制转换

const toBainary = num =>{
  const queue = new Queue();
  while(num>0){
    queue.enqueue(num % 2);
    num = parseInt(num / 2);
  }
  // 得到队列的的值要翻转一下
  return queue.toArray().reverse().join('');
}

3、广度优先(BFS)搜索算法

“先来的数据先处理”是一种很常见的思路,所以队列的应用范围非常广泛。最常见的广度优先搜索算法,通常就会从搜索候补中选择最早的数据作为下一个顶点。此时,在候补顶点的管理上就可以使用队列。

此处先留一个坑,比如迷宫问题,路径问题算法的时候,我们再来详谈。

点击这里复制本文地址 以上内容由权冠洲的博客整理呈现,请务必在转载分享时注明本文地址!如对内容有疑问,请联系我们,谢谢!

支持Ctrl+Enter提交

联系我们| 本站介绍| 留言建议 | 交换友链 | 域名展示
本站资源来自互联网收集,仅供用于学习和交流,请遵循相关法律法规,本站一切资源不代表本站立场,如有侵权、后门、不妥请联系本站删除

权冠洲的博客 © All Rights Reserved.  Copyright quanguanzhou.top All Rights Reserved
苏公网安备 32030302000848号   苏ICP备20033101号-1

联系我们