关于算法:小五的算法系列-栈与队列

Hello, 各位怯懦的小伙伴, 大家好, 我是你们的嘴强王者小五, 身体健康, 脑子没病.
自己有丰盛的脱发技巧, 能让你一跃成为资深大咖.
一看就会一写就废是自己的宗旨, 菜到抠脚是自己的特点, 低微中透着一丝丝坚强, 傻人有傻福是对我最大的刺激.
欢送来到小五的算法系列之栈与队列.

前言

此系列文章以《算法图解》和《学习JavaScript算法》两书为外围，其余材料为辅助，并佐以笔者愚见所成。力求以简略、趣味的语言带大家领略这算法世界的微妙。

本文内容为栈和队列。笔者将率领大家从 js 模仿其实现登程，摸索栈与队列在理论场景中的利用。其间会交叉解说 程序调用栈 及 工作队列，使了解程序执行、递归、异步调用等易如破竹。最初，附上几道习题以加深了解及坚固所学。

栈

特点及实现

特点：<后进先出>

下图羽毛球筒就是对栈的形象比喻

创立栈

咱们接下来用js模仿一个栈，并为其增加如下办法：

push(element(s))：入栈 -> 增加一个/多个元素至栈顶
pop()：出栈 -> 移除栈顶元素，并返回被移除的元素
peek()：返回栈顶元素
isEmpty()：该栈是否存在元素
clear()：移除栈中所有元素
size()：栈中元素个数

利用：十进制转二进制

思考: ❓ 如何将十进制转换为二进制

<除2取余，逆序排列>：将十进制数字与2进行累除运算，取余后将余数逆序排列，失去的后果即为该数的二进制.

上述剖析可知，这个是典型的后进先出场景，即栈的场景，代码如下:

import Stack from 'stack';export const binaryConversion = (num: number) => {  const stack = new Stack<number>();  let binaryStr = '';  while (num > 0) {    stack.push(num % 2);    num = Math.floor(num / 2);  }  while (!stack.isEmpty()) {    binaryStr += stack.pop();  }  return binaryStr;}// 输出 10 -> 输入: '1010'

扩大：十进制转其它进制

思路剖析：咱们追加一个入参base代表进制；二进制余数为0 ~ 1，八进制余数为0 ~ 7，十六进制余数为0 ~ 15，搭配字母示意即为0 ~ 9，A ~ F。

增加一组对数字的映射就好了, 功败垂成!

import Stack from 'stack';export const binaryConversion = (num: number, base: number) => {  const stack = new Stack<number>();  let binaryStr = '';+ let baseMap = '0123456789ABCDEF';  while (num > 0) {-   stack.push(num % 2);-   num = Math.floor(num / 2);+   stack.push(num % base);+   num = Math.floor(num / base);  }  while (!stack.isEmpty()) {-   binaryStr += stack.pop();+   binaryStr += baseMap[stack.pop() as number];  }  return binaryStr;}// binaryConversion(100345, 2)  ->  11000011111111001// binaryConversion(100345, 8)  ->  303771// binaryConversion(100345, 16) ->  187F9

函数调用栈 - 了解递归的重要神器

提到递归，大家必定会说，这个我会呀，不就是一直循环本身的过程吗？

可你真的了解递归了吗？快排、归并、树的前中后序遍历等是否能够轻松驾驭？如若不能，则递归仍没有了解透彻，即没有吃透函数的执行程序。

咱们来看上面一段函数:

const greet = (name) => {  console.log(`hello, ${name}!`);  newGreet(name);  console.log('getting ready to say bye...');  bye();}const newGreet = (name) => {  console.log(`how are you, ${name}?`);}const bye = () => {  console.log('ok, bye!');}greet('xiaowu');

它的执行过程是怎么的呢？咱们一起来看下吧

咱们再来写个简略的递归, 求5的阶乘 ($5!$)

const fact = num => {  if (num === 1) return 1;  return num * fact(num - 1);}fact(5);

翠花, 上执行图

扩大：执行上下文

分为 “全局执行上下文” 和 “函数执行上下文”

