什么是栈

一个后进先出的数据结构，用栈的方法，可以模拟递归，改写递归

栈 - 图1

如何实现栈

  1. const stack = []
  3. // 入栈
  4. stack.push(1)
  5. stack.push(2)
  7. //出栈
  8. stack.pop();
  9. stack.pop();

场景

后进先出的场景。比如: 十进制转二进制，判断字符串括号是否有效，函数调用堆栈

十进制转二进制

算法: 当前值处以2，余1/0, 一直到0位置。以余数入栈，再依次出栈，拿到最终结果

栈 - 图2

  • 如上图所示，35的二进制值是100011
  1. var trans = function(data) {
  2.     const stack = []
  3.     while (data > 0) {
  4.         // 拿到余数，存入栈
  5.         stack.push(data % 2);
  6.         // 向下取整
  7.         data  = Math.floor(data / 2)
  8.     }
  9.     return stack.reverse().join().replace(/,/g, "")
  10. };

有效的括号

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

有效字符串需满足：

左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。

  • 算法： 判断括号是否有效闭合，越靠后的左扩号，对应的右括号越靠前。左括号入栈，右括号出栈，最后栈空了就是合法的
  • 解法 
  1. var isValid = function(s) {
  2.     const stack = [];
  3.     for(let i = 0 ; i < s.length; i++) {
  4.         const c = s[i]
  5.         if(c === '(' || c === '[' || c === '{') {
  6.             stack.push(c)
  7.         } else {
  8.             const t = stack[stack.length - 1];
  9.             if(
  10.                 (t === '{' && c === '}')||
  11.                 (t === '[' && c === ']')||
  12.                 (t === '(' && c === ')')
  13.             ) {
  14.                 stack.pop()
  15.             } else {
  16.                 return false
  17.             }
  18.         }
  19.     }
  20.     return stack.length === 0
  21. };
  • 时空复杂度
    • 时间复杂度,O(n)
    • 空间复杂度,O(n)

函数调用堆栈

  • 最后调用的函数，最先执行完
  • Js解释器使用栈来控制函数的调用顺序

二叉树前序遍历

给你二叉树的根节点 root ，返回它节点值的 前序 遍历。

  1. var preorderTraversal = function(root) {
  2.     const res = []
  3.     const stack = []
  4.     if(root) {
  5.         stack.push(root)
  6.     }
  7.     while(stack.length) {
  8.         const n = stack.pop()
  9.         res.push(n.val)
  10.         if(n.right) stack.push(n.right)
  11.         if(n.left) stack.push(n.left)
  12.     }
  13.     return res
  14. };
  • 时空复杂度
    • 时间复杂度,O(n)
    • 空间复杂度,O(n)