简述
由于栈有后进先出的特性，利用好栈的这一特性，可以轻松解决一些看似复杂的问题。
例题目录
例题
1、最长有效括号
题目描述：
给定一个只包含 '(' 和 ')' 的字符串，找出最长的包含有效括号的子串的长度。
示例 1:
输入: "(()"
输出: 2
解释: 最长有效括号子串为 "()"
算法
维护一个栈，初始状态下放入 -1，遍历字符串
“(”时， 入栈，
“)”时， 弹出栈顶，如果此时栈空，入栈；不为空，计算 i - stack[-1]
代码
class Solution:
def longestValidParentheses(self, s: str) -> int:
stack = [-1]
res = 0
for i, char in enumerate(s):
if char == '(':
stack.append(i)
else:
stack.pop()
if not stack:
stack.append(i)
else:
res = max(res, i - stack[-1])
return res
时间复杂度：O(n)
这个问题也可以用动态规划来解决。参考
2、逆波兰表达式求值
题目描述：
根据逆波兰表示法，求表达式的值。
有效的运算符包括 +, -, *, / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。
给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
示例 1：
输入: ["2", "1", "+", "3", "*"]
输出: 9
解释: ((2 + 1) * 3) = 9
算法：
维护一个栈，遇到数字入栈，遇到符号弹出两个数字计算后的值再入栈，最后栈中所剩的数就是结果。
代码
class Solution:
def evalRPN(self, tokens: List[str]) -> int:
stack = []
for token in tokens:
if token == '/':
v1 = stack.pop()
v2 = stack.pop()
stack.append(int(v2 / v1))
elif token == '-':
v1 = stack.pop()
v2 = stack.pop()
stack.append(v2 - v1)
elif token == '+':
v1 = stack.pop()
v2 = stack.pop()
stack.append(v2 + v1)
elif token == '*':
v1 = stack.pop()
v2 = stack.pop()
stack.append(v2 * v1)
else:
stack.append(int(token))
return stack[-1]
时间复杂度：O(n)
