1.栈

基础

1. 特点：后入先出
2. 如：如十进制转二进制，函数调用栈

   例题：

   1.有效括号

   ```html 示例 1： 输入：s = “()” 输出：true 示例 2：

输入：s = “()[]{}” 输出：true 示例 3：

输入：s = “(]” 输出：false

思路：
1. 创建一个栈 stack，遍历字符串
1. 如果stack最后一项与当前字符串相对应则pop，否则则 push，最后分析 stack 长度
1. 创建一个 map 实现 括号的对应关系
```javascript
var isValid = function(s) {
  let map = {
    '{': '}',
    '(': ')',
    '[': ']'
  }
  let stack = []
  for (let i = 0; i < s.length; i++) {
    if (map[stack[stack.length - 1]] === s[i]) {
      stack.pop()
    } else {
      stack.push(s[i])
    }
  }
  // console.log(stack);
  return stack.length === 0
};

2.二叉树的前序遍历

思路：

1. 前序遍历：先处理当前节点，再处理左节点，再处理右节点，深度优先遍历
2. 采用栈空间配合 while 循环的方式，不断地将 left 节点后 push进 stack中，先处理，直到 stack 被清空

   function(root) {
   const res = []
   const stack = []
   if (root) {
    stack.push(root)
   }
   // 清空当前栈
   while(stack.length) { // while 循环会不断地先 push left 到 stack 直到处理完所有的 left
    // 调用栈后入先出
    const n = stack.pop()
    // 1.先把当前 key 的节点放入 res
    res.push(n.val)
    if (n.right) {
      // 2.把 right 节点先 push 进调用栈，实际上是为了后处理 right
      stack.push(n.right)
    }
    if (n.left) {
      // 3.把 left 节点后 push 进调用栈，是为了先处理 left
      stack.push(n.left)
    }
   }
   return res
   };