1. 栈是什么？
- 一种先进后出的数据结构；
JavaScript没有栈的构造；能够用array实现栈的性能
入栈 push(x);出栈 pop();
const stack = [];// 入栈 stack.push(1);stack.push(2);// 出栈const item1 = stack.pop();const item2 = stack.pop();2. 什么场景下用栈
所有后进先出的构造。
2.1 十进制转换为二进制：最初余数要顺叙输入才是正确二进制；
- 后进去的余数反而要排到后面
- 把余数顺次入栈，而后出栈，就能够实现余数顺叙输入。
2.2 判断括号是否非法：左括号进栈，右括号出栈，栈空则非法；
- 越靠后的左括号，对应的右括号越靠前
- 左括号入栈，右括号出栈，最初栈空了就是非法的
2.3 函数调用栈：最初调用的函数，最先执行完；
- 最初调用的函数，最先执行完
- JS解释器应用栈来管制函数调用的程序
3. leetcode: 20. 无效的括号
valid-parentheses
参考视频：传送门
3.1 解题思路
对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前
输出： "{[]}"输入：true3.2 解题步骤
- 新建一个栈
- 扫描字符串，遇左括号入栈，遇到和栈顶括号类型匹配的右括号就出栈，类型不匹配间接断定为不非法
/** * @param {string} s * @return {boolean} */var isValid = function (s) { if (s.length % 2 === 1) { return false } const stack = []; for (let i = 0; i < s.length; i += 1) { const c = s[i]; if (c === '(' || c === '{' || c === '[') { stack.push(c) } else { const t = stack[stack.length - 1]; if ( (t === '(' && c === ')') || (t === '{' && c === '}') || (t === '[' && c === ']') ) { stack.pop(); } else { return false; } } } return stack.length === 0;};4. 前端与栈：JS中的函数调用栈
4.1 后进先出
const func1 = () => { func2(); }; const func2 = () => { func3(); }; const func3 = () => {}; func1();5. LeetCode：144. 二叉树的前序遍历
学习这个题之前，要先理解下什么是二叉树·～～
进阶： 递归算法很简略，你能够通过迭代算法实现吗？
5.1 利用栈模仿递归，改写递归
/** * Definition for a binary tree node. * function TreeNode(val, left, right) { * this.val = (val===undefined ? 0 : val) * this.left = (left===undefined ? null : left) * this.right = (right===undefined ? null : right) * } *//** * @param {TreeNode} root * @return {number[]} */var preorderTraversal = function (root) { const res = []; const stack = []; if (root) stack.push(root) while (stack.length) { const n = stack.pop(); res.push(n.val) if (n.right) stack.push(n.right) if (n.left) stack.push(n.left) } return res};6. 栈-总结
- 栈是一个后进先出的数据结构
- JavaScript没有栈的构造；能够用array实现栈的性能
- 栈罕用操作：
入栈 push(x);、出栈 pop();、最初元素 stack[stack.length - 1]