栈基础
栈是一种”先进后出”(FILO,Fist In Last Out)的数据结构
出栈和入栈是一种逻辑上的，出栈把栈顶指针向后移动一位，入栈则是把栈顶指针向前移动一位
思考
思考？LeetCode20,有效的括号
LeetCode #20 有效的括号
结论1：在任意⼀个位置上，左括号数量>=右括号数量
结论2：在最后⼀个位置上，左括号数量=右括号数量
根据上述两个结论，程序中只需要记录左括号和右括号的数量即可。
理解：匹配到左括号lnum+1, 匹配到右括号rnum+1,要满足以上结论=>lnum >= rnum
优化：差值-》不用两个变量，用一个差值表示且查找>=0(左括号+1，右括号-1)
==》我们可以把遇到左括号+1抽象成一件事情的发生（进栈），遇到右括号-1相当于一件事情的结束(出栈)===》括号关系和函数执行上下文栈类似
思考：
⼀对括号可以等价为⼀个完整的事件。
左括号可以看作事件的开始（进栈）、右括号可以看作事件的结束（出栈）。
⽽括号序列可以看作事件与事件之间的完全包含关系。
栈可以处理具有完全包含关系的问题。
为什么栈可以处理递归问题，递归是一种完全包含关系-》(执行上下文栈)
栈的典型应用场景
- 场景一、操作系统中的线程栈（线程池中的线程就是用栈存储的）
- 场景二、表达式求值（用栈来求值和用递归本质上没有差别-》递归用的是系统栈）
经典面试题
栈的基本操作
LeetCode #面试题 03.04化栈为队
利⽤两个栈来实现，⼀个输⼊栈、⼀个输出栈。
输⼊栈⽤于读⼊数据。当需要输出元素时，若输出栈为空，则将输⼊栈的所有元素推送到输出栈，然后取栈顶元素；若输出栈⾮空，则输出栈顶即可。
输出栈的作⽤是对已经被反转的序列进⾏⼆次反转。对此感到困惑的同学可以画图模拟⼀下。
LeetCode #682 棒球⽐赛
用栈思想模拟本题，整数x就是入栈操作，C操作相当于出栈，D操作相当于将栈顶元素*2入栈
+操作：将栈顶元素出栈并记录下来，然后将栈顶元素和弹出的值相加作为新元素，把弹出的值再入栈，然后把新元素入栈
遍历完成后计算栈中元素的和即可。
LeetCode #844 ⽐较含退格的字符串
1、我们可以利用栈，将两个字符串处理成没有退格的字符串，然后进行比较即可
2、我们创建一个栈，用来处理我们的两个字符串
3、首先处理我们的第一个字符串，我们将字符串的每个元素压入栈。如果遇到#我们就弹出一个元素。
当我们遍历完整个字符串的时候，我们就将栈中的字符输出组成字符串。
4、然后我们按相同的步骤处理第二个字符串
5、最后我们比较两个字符串是否相等
LeetCode #946 验证栈序列
被出栈的元素只有两种可能：即将⼊栈的元素 和 当前栈顶的元素。
只需要关注出栈序列，分类讨论后模拟即可。
栈结构的扩展应用
LeetCode #20 有效的括号
结论1：在任意⼀个位置上，左括号数量 右括号数量
结论2：在最后⼀个位置上，左括号数量 右括号数量
根据上述两个结论，程序中只需要记录左括号和右括号的数量即可。
思考：
⼀对括号可以等价为⼀个完整的事件。
左括号可以看作事件的开始（进栈）、右括号可以看作事件的结束（出栈）。
⽽括号序列可以看作事件与事件之间的完全包含关系。
栈可以处理具有完全包含关系的问题。
为什么栈可以处理递归问题，递归是一种完全包含关系-》(执行上下文栈)
栈如果为空的话，栈顶指针指向-1
理解：匹配到左括号lnum+1, 匹配到右括号rnum+1,要满足以上结论=>lnum >= rnum
优化：差值-》不用两个变量，用一个差值表示且查找>=0(左括号+1，右括号-1)
==》我们可以把遇到左括号+1抽象成一件事情的发生（进栈），遇到右括号-1相当于一件事情的结束(出栈)===》括号关系和函数执行上下文栈类似
LeetCode #1021删除最外层的括号
左括号和右括号差值为0时，代表这一串括号序列是独立的，可以被单独分解出来。
相当于用栈模拟，我们可以步骤差值看成栈操作，比如’(()())’ => 匹配到第一个(时,cnt = 1,相当于入栈，第二个(cnt=2,接着入栈
第三个为)时，相当于出栈，cnt = 1, 第四个(,第五个)相当于入栈出栈，第六个)时相当于出栈cnt = 0
LeetCode #1249移除无效的括号
可以被匹配的括号都是有效的，而其他的括号都需要被删除
LeetCode #145二叉树的后序遍历
1、递归
2、非递归(迭代)
LeetCode #331验证二叉树的前序序列化
我们可以利用栈的特性来完成这件事，前序遍历的顺序是中前后。我们可以在栈中记录一个数字，
代表当前节点可能有几个节点。首先我们存入一个1代表根节点。
然后我们开始遍历字符串，如果我们遇到”#”就代表这个节点是空节点，我们就需要将栈顶的元素进行减一，
代表我们已经找到了一个子节点。如果我们遇到的是数字，就代表当前节点不为空，我们就需要将栈顶的数字进行减一，代表我们已经
找到了一个子节点，并且一个不为空的节点可能有两个子节点，所以我们要在栈中再压入一个2.
我们需要判断每次遍历栈顶元素是否为0，如果为0代表这个中间节点的两个子节点都找到了，当前节点的遍历完成。要进行出栈操作。
到最后我们就判断栈中是否还有元素即可，如果还有说明序列错误。
LeetCode #227基本计算器II
思路1：找到式⼦中优先级最低的运算符，然后递归分治运算两侧的⼦式即可。
思路2：使⽤操作数栈和操作符栈辅助计算，当操作符栈遇到更低优先级的操作符 时，需要将之前更⾼级别的操作符对应的结果计算出来。
对于有括号的情况，左括号相当于提⾼了内部全部运算符的优先级，当遇到右括号 的时候需要将匹配的括号间的内容全部计算出来。 可以通过加⼀个特殊操作符的处理技巧，来额外处理结尾的数字。
智力发散题
LeetCode #636函数的独占时间
本质就是⼀道模拟题，画⼀个线段图能显著地辅助理解。任务开始时进栈，上⼀个 任务暂停执⾏；任务完成时出栈，恢复上⼀个任务的执⾏。
LeetCode #1124表现良好的最长时间段