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

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 时开启循环，直至仅剩一位，即胜者

👺 代码实现

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

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

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

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

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

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

👺 题目形容

请你仅应用两个栈实现先入先出队列。队列该当反对个别队列反对的所有操作（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);
    }
  }
  
 // 其余办法无变动
}

👺 题目形容

请你仅应用两个队列实现一个后入先出（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);
    }
  }

  // 其余办法无变动
}

👺 题目形容

👺 题目剖析

咱们看上面这个 🌰 例子

{[()][]}

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

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

👺 代码实现

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;}

👺 题目形容

👺 题目剖析

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

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

上图可看出长度为 出栈索引减栈顶值；而实际操作时，右括号不入栈，故咱们记录一个 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;
}

👺 题目形容

👺 题目剖析

乍一看题干，这不就是一个行走的队列吗，[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 链接：栈，队列

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

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

前言

栈

特点及实现

利用：十进制转二进制

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

队列

特点及实现

优先队列

循环队列

JavaScript 工作队列

小试牛刀

LeetCode 232. 用栈实现队列

LeetCode 225. 用队列实现栈

LeetCode 20. 无效的括号

LeetCode 32. 最长无效括号

LeetCode 239. 滑动窗口最大值

后记

Just My Socks（注册教程内含优惠码）

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

前言

栈

特点及实现

利用：十进制转二进制

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

队列

特点及实现

优先队列

循环队列

JavaScript 工作队列

小试牛刀

LeetCode 232. 用栈实现队列

LeetCode 225. 用队列实现栈

LeetCode 20. 无效的括号

LeetCode 32. 最长无效括号

LeetCode 239. 滑动窗口最大值

后记

Just My Socks（注册教程 内含优惠码）

Just My Socks（注册教程内含优惠码）