关于程序员:JS算法探险之队列Queue

乔布斯常常说到一句话：“Stay hungry, Stay foolish”

Stay hungry:永不满足，

Stay foolish: 是说埋头做本人的事，不要理睬前行路上的各种讥嘲声音。

大家好，我是柒八九。

明天，咱们持续摸索JS算法相干的知识点。咱们来谈谈对于<span style=”font-weight:800;color:#FFA500;font-size:18px”>{队列| Queue}</span>的相干知识点和具体的算法。

如果，想理解其余数据结构的算法介绍，能够参考咱们曾经公布的文章。如下是算法系列的往期文章。

文章list

整数
惯例排序算法
数组
字符串
链表
栈

好了，天不早了，干点闲事哇。

你能所学到的知识点

JS队列的各种实现

滑动窗口的概念和对应算法

利用队列解决和二叉树层树相干的算法

文章概要

知识点简讲
滑动窗口
二叉树的广度优先搜寻（BFS）

知识点简讲

队列是个啥

队列是一种听从先进先出（FIFO）准则的有序汇合。队列在尾部增加新元素，并从顶部移除元素。最新增加的元素必须排在队列的开端。

在事实中，最常见的队列的例子就是排队。

JS版本的Queue

因为JS语言的特殊性，不存在真正意义上的Queue构造，个别应用数组特定的Api（push/shift）模仿最简略的queue使得可能满足先进先出的个性。

let queue = [];
queue.push(1);
queue.push(2);
==== 入队 1、2====

queue.shift() // 1出队
queue.shift() // 2出队

在一些简略的场景下，利用数组来模仿队列是能够满足条件的。然而作为一个性能齐备的数据结构，还有一些其余的性能，应用上述的实现形式显的有点顾此失彼。

这里做一个简略的补充：其实针对stack/queue的实现形式有两种，一种是利用数组实现一个存储地址间断的构造，另外一种实现形式是利用链表实现存储地址不间断的构造。

那么，咱们就本人实现一个比拟性能齐备的queue。它有如下的性能点

enqueue(element(s))：向队列尾部增加一个（或多个）新的项。
dequeue()：移除队列的第一项（即排在队列最后面的项）并返回被移除的元素。
peek()：返回队列中第一个元素——最先被增加，也将是最先被移除的元素。队列不做任何变动（不移除元素，只返回元素信息——与 Stack 类的 peek 办法十分相似）。
isEmpty()：如果队列中不蕴含任何元素，返回 true，否则返回 false。
size()：返回队列蕴含的元素个数，与数组的 length 属性相似。

数组版本

class Queue {
   constructor() {
     this.items = []; 
   }
   // 入队
   enqueue(element) {
     this.items.push(element);
  } 
  // 出队，并返回队首元素
  dequeue() {
    return this.items.shift();
  } 
  // 查看，队首元素
  peek() {
    return this.items[0]
  } 
  // 如果队列里没有任何元素就返回`true`,否则返回`false`
  isEmpty() {
   return this.items.length === 0;
  }
  // 返回队列的元素个数
  size() {
   return this.items.length;
  }
  // 移除队列里所有的元素
  clear() {
   this.items = [];
  }
}

下面是应用数组来实现queue,可能实现根本的CRUD。然而，如果还记得咱们在介绍stack的时候，也利用数组实现了一个Stack。

上面是用数组实现stack和queue的具体代码。能够发现，在利用数组实现这两个数据结构时候，除了针对剔除/查看数据有点不同，其余办法都截然不同。(除去办法名的差别)

在针对一些不强调耗费和性能的状况下，用数组实现queue是一个不错且简略的形式。然而，因为queue删除数据的地位是在队首。在利用数组实现的queue中，每次删除一个元素，数组残余的元素的序号地址，都须要进行变更。这样会造成不必要的性能损耗。

所以，大部分状况下，queue是利用链表构建的。

链表版本

这里再做一个简略阐明，在js中，对象类型数据,它自身就是一个以零散形式存储的。咱们来简略做一个试验。