在开始执行任何代码前，JavaScript会创立全局上下文压入栈底，即 window 对象；每当咱们调用一个函数时，一个新的函数执行上下文就会被创立，如上文过程图所示；整个JavaScript执行过程即是一个 “调用栈”。

队列

特点及实现

特点：<先进先出>

先来先服务即对队列形象的比喻

创立队列

咱们接下来用js模仿一个队列，并为其增加如下办法：

enqueue(element(s))：入队 -> 增加一个/多个元素至队尾
dequeue()：出队 -> 移除队首元素, 并返回被移除的元素
peek()：返回队首元素
isEmpty()：该队列是否存在元素
size()：队列中元素个数

优先队列

理论生存中，并不会时刻都遵循着先来先服务的准则；比方医院，医生会优先解决病情较为重大的患者；这便引出了队列的第一个变种 - 优先队列；

优先队列 - 在插入数据时，按其权重将数据插入到正确的地位。

代码剖析

减少一个代表权重的入参来决定插入地位
改写enqueue办法，使其能依照权重插入正确地位
将Queue类中的private改为protected，使继承后的类可重写enqueue办法
队列为空时，间接push元素
队列非空时，判断元素插入地位，若为队尾则间接push，否则应用splice插入

代码实现

循环队列

“击鼓传花” 讲的是一种游戏规则，人们在击鼓声中传花，鼓声进行时，花传到谁手上，谁就被淘汰，直到残余一个人〈胜者〉。

此游戏始终处于循环状态，由此引出了队列的第二个变种 - 循环队列。

咱们拟定，每循环n次淘汰一人，n为入参。

代码剖析

如何循环？先出列在入列
当队列大于1时开启循环，直至仅剩一位，即胜者

代码实现

JavaScript 工作队列

书接上文，咱们讲到了程序调用栈，而程序并不会均同步执行，当其执行异步操作时又会产生什么呢？

思考: ❓ $setTimeout(() => {执行函数}, 0)$ 为何没有立刻执行

【图片起源 - JavaScript Event Loop 机制详解与 Vue.js 中实际利用】

程序程序执行，顺次入栈；当遇到异步工作时，将其推入工作队列；待程序栈清空后，读取工作队列，将其别离入栈；如此重复的过程，便是 Event Loop - 事件循环。

这里举荐一篇解说JS执行机制的文章这一次，彻底弄懂 JavaScript 执行机制

小试牛刀

以下题目均来自 LeetCode，笔者会为每道题目提供一种解题思路；此思路绝非最佳，欢送各位看官积极思考，并留下本人的独特见解。

LeetCode 232. 用栈实现队列

题目形容

请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（enqueue、dequeue、peek、size、isEmpty）；

你只能应用规范的栈操作 ~ 也就是只有 push, pop, peek, size 和 isEmpty 操作是非法的。

题目剖析

栈实现队列，有两种思路方向，别离为从入栈动手和从出栈动手，笔者抉择从入栈动手；

外围思路即是如何让后入栈的元素在栈底，先入栈的元素在栈顶；

用辅助栈倒换下程序，即可模仿队列，过程如下

代码实现

