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

37次阅读

共计 5907 个字符，预计需要花费 15 分钟才能阅读完成。

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 链接：栈，队列

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

正文完
算法
发表至： 算法
2021-08-10
 0
关于算法:手撸golang-基本数据结构与算法-最大公约数-欧几里得算法辗转相除法
关于算法:ChatGPT-的出现对于-Citizen-developers-意味着什么
关于算法:R语言实现偏最小二乘回归法-partial-least-squares-PLS回归
关于算法:得物技术浅谈AB实验设计实现与分流算法