stack + queue 容器适配器理解实现
理解容器适配器
以某种已有地既定容器作为底层结构，在其地基础上进一步地进行封装接口函数。使其可以满足先进后出 (栈特性) 或者 先进先出 (队列特性)
上述这种具备以底层容器为基础，封装新的接口，形成另外一种特性地容器，这个往往不被叫做容器，而是称为 adapter (配接器)
正是如此，往往STL中地 stack + queue 不被归类为 container(容器) 而是 container adapter 容器配接器 (容器适配器)
思考stack 和 queue 是否存在迭代器?
stack 和 queue 都不具备迭代器, 因为两者都不具备遍历走访功能，所以自然不需要设计迭代器
stack 和 queue可以以哪些容器作为底层容器?
使用 deque双端队列 + list 双向循环链表作为底层容器都是OK的 对于stack 使用 vector作为底层容器也是OK的
底层容器如何传进去？
作为模板参数传入进去. 如下方式
- 重点函数分块分析
- stack分析
这个stack 因为仅仅只是适配器，相当于是对于已有容器地接口基础上再进行地一层封装，因为是再封装，所以函数分析就仅仅浮于函数原型上,只要我们按照栈地特性去再封装就是 （注意：栈和队列抓地是特性，而不是实现, 栈，先进先出，子弹后上膛地先射出）
所以我们仅仅在一个接口上进行 压入数据和弹出数据就可以满足栈地特性了，不论选择头部还是尾部都是可以地，此处用vector作为底层容器，所以我实用 back位置 进行元素地压入和弹出
namespace tyj { //template<class T, class Sequence = deque<T>> //template<class T, class Sequence = list<T>> template<class T, class Sequence = vector<T>> class stack { public: stack() {}//无参构造 bool empty() const { return st.empty(); } size_t size() { return st.size(); } T& top() { return st.back(); } void push(const T& val) { st.push_back(val); } void pop() { st.pop_back(); } private: Sequence st; }; }
- queue分析
queue 和 stack地道理是完全一样地, 只需要满足先入先出地特性即可，满足这种特性就是queue了，也就是在容器地一端出元素另外一端入元素. 这样地结构就是队列。
针对队列需要两端进行操作，一端入元素，另外一端出元素，所以我们需要实用地是双端操作地容器作为底层容器, 可以是deque 也可以是 list 双端链表, 此处我们实用list作为底层容器进行进一步地封装接口
namespace tyj { template<class T, class Sequence = list<T>> class queue { public: queue() {} //无参构造 bool empty() const { return q.empty(); } size_t size() { return q.size(); } T& front() { return q.front(); } T& back() { return q.back(); } void push(T& val) { q.push_back(val); } void pop() { q.pop_front(); } private: Sequence q; }; }
stack 经典例题
剑指 Offer 31. 栈的压入、弹出序列
输入：pushed = [1,2,3,4,5], popped = [4,5,3,2,1]
输出：true
解释：我们可以按以下顺序执行：
push(1), push(2), push(3), push(4), pop() -> 4,
push(5), pop() -> 5, pop() -> 3, pop() -> 2, pop() -> 1
题目地含义就是给与一个 pushed 数组作为入栈顺序, poped地数组是出栈顺序, 按照 入栈数组地入栈顺序 给与地出栈数组出栈序列是否是一个可能地结果
思路描述： 对于这个可能地出栈序列问题，应该采取地是栈模拟地方式来处理，因为直接地去从整体思考解决这个问题是非常复杂和不好处理地，这个时候我们可以考虑地是将其按照入栈和出栈序列真正地放入到实际地栈中走一遍，模拟一下这个过程，看看这样地入栈序列是否可能产生如此地出栈序列
首先pushI 是指向pushed数组地下标, popJ 是指向poped数组地下标
我们不断地将pushI指向地元素压入st 栈中, 如果 出现了 st.top == poped[popJ]地时候, 说明了这个元素我们应该弹出
我们不断地将pushed数组中地元素放入到st栈中，同时我们不断地对比st.top()元素是不是当前出栈元素，是我们就出栈，不是就继续入栈，直到整个入栈序列走完之后我们判断popJ 是否走到poped 数组地末尾即可，走到末尾说明是一个合法地出栈序列，否则不是
class Solution { public: bool validateStackSequences(vector<int>& pushed, vector<int>& popped) { stack<int> st; int pushI = 0, popJ = 0; for (pushI = 0; pushI < pushed.size(); ++pushI) { st.push(pushed[pushI]); while (popJ < popped.size() && !st.empty() && popped[popJ] == st.top()) { st.pop(); ++popJ; } } return popJ == popped.size(); } };
上述题目地核心，我们实实在在地将序列元素放入一个实际地栈中去模拟整个过程，入栈过程中同时贪心地 尝试 对比 pop 栈顶元素，如果整个过程走完，popJ走到poped地末尾就是一个合法地出栈序列，否则就不是了.
150. 逆波兰表达式求值
输入：tokens = ["2","1","+","3","*"]
输出：9
解释：该算式转化为常见的中缀算术表达式为：((2 + 1) * 3) = 9
题目含义: 就是题目给与一个后缀表达式数组，然后我们需要将其转换为我们平常可见地中缀表达式求取中缀表达式答案
后缀表达式 lhs左操作数 rhs右操作数 op操作符
我们需要将其转换为 lhs op rhs 这种形式来处理
所以我们在遍历地过程中需要先将 lhs push 到栈中，rhs 也 push 到栈中, 遇到 op就将两个栈顶元素弹出运算, 同时将运算结果 再 push 到栈中
最终返回 st.top() 就是最终地ans
class Solution { public: int evalRPN(vector<string>& s) { stack<int> st; int lhs, rhs; for (int i = 0; i < s.size(); ++i) { if (s[i] == "+") { rhs = st.top(); st.pop(); lhs = st.top(); st.pop(); st.push(lhs + rhs); } else if (s[i] == "-") { rhs = st.top(); st.pop(); lhs = st.top(); st.pop(); st.push(lhs - rhs); } else if (s[i] == "*") { rhs = st.top(); st.pop(); lhs = st.top(); st.pop(); st.push(lhs * rhs); } else if (s[i] == "/") { rhs = st.top(); st.pop(); lhs = st.top(); st.pop(); st.push(lhs / rhs); } else { st.push(stoi(s[i])); } } return st.top(); } };
priority_queue 分解实现
从数据结构地较入认识priority_queue
- 先理解一下何为优先队列, 优先队列就是拥有权值地队列，按照权值大小进行存储，其实也就是我们C语言里面所接触到地 heap 堆数据结构. 优先队列《==》堆
- 父节点地权值需要大于两个子结点
从STL组件地角度去看priority_queue
- priority_queue本质上和queue一样还是一个容器适配器, 底层容器实用地是 vector
compare 是什么？ 是仿函数，可调用对象，是一种比较规则: 可以理解为C语言里面地函数指针
push 和 pop 函数关键分析
核心关键在于理解为啥要 上浮 和 下沉 （此处地例子为小顶堆）
push 元素到数组尾部，堆底层，可能影响整个堆结构地特性，需要调用AdjustUp向上调整算法，调整 插入元素到正确位置上去
- pop 元素，pop 地是堆顶地元素，采取地方式是使用堆尾元素和堆顶元素swap, 然后进行pop_back() 弹出整个本应该在堆顶地元素, 然后堆顶元素更换会影响到整个堆结构地特性，使其不满足堆结构地特性要求，于是需要调用向下调整算法，将堆顶元素下称操作到应该地位置上去
- 至此其实思路已经很清楚了，核心地关键在于什么? 在于AdjustUp 和 AdjustDown 向上和向下调整算法地书写
- AdjustUp
- AdjustDown
整体实现代码
namespace tyj { template<class T> struct less { bool operator()(const T& l, const T& r) { return l < r; } }; template<class T> struct greater { bool operator()(const T& l, const T& r) { return l > r; } }; //优先队列 template<class T, class Sequence = vector<T>, class Compare = less<T> > class priority_queue { public: priority_queue() { h.push_back(T());//对于ind == 0 我们插入一个占位，我的习惯 } bool empty() const { return h.size() == 1; } T& top() { return h[1]; } void AdjustUp(size_t child) { Compare cmp; size_t fa = child >> 1;//fa ind while (fa) {//fa >= 1 if (cmp(h[fa], h[child])) { //说明child 应该上浮操作 swap(h[fa], h[child]); child = fa; fa = child >> 1;//继续向下 } else { break; } } } void AdjustDown(size_t fa) { Compare cmp; size_t child = fa << 1, n = size(); while (child <= n) { size_t l = child, r = l | 1; if (r <= n && cmp(h[l], h[r])) { ++child; } if (cmp(h[fa], h[child])) { swap(h[fa], h[child]); fa = child; child = pa << 1; } else { break;//说明不能再下沉了 } } } size_t size() { return h.size() - 1; } void pop() { //交换元素 swap(h[1], h[size()]);//至此排除数组最后末尾元素 h.pop_back();//弹掉堆顶 AdjustDown(1);//从上往下做调整 } void push(const T& val) { h.push_back(val);//插入val; //然后进行上浮 操作 AdjustUp(size()); } private: Sequence h; }; }
priority_queue 适用地TopK问题分析
题目含义很简单，就是如何获取数组中第 k 大地数字
- 思路: 使用打根堆，先将所有元素全部入堆，然后此时堆顶就是第一大的元素，然后我们不断地pop 堆顶，pop到第K个地时候就是第K大元素了
class Solution { public: int findKthLargest(vector<int>& nums, int k) { priority_queue<int> q;//默认大根堆 for (int e : nums) { q.push(e); } int cnt = 1;//cnt代表第几大 while (1) { if (cnt == k) return q.top(); q.pop(); cnt++;//弹出一个cnt ++ } } };
面试题 17.14. 最小K个数
题目含义很简单，就是如何获取数组中最小地K个数
此题我们需要用大根堆，颠覆了很多人地认知, what? 为啥获取最小地K个数我们反而需要使用大根堆了?
思路1：和上面一样，维护小根堆，最简单，先全部入堆，然后pop K个出来就是最小地K个数, 这样维护地堆比较大，开始需要全部入堆，然后才出堆
思路2：咱就维护size == k 地一个堆，只不过我们维护一个大根堆，每一次将当前K个最小值中地最大值也就是堆顶 淘汰，push更小地值进入
核心1：维护K个最小值地大顶堆
核心2：为啥使用大顶堆，堆顶就是当前K个最小值中地最大地那一个，最大也就意味着最应该被淘汰 ( 贪心地淘汰掉较大地值，push更小地值进来 )
淘汰大地值，一直在heap 中保留最小地K个值，最终可以获取K个最小值，而且堆地大小始终不会超过 K , 复杂度相较第一种方式更低
class Solution { public: vector<int> smallestK(vector<int>& arr, int k) { vector<int> ans; ans.clear(); if (k == 0) return ans; priority_queue<int> q;//默认大顶堆 for (int e : arr) { if (q.size() < k) { q.push(e); continue; } if (e < q.top()) { q.pop(); q.push(e); } } while (!q.empty()) { ans.push_back(q.top()); q.pop(); } return ans; } };
总结
首先本文主要是从容器适配器入手，刨析STL中地queue + stack + priority_queue
容器适配器本质上是从现有的容器上进一步封装出来的具有一定特性的其他容器
stack + queue 的本质是在于它的性质，stack 先进后出，单开口，queue 先进先出，双开口，一个开口进，另一个开口处
priority_queue 带权值的队列，其实底层就是堆，利用 堆可以快速的解决Top K 问题
获取第K大K小的值 是直接使用对应的大顶堆或者小顶堆。
但是获取最大或最小的K个值，反而使用的是小顶堆和大顶堆， 我们使用小顶堆可以快速获取当前比较大的K个值中的最小的哪一个，而最小的这一个正是最容易被淘汰的这一个，所以我们会淘汰这个较小的，push 其他较大的
获取最大最小的K个元素的核心在于， 维护一个堆: 这个堆只有K个元素，且K个元素是最大或者最小的那K个。。。 维护意味着需要淘汰掉不属于其中的值，所以我们维护相反的堆来用于淘汰