class Queue<T> {  private items = new Stack<T>();  enqueue(item: T) {    if (this.items.isEmpty()) {      this.items.push(item);      return;    }    const _stack = new Stack<T>();    while (!this.items.isEmpty()) {      _stack.push(this.items.pop() as T);    }    _stack.push(item);    while (!_stack.isEmpty()) {      this.items.push(_stack.pop() as T);    }  }   // 其余办法无变动}

LeetCode 225. 用队列实现栈

题目形容

请你仅应用两个队列实现一个后入先出（LIFO）的栈，并反对一般栈的所有操作（push、 pop、peek、size、isEmpty）；

你只能应用队列的基本操作 ~ 也就是 enqueue, dequeue, peek, size和 isEmpty 这些操作。

题目剖析

队列实现栈，同样有两种思路方向，别离为从入队动手和从出队动手，笔者抉择从入队动手；

外围思路即是如何让后入队的元素在队首，先入队的元素在队尾；

每次入队新元素时，将队列其它元素先出队后入队即可，过程如下

代码实现

class Stack<T> {  private items = new Queue<T>();  push(item: T) {    this.items.enqueue(item);    for (let i = 1; i < this.items.size(); i++) {      this.items.enqueue(this.items.dequeue() as T);    }  }  // 其余办法无变动}

LeetCode 20. 无效的括号

题目形容

题目剖析

咱们看上面这个例子

{[()][]}

给定字符串是否闭合，就是在找最小闭合单元，剔除后持续寻找直至字符串为空则满足条件，过程如下

如上图剖析，与栈的思维齐全吻合
遇左括号则进栈
遇右括号：若为最小闭合单元则出栈，若匹配不上则字符串不闭合
操作实现后，若栈为空，则字符串闭合

代码实现

const isValid = (str: string) => {  const stack = new Stack();  const strMap = {    ')': '(',    ']': '[',    '}': '{',  };  for (let i of str) {    if (['(', '[', '{'].includes(i)) {      stack.push(i);    }    if (strMap[i]) {      if (strMap[i] === stack.peek()) {        stack.pop();      } else {        return false;      }    }  }  return stack.size() === 0;}

LeetCode 32. 最长无效括号

题目形容

题目剖析

此题为上一题的扩大，由上题剖析，咱们可知，此题应持续应用栈；

❓ 那怎么求长度呢与数字挂钩的话借助下数组的下标呗，下标差即为长度

上图可看出长度为 出栈索引减栈顶值；而实际操作时，右括号不入栈，故咱们记录一个bottom值；若栈为空，则减bottom，栈不为空，则减栈顶值。

代码实现

const longestValidParentheses = (str: string) => {  const stack = new Stack<number>();  let maxLen = 0;  let bottom: number | undefined = undefined;  for (let i = 0; i < str.length; i++) {    if (stack.isEmpty() && str[i] === ')') bottom = undefined;    if (str[i] === '(') {      if (bottom === undefined) bottom = i - 1;      stack.push(i);    }    if (!stack.isEmpty() && str[i] === ')') {      stack.pop();      let len = i - (stack.peek() ?? bottom);      if (len > maxLen) maxLen = len;    }  }  return maxLen;}

LeetCode 239. 滑动窗口最大值

题目形容

题目剖析

乍一看题干，这不就是一个行走的队列吗，[1, 3, -1, -3, 5, 3, 6, 7] 执行程序如下

于是笔者实现了如下代码:

const maxSlidingWindow = (nums: number[], k: number) => {  let queue: number[] = [];  let maxArr: number[] = [];  nums.forEach(item => {    if (queue.length <= k) {      queue.push(item);    }    if (queue.length === k) {      let max = queue[0];      for (let i = 1; i < queue.length; i++) {        if (queue[i] > max) max = queue[i];      }      maxArr.push(max);      queue.shift();    }  })  return maxArr;}

当我兴致冲冲的提交到 LeetCode 上时

无奈，咱们持续优化，看看怎么能缩小循环；察看上图，咱们发现，窗口中在最大值左侧的数字没有意义，咱们无需关怀，可将其出队，这样窗口最大值为队首元素；

❓ 队首什么时候出队呢队列中存索引值不就好了，以后元素索引和队首元素的差值与窗口大小比对，若大于窗口大小，则队首元素已不在此窗口中，出队。

代码实现

其本质是一个双端队列，扩大下咱们的 Queue 类，减少 pop、tail 两个办法，代表从队尾移除元素和获取队尾值。

pop() {  return this.items.pop();}tail() {  return this.items[this.items.length - 1];}

const maxSlidingWindow = (nums: number[], k: number) => {  const queue = new Queue<number>();  let maxArr: number[] = [];  nums.forEach((item, index) => {    while (!queue.isEmpty() && item >= nums[queue.tail()]) {      queue.pop();    }    queue.enqueue(index);    if (queue.peek() <= index - k) queue.dequeue();    if (index >= k - 1) maxArr.push(nums[queue.peek()]);  })  return maxArr;}

后记

本文代码 Github 链接：栈，队列

本系列其它文章链接：起航篇 - 排序算法