很久没做题更新博客了，最近在做项目与复习八股，每次被面试横向后都要摆烂一段时间
栈与队列
1.用栈实现队列
力扣题目链接(opens new window)
使用栈实现队列的下列操作：
push(x) -- 将一个元素放入队列的尾部。
pop() -- 从队列首部移除元素。
peek() -- 返回队列首部的元素。
empty() -- 返回队列是否为空。
class MyQueue { public: stack<int> stIn; stack<int> stOut; MyQueue() { } void push(int x) {//放在队尾，即放在in栈的栈顶 stIn.push(x); } int pop() {//循环取出，out栈为空时，循环取出in栈放入out栈中，取出out栈栈顶元素 if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.top()); stIn.pop(); } } int result=stOut.top(); stOut.pop(); return result; } int peek() { if(stOut.empty()){ while(!stIn.empty()){ stOut.push(stIn.top()); stIn.pop(); } } int result=stOut.top(); return result; } bool empty() { return stIn.empty()&&stOut.empty(); } };这里使用的是两个栈来模拟一个队列的方法，使用一个in栈一个out栈来代替队列的入口与出口，
入栈操作就只需要压入in栈就可以了
出栈时，若out栈为空，就要将in栈内的元素循环压入到out栈之中，之后弹出out栈的栈顶就可以了，out栈不为空，就直接弹出out栈栈顶元素。
获得栈顶元素，入出栈是一样的操作，只是不需要弹出，获得返回就可以了
判空，两个栈都为空即为队列为空。
2.用队列实现栈
力扣题目链接(opens new window)
使用队列实现栈的下列操作：
- push(x) -- 元素 x 入栈
- pop() -- 移除栈顶元素
- top() -- 获取栈顶元素
- empty() -- 返回栈是否为空
class MyStack { public: queue<int> q; MyStack() { } void push(int x) {//直接放入队尾 q.push(x); } int pop() {//弹出栈顶元素，即队尾元素 int size=q.size(); size--; while(size--){//将队尾元素移动到队首 q.push(q.front()); q.pop(); } int result=q.front(); q.pop(); return result; } int top() { int size=q.size(); size--; while(size--){ q.push(q.front()); q.pop(); } int result=q.front(); q.push(result);//恢复原来结构 q.pop(); return result; } bool empty() { return q.empty(); } };这里使用的是一个队列来模拟栈的操作
入栈，直接放入队列就可以了。
出栈，计算出队列的长度，循环将队首元素放入队尾就可以，次数为长度-1，然后获得队首元素并弹出。
获得栈顶元素，与出栈类似，不过不弹出队首元素，需要再取出放入队尾，恢复原来的结构。
判空，直接返回队列是否为空。
3.有效的括号
力扣题目链接(opens new window)
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 注意空字符串可被认为是有效字符串。
class Solution { public: stack<char> st; bool isValid(string s) { for(int i=0;i<s.size();i++){ if(s[i]=='('){ st.push(')'); }else if(s[i]=='{'){ st.push('}'); }else if(s[i]=='['){ st.push(']'); }else if(st.empty()||s[i]!=st.top()){//右括号多了或者括号不匹配 return false; }else{ st.pop(); } } return st.empty();//栈为空说明全部匹配有效，不为空说明左括号多了 } };这里使用栈来进行解决，遍历字符串，遇到左边括号就在栈内放入一个对应的右括号，反之，三种情况
1.括号不匹配，即此时遇到的右括号与栈顶不匹配，说明左右括号不匹配
2.栈为空，说明右括号更多，左括号不够的情况
3.说明括号可以匹配的上，弹出栈内元素
最后遍历结束后，若栈内不为空，说明左括号多了，不匹配，为空说明刚好匹配成功。
4.删除字符串中的所有相邻重复项
力扣题目链接(opens new window)
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
class Solution { public: stack<char> st; string removeDuplicates(string s) { for(int i=0;i<s.size();i++){ if(st.empty()||s[i]!=st.top()){ st.push(s[i]); }else{ st.pop(); } } string res=""; while(!st.empty()){ res+=st.top(); st.pop(); } reverse(res.begin(),res.end()); return res; } };这里也是使用栈来解决，遍历字符串，栈为空或者栈顶与字符不相等的时候，就加入到栈内，相反，栈不为空且栈顶元素与字符相等的时候，说明相邻重复，就要弹出栈顶元素。
遍历结束后，循环取出栈顶字符，得到的字符串反转就可以得到删除后的字符串。
5.逆波兰表达式求值
力扣题目链接(opens new window)
根据 逆波兰表示法，求表达式的值。
有效的运算符包括 + , - , * , / 。每个运算对象可以是整数，也可以是另一个逆波兰表达式。
说明：
整数除法只保留整数部分。 给定逆波兰表达式总是有效的。换句话说，表达式总会得出有效数值且不存在除数为 0 的情况。
class Solution { public: int evalRPN(vector<string>& tokens) { stack<int> st; for(int i=0;i<tokens.size();i++){ if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/"){ int num1=st.top(); st.pop(); int num2=st.top(); st.pop(); if(tokens[i]=="+") st.push(num2+num1); if(tokens[i]=="-") st.push(num2-num1); if(tokens[i]=="*") st.push(num2*num1); if(tokens[i]=="/") st.push(num2/num1); }else{ st.push(stoi(tokens[i])); } } int res=st.top(); return res; } };这里也是用栈来解决，遍历字符串数组，将字符串转换成数字stoi(tokens[i])存入栈内，遇到运算符就进行计算，将栈顶的两个数字进行运算符计算，得到的值再加入到栈中，遍历结束后，栈内剩余的数就是最后结果。
6.滑动窗口最大值
力扣题目链接(opens new window)
给定一个数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回滑动窗口中的最大值。
class Solution { private: class Myque{//使用双端队列自定义实现一个单调队列，出口按照由大到小 public: deque<int> que; void pop(int value){//弹出元素 if(!que.empty()&&value==que.front()){//不为空并且与出口值相等时才弹出 que.pop_front();//弹出出口元素，即最大值 } } void push(int value){//压入新元素 while(!que.empty()&&value>que.back()){//从入口处开始比较，将更小的弹出 que.pop_back(); } que.push_back(value);//队尾入口处放入新元素 } int front(){ return que.front();//返回出口元素，即最大值 } }; public: vector<int> maxSlidingWindow(vector<int>& nums, int k) { Myque que; vector<int> res; for(int i=0;i<k;i++){ que.push(nums[i]); } res.push_back(que.front()); for(int i=k;i<nums.size();i++){ que.pop(nums[i-k]);//将窗口内第一个移除 que.push(nums[i]);//放入新元素 res.push_back(que.front());//返回最大值 } return res; } };这里每次移动窗口的时候就要获得窗口内的最大值，如果直接对窗口内元素进行排序的话，复杂度太高，这里使用单调队列来解决
即加入元素的时候，比入口的元素值小，就直接放在队尾，如果比入口元素值大，则直接删除队尾中小于这个元素的值，直到比入口元素小或者队列为空，这样就保证了队列的队首为最大值，后面的元素也是按照由大到小排列的。
使用双端队列deque实现单调队列这个数据结构
出队操作，即移动窗口把最大值移出去了，就弹出队首元素，否则就不变。
入队操作，即移动窗口时加入新元素，新元素比队尾值大就移除队尾的值，直到队尾元素比新元素大，并放入新元素到队尾。
获取队首，直接返回双端队列的首部元素，即为最大值。
具体做题，遍历k个元素，都加入到单调队列中，获得此时最大值加入到返回数组中，之后继续遍历之后的元素，先移除窗口内第一个元素，再新元素加入到单调队列中，最后将最大值即队首元素加入到返回数组中。
7.前 K 个高频元素
力扣题目链接(opens new window)
给定一个非空的整数数组，返回其中出现频率前 k 高的元素。
示例 1:
- 输入: nums = [1,1,1,2,2,3], k = 2
- 输出: [1,2]
示例 2:
- 输入: nums = [1], k = 1
- 输出: [1]
提示：
- 你可以假设给定的 k 总是合理的，且 1 ≤ k ≤ 数组中不相同的元素的个数。
- 你的算法的时间复杂度必须优于 $O(n \log n)$ , n 是数组的大小。
- 题目数据保证答案唯一，换句话说，数组中前 k 个高频元素的集合是唯一的。
- 你可以按任意顺序返回答案。
class Solution { public: vector<int> topKFrequent(vector<int>& nums, int k) { vector<int> res(k); unordered_map<int,int> map; for(int i=0;i<nums.size();i++){ map[nums[i]]++; } //使用小顶堆，这样队列中只需要存入k个元素，大顶堆就要全部存入 priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>> que;//小顶堆 for(auto& it:map){ que.push({it.second,it.first});//first为频率，second为元素 if(que.size()>k){//只维护前k个 que.pop(); } } for(int i=k-1;i>=0;i--){//逆序存入 res[i]=que.top().second; que.pop(); } return res; } };这里因为要求前k个高频元素，实际上就是先对数组中元素的出现次数进行记录，之后排序，求出前k个元素，这里其实就是求第k元素，可以考虑使用堆来实现
因为要第k大，就要考虑使用小顶堆，这样堆中只需要存放k个元素，空间消耗更小
如果使用大顶堆，堆中就要存放全部的元素，空间消耗高。
先使用unordered_map来存入元素以及出现次数，再构建小顶堆，最后再存入。
priority_queue<存放类型，存放容器，比较方法>
存放类型为pair<int,int> 使用的比较方式为greater<pair<int,int>>，容器是vector<pair<int,int>>
遍历map，元素存入堆中，由于greater默认比较的是第一个元素，所以这里存放的是{it.second,it.first}，注意只维护k个元素，超出就弹出，最后剩下的就是前k大的元素。由小到大排列。
之后创建大小为k的数组，逆序存入堆顶中元素que.top().second。