class TestObject {
    constructor() {
        this.elements = {
            o1:{},
            o2:{},
        };
        
  }
}
let to = new TestObject()

咱们利用Memory获取了，此时内存信息。咱们特意查看了TestObject中elements发现，针对他两个属性o1/o2所存的数据都放在不同的内存地址上。

咱们能够应用对象来存储元素信息。这样，就不须要额定的构建链表节点。

class Queue {
  constructor() {
    this.elements = {};
    this.head = 0;
    this.tail = 0;
  }
  enqueue(element) {
    this.elements[this.tail] = element;
    this.tail++;
  }
  dequeue() {
    const item = this.elements[this.head];
    delete this.elements[this.head];
    this.head++;
    return item;
  }
  peek() {
    return this.elements[this.head];
  }
  size() {
    return this.tail - this.head;
  }
  isEmpty() {
    return this.tail - this.head === 0; 
  }
}

滑动窗口

在数组中某一个长度的子数组能够看成数组的一个窗口。若给定数组[1,2,3,4,5,6],那么子数组[2,3,4]就是其中一个大小为3的窗口。窗口向右滑动一个数字，那么窗口就蕴含数字[3,4,5]。

也就是向右滑动窗口，每向右滑动一个数字，都在窗口的最左边插入一个数字，同时把最右边的数字删除。即满足队列 先进先出的个性。

滑动窗口的平均值

题目形容：

给定一个整数数据流和一个窗口大小，依据该滑动窗口的大小，计算滑动窗口里所有数字的平均值。

该类型的构造函数的参数确定滑动窗口的大小

每次调用next函数，会在滑动窗口中增加一个整数，并返回滑动窗口的所有数字的平均值

剖析

在窗口中增加数字，当窗口中的数字的数目超过限度时，还能够从窗口中删除数字。
- 例如，当窗口的大小为3,在增加第四个数字时，就须要从窗口中删除最早增加进来的数字。
- 这是一种先进先出的程序，对应的数据容器为队列
每次在窗口中增加数字之后，须要判断是否超出窗口的大小限度。如果超出限度，从队列中删除一个数字
利用sum实时记录，窗口中现存数据的和

代码实现

class MovingAverage {
    constructor(size) {
      this.nums = new Queue();
      this.capacity = size;
      this.sum = 0;
    }

    next(val) {
      this.nums.enqueue(val);
      this.sum+=val;
      if(this.nums.size()>this.capacity){
        this.sum -=this.nums.dequeue();
      }
      return this.sum / this.nums.size()
    }
}

二叉树的广度优先搜寻（BFS）

二叉树的广度优先搜寻是从上到下按层遍历二叉树，从二叉树的根节点开始，先遍历二叉树的第一层，再遍历第二层，以此类推。

通常基于队列来实现二叉树的广度优先搜寻。

从二叉树的根节点开始，先把根节点放入到一个队列中，而后每次从队列中取出一个节点遍历。
如果该节点有左右子节点，则别离将它们增加到队列中。（先左后右）
以此类推，直到所有节点都被遍历

二叉树节点

  class TreeNode {
      val: number
      left: TreeNode | null
      right: TreeNode | null
      constructor(val?: number, left?: TreeNode | null, right?: TreeNode | null) {
          this.val = (val===undefined ? 0 : val)
          this.left = (left===undefined ? null : left)
          this.right = (right===undefined ? null : right)
      }
  }

利用queue实现二叉树广度优先遍历

function bfs(root){
  let queue = new Queue();
  if(root!=null) {
    queue.enqueue(root);
  }
  
  let result = [];
  while(!queue.isEmpty()){
    let node = queue.dequeue();
    result.push(node.val)
    
    if(node.left!=null){
      queue.enqueue(node.left);
    }
    
    if(node.right!=null){
      queue.enqueue(node.right);
    }
  }
  return result;
}

因为queue的先进先出个性，二叉树的某一层节点依照从左到右的程序插入队列中。因而，这些节点肯定会依照从左到右的程序遍历到。用广度优先(BFS)的程序遍历二叉树，很容易晓得

