关于程序员: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版

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