栈

括号类问题

20. 有效的括号（easy）

遍历字符串，每次与栈顶括号进行匹配，匹配成功栈顶弹出，否则继续压入栈。

32. 最长有效括号（hard）

难点在于不知道如何得到有效括号的长度，以及如何更新长度。

解法：下标入栈法，每次括号匹配成功，都用当前下标减去栈顶元素的下标得到当前有效括号的长度，解决了长度更新问题。

设计类问题

155. 最小栈（easy）

在普通栈的基础上，实现常数时间检索到最小元素。

解法：增加一个辅助栈用于存储当前栈中的最小值。

255. 用队列实现栈（easy）

队列特性：先进先出；栈特性：后进先出

两个队列法：保存栈顶元素。

一个队列法：每次入队新元素时，把队列顺序反转过来。

单调栈问题

42. 接雨水（hard）

思路：当前柱子的接水量取决于左右两侧最高柱子。

解法：遍历两次序列，保存当前柱子的左侧最大值以及右侧最大值。再次遍历序列，得到最终接水量。

单调栈解法思路可见：https://www.jianshu.com/p/cd9b57d79b77

739. 每日温度（medium）

解法：下标入栈+维护一个单调递减栈

遍历序列，若当前元素值小于栈顶元素所对应的值，则当前元素的下标入栈，否则弹出栈顶元素并计算当前元素与栈顶元素下标之差。

84. 柱状图中矩形最大面积（hard）

解法：下标入栈+维护一个单调递增栈

栈与递归

1、二叉树的非递归遍历

2、同理，图的深度优先遍历也可借助栈来实现

队列

设计类问题

225. 用两个栈实现队列

类似于用队列实现栈

队列与广度优先

图问题的广度优先可借助队列实现，二叉树层序遍历也是

双端队列

239. 滑动窗口最大值（hard）

优先队列

347. 前k个高频元素（medium）

详见：https://www.jianshu.com/p/cd9b57d79b77