数据结构之栈

本篇文章可以收获的知识：

• 什么是栈
• 栈的常用操作
• 栈的使用场景
• 一道LeetCode算法题巩固栈
• 如何分析时间复杂度和空间复杂度

什么是栈

栈是一个后进先出的数据结构，在JavaScript中没有栈，但是可以使用Array来实现栈的所有功能。

栈的常用操作

const stack = [] // 栈
stack.push(1) // 入栈
const item = stack.pop() // 出栈

栈的使用场景

• 十进制转二进制

  可以从图中可以看到，我们如果按照顺序求出来的商是00111001，但是十进制转二进制得出来的结果是10011100，明显有后进先出的意思，所以遇到十进制转二进制的问题的时候，使用栈是最适合的。

  

• 有效的括号

  在我们开发中经常也会用到括号，例如([])，这样的括号会发现，(是先进的，[是后进的，但是]是先出的，这就符合栈的后进先出的特点，所以遇到有效括号这类的问题的时候，使用栈是最合适的。后面也会通过一道有效的括号LeetCode算法题来巩固栈的知识。

• 函数调用堆栈

  可以通过下面的代码进行断点进行调试，我们会发现我们先调用fn1，但是最后执行结束的是fn1

  const fn1 = () => {
    fn2()
  }
  
  const fn2 = () => {
    fn3()
  }
  
  const fn3 = () => {}
  
  fn1()
  

LeetCode算法题：题号20，有效的括号

解题思路：

• 对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前
• 满足后进先出的特点

解题步骤：

• 新建一个栈
• 判断字符串的长度是否是偶数，奇数直接判定为不合法
• 扫描字符串，遇到左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配直接判定为不合法
• 遍历结束后，栈为空代表合法，不为空代表不合法

代码实现：

/**
 * @param {string} s
 * @return {boolean}
 */
var isValid = function(s) {
  if (s.length % 2 === 1) { return false; }
 	const stack = [];
  const m = new Map();
  m.set("(", ")");
  m.set("{", "}");
  m.set("[", "]");
  for (let i = 0; i < s.length; i ++) {
    if (m.has(s[i])) {
      stack.push(s[i]);
    } else {
      if (m.get(stack[stack.length - 1]) !== s[i]) {
        return false
      }
      stack.pop()
    }
  }
  return stack.length === 0;
};

分析时间复杂度和空间复杂度：

因为代码中有一个for循环，循环的次数可能是传进来的字符串长度，所以时间复杂度是O(n)，n就是传进来的字符串长度。

代码中定义了两个数据结构，Array和Map，因为Array并不会线性的增长所以是O(n)，Map是O(n)，所以最终的空间复杂度是O(n)，n是传进来的字符串长度。

最后，希望读者可以通过本篇文章对栈有一定的认识和觉悟。。。。。。