每层最右边或者最左边的节点
每层的最大值或者最小值

也就是说，对于二叉树的题目如果呈现层的概念，尝试用广度优先来解决问题。

二叉树中每层的最大值

题目形容：

输出一课二叉树，请找出二叉树中每层的最大值。

示例：输出: root = [1,3,2,5,3,null,9]
输入: [1,3,9]

用一个队列实现二叉树的广度优先搜寻

剖析

找出二叉树中每层的最大值，在遍历的时须要晓得每层什么时候开始，什么时候完结。
- 因为，在某个时刻，队列中可能存在位于不同层的节点，如果不做辨别的话，是无奈获取到某层数据的最大值
解决上述问题的一个方法就是计数
- 用两个变量别离记录两层节点的数目
- 变量current记录以后遍历这一层中位于队列之中节点的数量
- 变量next记录下一层中位于队列之中节点的数量
最开始把根节点插入队列中，把变量current初始化为1.
- 一一从队列中取出节点遍历
- 每当从队列中取出一个节点时，以后层的残余节点数就少一个，即current - 1
- 以后遍历的节点有子节点，将子节点插入队列中，此时变量next的数目减少1即next + 1
当current的数值变成0时，示意以后层的所有节点都曾经遍历完。、
- 此时，能够通过比拟以后层的所有节点的值，找出最大值
在开始遍历下一层节点之前
- 须要把current的值设为next的值
- 变量next从新初始化为0

代码实现

function largestValues(root) {
  let current = 0;
  let next = 0;
  let queue = new Queue();
  let result = [];
  if(root!=null){
    queue.enqueue(root);
    current++;
  }
  let max = Number.MIN_SAFE_INTEGER;
  while(!queue.isEmpty()){
    let node = queue.dequeue();
    current--;
    max = Math.max(max,node.val);
    
    if(node.left!=null){
      queue.enqueue(node.left);
      next++;
    }
    
    if(node.right !=null){
      queue.enqueue(node.right);
      next++;
    }
    
    if(current==0){
      result.push(max);
      max = Number.MIN_SAFE_INTEGER;
      current = next;
      next = 0;
    }
  }
  return result;
}

用两个队列实现二叉树的广度优先搜寻

剖析

利用一个队列辨别不同的层，须要用到两个变量current/next，咱们能够换一个思路。将不同层树的节点，存入不同的队列中。
- queue1只放以后遍历层的节点
- queue2只放下一层的节点
最开始时，把二叉树的根节点放入队列queue1中。
- 接下来，每次从队列中取出一个节点遍历
- 队列queue1用来寄存以后遍历层的节点，总是从队列queue1中取出节点来遍历
- 如果以后遍历的节点有子节点，并且子节点位于下一层，则把子节点放入队列queue2
当队列queue1被清空时，此时可能获取到以后层的最大值
在开始遍历下一层之前，
- 把队列queue1指向queue2
- 将队列queue2从新初始化为空队列

代码实现

function largestValues(root) {
  
  let q1 = new Queue();
  let q2 = new Queue();
  let result = [];
  if(root!=null){
    q1.enqueue(root);
  }
  let max = Number.MIN_SAFE_INTEGER;
  while(!q1.isEmpty()){
    let node = q1.dequeue();
    max = Math.max(max,node.val);
    
    if(node.left!=null){
      q2.enqueue(node.left);
    }
    
    if(node.right !=null){
      q2.enqueue(node.right);
    }
    
    if(q1.isEmpty()){
      result.push(max);
      max = Number.MIN_SAFE_INTEGER;
      q1 = q2;
      q2 = new Queue();
    }
  }
  return result;
}

二叉树最底层最右边的值

题目形容：

输出一课二叉树，找出它最底层最右边节点的值。

示例：输出: root = [1,2,3,4,null,5,6,null,null,7]
输入: 7

剖析

