内容概述

常用的数据结构

栈
队列
集合
链表
字典
树
图
堆

常用的算法

冒泡算法
选择算法
插入算法
归并算法
快速算法
顺序算法
二分搜索

常用算法的设计思想

分而治之
动态规划
贪心
回溯

数据结构 - 栈

栈是什么？

栈是一种后进先出的数据结构，可以通过数组Array的push和pop方法来模拟栈这种数据结构。

class Stack {
  constructor() {
    this.list = [];
  }
  push(item) {
    return this.list.push(item);
  }
  pop() {
    return this.list.pop();
  }
  peek() {
    return this.list[this.list.length - 1];
  }
}

栈的使用场景是什么？

需要后进先出的使用场景。
比如：十进制转二进制、判断字符串的括号是否有效、函数调用栈、二叉树的前序遍历等等

具体案例

一、判断字符串的括号是否有效。

给定一个只包括 ‘(’，’)’，’{’，’}’，’[’，’]’ 的字符串 s ，判断字符串是否有效。

思路：

1. 创建一个栈，遍历整个字符串
2. 遇到左括号就入栈
3. 遇到右括号时，判断当前右括号是否与栈顶元素相匹配，如果不匹配，则直接返回false；如果匹配，就将栈顶元素出栈。
4. 遍历完成后，如果栈为空则返回true，如果栈不空则返回false

function isValid(s) {
  let len = s.length;
  if (len % 2 !== 0) {
    return false;
  }

  let stack = [];

  let map = new Map([
    [')', '('],
    ['}', '{'],
    [']', '['],
  ])

  for (let key of s) {
    if (map.has(key)) {
      if (!stack.length || map.get(key) !== stack[stack.length - 1]) {
        return false;
      } else {
        stack.pop();
      }
    } else {
      stack.push(key);
    }
  }

  return !stack.length
}

二、十进制转二进制

如下，可以通过数字的toString(2)把十进制转换为二进制

const num = 5
console.log(num.toString(2));  // 101

现在利用栈来实现上面的功能

思路：

1. 创建一个栈
2. 执行循环操作，首先把余数入栈，
3. 将num重置为计算得到的商；直到商为0，循环结束
4. 循环当前的栈，依次把栈顶元素出栈，拼接成一个字符串输出

function convertToBinary(num) {
  let str = '';
  const stack = [];

  while (num > 0) {
    stack.push(num % 2)
    num = Math.floor(num / 2);
  }

  while (stack.length) {
    const n = stack.pop();
    str += n;
  }

  return str;
}