数据结构与算法 - 栈&队列
1. 用栈实现队列
leetCode 232. 用栈实现队列
题目链接：https://leetcode-cn.com/problems/implement-queue-using-stacks/
- 方法一：双栈 - 数据栈和缓存栈
思路：队列为 FIFO，而栈为 LIFO，用栈实现队列，需要将最后一个入栈的数据放到栈底，可通过引入缓存栈实现。
构建两个栈：栈 s1 作为数据栈，栈 s2 作为缓存栈；当数据入队时，将 s1 中所有数据缓存到 s2 中，然后将新元素压入 s2 ，最后再将 s2 中所有元素再压回 s1 中，这样操作之后，其他的队列操作（出队/判空/取队首元素）只需要操作 s1 即可。
- 方法二：双栈 - 入队栈和出队栈
思路: 栈 s1 作为入队栈，栈 s2 作为出队栈, 当数据入队时，将数据直接插入到 s1 中，当数据出队或获取队首元素时，需要从 s2 中取数据，如果取数据时 s2 为空，此时需要将 s1 中的所有数据压入到 s2 中，当 s1 和 s2 均为空栈时，证明该队列为空。
相对于方法一，该方法减少了数据在两个栈之间轮转, 将入栈的时间复杂度从O(n)降到了O(1)。
2. 用队列实现栈
leetCode 225. 用队列实现栈
题目链接：https://leetcode-cn.com/problems/implement-stack-using-queues/
- 方法一：双队列 - 数据队列和缓存队列
思路：队列为 FIFO，而栈为 LIFO，用队列实现栈，需要将最后一个入队列的数据放到队列头，可通过引入缓存队列实现。
队列 q1 作为数据队列，队列 q2 作为缓存队列，当数据入队时，将 q1 中所有数据缓存到 q2 中，然后将新元素压入 q1 ，最后再将 q2 中所有元素再压回 q1 中，这样操作之后，其他的队列操作（出队/判空/取队首元素）只需要操作 q1 即可。
- 方法二：单队列
思路: 要实现将最后一个入队列的数据放到队列头，也可以不使用缓存队列，只需要将新压入队列的数据之前的数据循环弹出再压回队列内即可。
相对于方法一，该方法只需要使用一个队列, 可以降低空间占用（空间复杂度没有降低）。
3. 最小栈
leetCode 155. 最小栈
题目链接：https://leetcode-cn.com/problems/min-stack/
- 方法一：辅助栈法
思路：一个栈保存数据，另一个栈保存最小值，两个栈同时 push 和 pop。
- 方法二：单栈 + 最小值法
思路：仅使用一个栈，栈中元素最小值使用变量保存。如果即将入栈的数据小于或等于最小值，则先把最小值压栈，再压入数据；出栈的时候如果出栈的数据与最小值相等，需要再弹出栈顶元素赋值给最小值。
4. 单调栈的应用
leetCode 42. 接雨水
题目链接：https://leetcode-cn.com/problems/trapping-rain-water/
- 方法一：暴力法及其优化
思路：对于每一个柱子，遍历其左侧的最高柱子和右侧的最高柱子，则可求得当前柱子的水位值，将所有位置的水位值进行累加即可。
改进：双指针法 通过双指针记录左右两侧的最高柱子，从而减少遍历。
- 方法二：单调栈法 - 单调递减栈
思路：记录一个柱子高度单调下降的栈（栈中保存的柱子的位置），如果即将入栈的柱子高度上升，则代表栈顶元素的位置可以保存雨水：
# 假设栈顶元素为 top , 将 top 弹出后的新栈顶元素为 subtop , 即将入栈的元素为 index
rainblock = (min(height[index]， height[subtop]) - height[top]) * (index - subtop - 1)过程中将每一个 rainblock 累加即可。
leetCode 84.柱状图中最大的矩形
题目链接：https://leetcode-cn.com/problems/largest-rectangle-in-histogram/
- 方法一：暴力法及其优化
思路：对于每一个柱子，遍历寻找其左右两侧第一个低于当前柱子高度的柱子，则可求得完全覆盖当前柱子的矩形面积，将所有位置进行遍历，找到最大的矩形面积即可。
提交 Leetcode 测试，发现该方法会超时，原因是测试用例中有上万个高度为1的柱子的用例，在执行这个用例时，每个柱子都需要向前向后寻找左右两侧第一个低于当前柱子高度的柱子，造成时间的浪费，所以我们需要改进方案减少遍历次数。
改进：通过哈希表记录当前高度遍历到的最右侧柱子，如果当前柱子高度对应的哈希表中最右柱子在当前柱子右侧，则说明该高度的矩形已计算过，从而减少遍历。
- 方法二：单调栈法 - 单调递增栈
思路：记录一个柱子高度单调上升的栈（栈中保存的柱子的位置），如果即将入栈的柱子高度下降，则代表找到了栈顶元素的右侧边界，此时将栈顶元素弹出，新栈顶元素即为老栈顶元素高度的左侧边界，从而可以计算出栈顶元素对应矩形的面积:
# 假设栈顶元素为 top , 将 top 弹出后的新栈顶元素为 subtop , 即将入栈的元素为 index
Area = height[top] * (index - subtop - 1);过程中找出最大的 Area 值即可（记得最后要将栈弹空）。
5. 判断栈的 push 和 pop 序列是否一致
//TODO