题目越短，越须要咬文嚼字。
- 二叉树
- 最底层
依据①所得，咱们能够应用二叉树的广度优先遍历(BFS)来进行层级的解决。
最底层最右边的节点就是最初一层的第一个节点
能够应用一个bottomLeft来保留每层最右边的节点的值。没当新的层级呈现时候，将bottomLeft的值变更为第一个节点的值。
须要辨别不同的层，咱们采纳两个队列的形式来实现

代码实现

function findBottomLeftValue(root){
  let q1 = new Queue();
  let q2 = new Queue();
  
  q1.enqueue(root);
  let bottomLeft = root.val;
  
  while(!q1.isEmpty()){
    let node = q1.dequeue();
    if(node.left !=null){
      q2.enqueue(node.left)
    }
    
    if(node.right !=null){
      q2.enqueue(node.right)
    }
    
    if(q1.isEmpty()){
      q1 = q2;
      q2 = new Queue();
      // 当q1为空时，开始遍历下一层，如果下一层还有节点，则更新bottomLeft
      if(!q1.isEmpty()){
        bottomLeft = q1.peek().val;
      }
    }
  }
  return bottomLeft
}

二叉树的右侧视图

题目形容：

输出一课二叉树，站在该二叉树的右侧，从上到下看到的节点形成二叉树的右侧视图。

示例：输出: root = [1,2,3,null,5,null,4]
输入: [1,3,4]

剖析

题目越怪，越须要向已知套路靠
依据右侧视图的概念和示例的后果剖析，其实它就是想要每层最左边的一个节点，因而二叉树的右侧视图其实就是从上到下每层最左边的节点
有几个要害节点
- 二叉树
- 辨别不同的层
- 最左边的节点
间接二叉树bfs安顿上

代码实现

function rightSideView(root){
  let result = [];
  if(root==null) return result;
  
  let q1 = new Queue();
  let q2 = new Queue();
  q1.enqueue(root);
  while(!q1.isEmpty()){
    let node = q1.dequeue();
    if(node.left!=null){
      q2.enqueue(node.left)
    }
    
    if(node.right !=null){
      q2.enqueue(node.right)
    }
    
    if(q1.isEmpty()){
      result.push(node.val); //此时node是以后层的最初一个节点
      q1= q2;
      q2 = new Queue();
    }
  }
  return result;
}

后记

分享是一种态度。

参考资料：剑指offer/leetcode官网/学习JavaScript数据结构与算法第3版

全文完，既然看到这里了，如果感觉不错，顺手点个赞和“在看”吧。

关于程序员:JS算法探险之队列Queue

文章list

你能所学到的知识点

文章概要

知识点简讲

队列是个啥

JS版本的Queue

数组版本

链表版本

滑动窗口

滑动窗口的平均值

剖析

代码实现

二叉树的广度优先搜寻（BFS）

二叉树中每层的最大值

用一个队列实现二叉树的广度优先搜寻

剖析

代码实现

用两个队列实现二叉树的广度优先搜寻

剖析

代码实现

二叉树最底层最右边的值

剖析

代码实现

二叉树的右侧视图

剖析

代码实现

后记

评论

发表回复取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

关于程序员:JS算法探险之队列Queue

文章list

你能所学到的知识点

文章概要

知识点简讲

队列是个啥

JS版本的Queue

数组版本

链表版本

滑动窗口

滑动窗口的平均值

剖析

代码实现

二叉树的广度优先搜寻（BFS）

二叉树中每层的最大值

用一个队列实现二叉树的广度优先搜寻

剖析

代码实现

用两个队列实现二叉树的广度优先搜寻

剖析

代码实现

二叉树最底层最右边的值

剖析

代码实现

二叉树的右侧视图

剖析

代码实现

后记

评论

发表回复 取消回复

更多文章

苹果iOS打包的ipa应用无法安装？一篇文章带你了解可能的原因及排查方法

图解Golang：从零开始实现简易版过期LRU缓存

深入解析：基于Delta的线性数据结构模型，打造高效富文本编辑器

轻松管理社交媒体：使用Automa插件实现一键拉黑功能

发表回复取消回复