1. 栈简介（后进先出）
- 栈是一个后进先出的数据结构；
-
JS 中没有栈，但是可以用 Array 实现栈中的所有的功能；
image.png
const stack = [];
stack.push(); // 入栈
const item = stack.pop(); // 出栈
const item = stack.[stack.length -1]; // 查看栈顶元素
2. 栈应用场景
image.png
image.png
image.png
image.png
3. 栈算法题
image.png
image.png
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;
}
时间复杂度O(n)和空间复杂度O(n)
