栈适合解决匹配类问题
我们在删除相邻重复项的时候，其实就是要知道当前遍历的这个元素，我们在前一位是不是遍历过一样数值的元素，那么如何记录前面遍历过的元素呢？
所以就是用栈来存放，那么栈的目的，就是存放遍历过的元素，当遍历当前的这个元素的时候，去栈里看一下我们是不是遍历过相同数值的相邻元素，然后再去做对应的消除操作。
有效的括号
力扣题目
考点：栈(对称匹配类的题目)
思路：遍历这个字符串，当栈为空或者栈顶元素和遍历元素不相等的话，则把遍历元素添加到栈中，如果栈顶元素=遍历元素，则pop掉栈顶元素。
代码：
时间复杂度：O(n)
空间复杂度：O(n)
var isValid = function(s) {
//若为单数，直接返回false
if(s.length % 2 !==0) return false
let stack=[]
for(let i=0;i<s.length;i++){
if(s[i] === '(' || s[i] === '[' ||s[i] === '{' ){
stack.push(s[i])
continue
}
if((s[i]===')' && '('=== stack[stack.length-1]) ||( s[i]===']' && '['=== stack[stack.length-1] )||(s[i]==='}' && '{'=== stack[stack.length-1])){
stack.pop()
}else{
return false
}
}
return stack.length === 0
};
删除字符串中的所有相邻重复项
考点：栈（匹配问题）
代码：
时间复杂度：O(n)
空间复杂度:O(n)
var removeDuplicates = function(s) {
let stack=[]
for(let i=0;i<s.length;i++){
// 相同就弹出，
// 不同就压栈
if(stack[stack.length-1] === s[i]){
stack.pop()
continue
}
stack.push(s[i])
}
return stack.join('')
};
逆波兰表达式求值
注意：
- 数字做运算的顺序
- 遇到除号；结果小于0时，向上取整，；结果大于0时，向下取整
- 遇到减号，且被减数小于零，即2--3的情况；将符号转换为正号进行运算
时间复杂度：O(n)
空间复杂度：O(n)
var evalRPN = function(tokens) {
//遇到数字放进去
//遇到符号，出栈两个数字；再把结果放进去
let stack=[]
let sign= '+-*/'
let res =0
for(let i in tokens){
if(sign.includes(tokens[i])){
let n1=stack.pop()
let n2=stack.pop()
if(tokens[i] ==='/'){ //若为除法，特殊处理
res = ((n2)/(n1)) < 0? Math.ceil((n2)/(n1)): Math.floor((n2)/(n1))
}else if(tokens[i] ==='-' && n1<0){ //若出现类似2--3的情况，特殊处理
res= eval(n2+'+'+Math.abs(n1))
}else{
res = eval((n2)+tokens[i]+(n1))
}
stack.push(res)
continue
}
stack.push(tokens[i])
}
return Number(stack[0])
};
参考：
感觉参考的代码更优雅:
入栈时，直接放入数字类型；求除数那里利用了按位或运算，简化写法：
n1 / n2 | 0
var evalRPN = function (tokens) {
const stack = [];
for (const token of tokens) {
if (isNaN(Number(token))) { // 非数字
const n2 = stack.pop(); // 出栈两个数字
const n1 = stack.pop();
switch (token) { // 判断运算符类型，算出新数入栈
case "+":
stack.push(n1 + n2);
break;
case "-":
stack.push(n1 - n2);
break;
case "*":
stack.push(n1 * n2);
break;
case "/":
stack.push(n1 / n2 | 0);
break;
}
} else { // 数字
stack.push(Number(token));
}
}
return stack[0]; // 因没有遇到运算符而待在栈中的结果
};
