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 解题思路
对于没有闭合的左括号而言，越靠后的左括号，对应的右括号越靠前
代码语言：javascript复制输入： "{[]}"
输出：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 后进先出
代码语言：javascript复制 const func1 = () => {
func2();
};
const func2 = () => {
func3();
};
const func3 = () => {};
func1();
在这里插入图片描述5. LeetCode：144. 二叉树的前序遍历
学习这个题之前，要先了解下什么是二叉树·～～
在这里插入图片描述进阶： 递归算法很简单，你可以通过迭代算法完成吗？
5.1 利用栈模拟递归，改写递归
代码语言：javascript复制/** * 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]
