一、概念：
栈是一种 “操作受限” 的线性表，体现在只能在一端插入删除数据，符合先进后出的特性。
二、操作：
入栈 push：
从栈顶放入元素， O（1）
出栈 pop：
从栈顶取出元素， O（1）
取栈顶元素 top 或者 peek：
访问栈顶元素但不弹出， O（1）
三、栈的特性：
栈可以用数组实现（顺序栈），也可以用链表实现（链式栈）
四、注意点：
1、函数调用栈
2、编译器利用栈实现表达式求值
3、浏览器的前进后退功能使用栈
五、常见面试题：
例题1：1021. 删除最外层的括号
https://leetcode-cn.com/problems/remove-outermost-parentheses/
有效括号字符串为空 ("")、"(" + A + ")" 或 A + B，其中 A 和 B 都是有效的括号字符串，+ 代表字符串的连接。例如，""，"()"，"(())()" 和 "(()(()))" 都是有效的括号字符串。
如果有效字符串 S 非空，且不存在将其拆分为 S = A+B 的方法，我们称其为原语（primitive），其中 A 和 B 都是非空有效括号字符串。
给出一个非空有效字符串 S，考虑将其进行原语化分解，使得：S = P_1 + P_2 + ... + P_k，其中 P_i 是有效括号字符串原语。
对 S 进行原语化分解，删除分解中每个原语字符串的最外层括号，返回 S 。
示例 1：
输入："(()())(())"
输出："()()()"
解释：
输入字符串为 "(()())(())"，原语化分解得到 "(()())" + "(())"，
删除每个部分中的最外层括号后得到 "()()" + "()" = "()()()"。
示例 2：
输入："(()())(())(()(()))"
输出："()()()()(())"
解释：
输入字符串为 "(()())(())(()(()))"，原语化分解得到 "(()())" + "(())" + "(()(()))"，
删除每个部分中的最外层括号后得到 "()()" + "()" + "()(())" = "()()()()(())"。
示例 3：
输入："()()"
输出：""
解释：
输入字符串为 "()()"，原语化分解得到 "()" + "()"，
删除每个部分中的最外层括号后得到 "" + "" = ""。
思路：
思路：借助辅助栈，如果是左括号，同时stack中还有元素的话，则加入返回的结果集中；如果是右括号，先弹出一个栈中元素，如果栈中还有元素的话，则加入至返回的结果集中。
时间复杂度：O（n），n为字符串的长度
空间复杂度：O（k） ，0 < k < n
代码实现：
class Solution:
def removeOuterParentheses(self, S: str) -> str:
res = ''
stack = []
for s in S:
if s == '(':
if stack:
res += s
stack.append(s)
else:
stack.pop()
if stack:
res += s
return res
例题2：394. 字符串解码 https://leetcode-cn.com/problems/decode-string/
给定一个经过编码的字符串，返回它解码后的字符串。
编码规则为: k[encoded_string]，表示其中方括号内部的 encoded_string 正好重复 k 次。注意 k 保证为正整数。
你可以认为输入字符串总是有效的；输入字符串中没有额外的空格，且输入的方括号总是符合格式要求的。
此外，你可以认为原始数据不包含数字，所有的数字只表示重复的次数 k ，例如不会出现像 3a 或 2[4] 的输入。
示例 1：
输入：s = "3[a]2[bc]"
输出："aaabcbc"
示例 2：
输入：s = "3[a2[c]]"
输出："accaccacc"
示例 3：
输入：s = "2[abc]3[cd]ef"
输出："abcabccdcdcdef"
示例 4：
输入：s = "abc3[cd]xyz"
输出："abccdcdcdxyz"
思路：
思路：借助辅助栈
1、遇到左括号 '['，则将结果和乘数压入栈中
2、遇到右括号 ']'， 则弹出上次记录的res结果和乘数，进行当前结果res的拼接
3、遇到数字，则进行乘数计算
4、遇到字母，则加入返回结果集中
时间复杂度：O（n）
空间复杂度：O（1）
代码实现：
class Solution:
def decodeString(self, s: str) -> str:
stack, res, multi = [], "", 0
for c in s:
if c == '[':
stack.append([multi, res])
res, multi = "", 0
elif c == ']':
cur_multi, last_res = stack.pop()
res = last_res + cur_multi * res
elif '0' <= c <= '9':
multi = multi * 10 + int(c)
else:
res += c
return res
例题3： 20. 有效的括号https://leetcode-cn.com/problems/valid-parentheses/
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
左括号必须用相同类型的右括号闭合。
左括号必须以正确的顺序闭合。
示例 1：
输入：s = "()"
输出：true
示例 2：
输入：s = "()[]{}"
输出：true
示例 3：
输入：s = "(]"
输出：false
示例 4：
输入：s = "([)]"
输出：false
示例 5：
输入：s = "{[]}"
输出：true
思路：
思路：借助辅助栈
1、如果是左括号，则压入栈中；
2、如果是右括号，先判断栈中是否有元素，无的话，则为False；有的话，根据栈中的左括号取出字典中的右括号，判断是否和当前右括号一致。
3、最后判断栈中是否还有元素，有的话，说明括号不能完全匹配。返回False。
时间复杂度：O（n）
空间复杂度：O（n）
代码实现：
class Solution:
def isValid(self, s: str) -> bool:
dic = {'{': '}', '[': ']', '(': ')'}
stack = []
for c in s:
if c in dic:
stack.append(c)
else:
if not stack:
return False
if dic[stack.pop()] != c:
return False
return len(stack) == 0
撰写记录
2021.01.18-07:25:00-第一次撰写
2021.02.13-23:15:00-第二次撰写
2021.02.14-11:22:00-第三次撰写
