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

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

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

大家好，我是 柒八九。

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

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

文章 list

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

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

你能所学到的知识点

1. JS 队列的各种实现
2. 滑动窗口的概念和对应算法
3. 利用队列解决和二叉树层树相干的算法

文章概要

0. 知识点简讲
1. 滑动窗口
2. 二叉树的广度优先搜寻（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 函数，会在滑动窗口中增加一个整数，并返回滑动窗口的所有数字的平均值

剖析

1. 在窗口中增加数字，当窗口中的数字的数目超过限度时，还能够从窗口中删除数字。

   • 例如，当窗口的大小为 3, 在增加第四个数字时，就须要从窗口中删除 最早增加 进来的数字。
   • 这是一种 先进先出 的程序，对应的数据容器为 队列
2. 每次在窗口中增加数字之后，须要判断是否超出窗口的大小限度。如果超出限度，从队列中删除一个数字
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]

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

剖析

1. 找出二叉树中 每层 的最大值，在遍历的时须要晓得每层什么时候开始，什么时候完结。

   • 因为，在某个时刻，队列中可能存在位于不同层的节点，如果不做辨别的话，是无奈获取到某层数据的最大值

2. 解决上述问题的一个方法就是 计数

   • 用两个变量别离记录两层节点的数目
   • 变量 current 记录以后遍历这一层中位于队列之中节点的数量
   • 变量 next 记录下一层中位于队列之中节点的数量

3. 最开始把根节点插入队列中，把变量 current 初始化为 1.

   • 一一从队列中取出节点遍历
   • 每当从队列中 取出一个节点 时，以后层的残余节点数 就少一个，即current - 1
   • 以后遍历的节点有子节点，将子节点插入队列中，此时变量 next 的数目减少 1 即next + 1

4. 当 current 的数值变成 0 时，示意以后层的所有节点都曾经遍历完。、

   • 此时，能够通过比拟以后层的所有节点的值，找出最大值

5. 在开始遍历下一层节点之前

   • 须要把 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;
}

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

剖析

1. 利用一个队列辨别不同的层，须要用到两个变量current/next，咱们能够换一个思路。将不同层树的节点，存入不同的队列中。

   • queue1只放以后遍历层的节点
   • queue2只放下一层的节点

2. 最开始时，把二叉树的根节点放入队列 queue1 中。

   • 接下来，每次从队列中取出一个节点遍历
   • 队列 queue1 用来寄存以后遍历层的节点，总是从队列 queue1 中取出节点来遍历
   • 如果以后遍历的节点有子节点，并且子节点位于下一层，则把子节点放入队列queue2
3. 当队列 queue1 被清空时，此时可能获取到以后层的最大值

4. 在开始遍历下一层之前，

   • 把队列 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

剖析

1. 题目越短，越须要咬文嚼字。

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

代码实现

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]

剖析

1. 题目越怪，越须要向已知套路靠
2. 依据右侧视图的概念和示例的后果剖析，其实它就是想要 每层最左边 的一个节点，因而二叉树的右侧视图其实就是从上到下每层最左边的节点

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 版

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