一、C++&Python实现
C++
栈
std::stack<Template T>，常用API：push(),pop(),top(),empty()
堆
- 用priority_queue：常用API和stack一样
priority_queue<int> lo; // max heap
priority_queue<int, vector<int>, greater<int>> hi; // min heap
- std::make_heap(nums.begin(), nums.end())，以及std::pop_heap(),vector::pop_back()接口
Python
栈
用list即可
堆
- MinHeap（默认）：heapq.heapify()，heapq.heappush()，heapq.heappop()等接口
- MaxHeap：可以直接构造heapq._heapify_max()，但是我觉得把元素全部取负，然后用最小堆即可，因为最小堆的接口更多（例如heapq最大堆，似乎不能push新元素，而最小堆有heappush接口）
二、经典题目
1. 使用Queue实现Stack
1个Queue，push的时候，将新元素压入，更新记录的top元素，并将Queue中元素pop()和push()循环n-1次；pop和push类似，循环n-1次，并更新top记录
- 时间复杂度
- push：\(O(n)\)
- pop：\(O(n)\)
- top：\(O(1)\)
- empty：\(O(1)\)
- 空间复杂度：O(n)
2. 使用Stack实现Queue
2个Stack，因为Stack是FILO，Queue是FIFO，因此Stack压入压出2次即可实现FIFO，如图
- 时间复杂度
- push：\(O(1)\)
- pop：\(O(n)\)
- top：\(O(n)\)
- empty：\(O(1)\)
- 空间复杂度：O(n)
3. 包含min的栈
需要2个栈，一个记录原数据，一个记录最小值，但是2个stack长度相同，具体如下
- min的时间复杂度：\(O(1)\)
4. 合法出栈序列
题目描述
给2个数字序列，一个入栈序列，一个出栈序列，判断出栈序列是否合法
算法设计
用1个stack，按照入栈序列push元素，同时循环出栈序列，如果top元素和出栈序列当前元素相等，则pop，并继续循环出栈序列
- 如果push完入栈序列，但出栈序列没有遍历结束，返回false
- 如果出栈序列遍历结束，但stack不为empty，返回false
- 否则返回true
图中思路和上述是一致的，只不过添加了1个Queue，实际可以省略，遍历即可
5. 数组中第K大的数
用最小堆，保持堆大小为k，最后返回堆顶即可
- 时间复杂度：\(O(nlogk)\)
- 空间复杂度：\(O(k)\)
6. 寻找中位数
动态维护一个最大堆和最小堆，保证两个堆大小相差为1即可
- 时间复杂度：\(O(logn)\)
- 空间复杂度：\(O(n)\)
更多
个人更多算法总结在Github
