栈题目总结——用栈解决消消乐问题

定义

• 消消乐的常见形式是消除相邻的相同的事物。我们可以把相邻这个条件用栈实现，相同的这个条件由我们决定，一旦我们遇到符合相同条件的情况，我们就把相邻的事物消除掉，由此我们就可以用栈解决类似消消乐的问题了。

题目

LC20. 有效的括号

• 这道题相同的条件是，左括号匹配右括号，比如 { 和 } 的匹配，如果 { 匹配的是 [ ,],( ) 则视为不相同
• 相邻条件为左括号相邻右括号，第一个匹配的括号在 字符串上的排列必是相邻的，后续匹配的括号则靠栈实现相邻，代码为 stack.peek() == str.chatAt(i)
• 这道题的栈空和栈为空的两种情况，也能解决括号不匹配的两种情况

LC1047. 删除字符串中的所有相邻重复项

• 相同的条件是字母相同
• 相邻条件为字母相邻，第一个相邻的字母在 字符串上的排列必是相邻的，后续匹配的字母则靠栈实现相邻

LC150. 逆波兰表达式求值

• 相同的条件在这道题为存入字符是运算符 \+ , - , * , /
• 相邻条件为运算符前的数字，相邻的事物为数字。
• 由此，我们要在遇到运算符时，把运算符前的数字消除掉