我们需要时刻理解栈和队列这两种数据结构的思想。
栈：先进后出，用于保存现场。
队列：先进先出，用于表示优先级。
不管是栈还是队列，在操作的时候需要时刻记住判空，否则top()和front()函数会报错。
1 用栈实现队列
2 用队列实现栈
请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。
实现 MyStack 类：
void push(int x)将元素 x 压入栈顶。int pop()移除并返回栈顶元素。int top()返回栈顶元素。boolean empty()如果栈是空的，返回true；否则，返回false。
解题思路：
- 1 数据结构：一个队列
- 2 输入：每输入一个数，就将该数前面的全部元素移到末尾（pop最前一个数，push到末尾）。
- 3 输出：输出最前方的数。
3 有效的括号
给定一个只包括 '('，')'，'{'，'}'，'['，']' 的字符串 s ，判断字符串是否有效。
有效字符串需满足：
- 左括号必须用相同类型的右括号闭合。
- 左括号必须以正确的顺序闭合。
- 每个右括号都有一个对应的相同类型的左括号。
解题思路：
- 1 数据结构：栈
- 2 输入：
- 遇到”({[“，就push进栈
- 遇到”)}]”，如果栈为空，则return fasle
- 遇到”)”就判断栈顶部元素是否为”(“，是则pop()，否则return false
- 遇到”}”就判断栈顶部元素是否为”{“，是则pop()，否则return false
- 遇到”]”就判断栈顶部元素是否为”[“，是则pop()，否则return false
代码如下：
class Solution {
public:
bool isValid(string s) {
stack st;
for(auto c:s){
if (c == '(' || c == '{' || c == '[') st.push(c);
else{
if (st.empty()) return false;
if (c == ')' && st.top() != '(') return false;
else if (c == '}' && st.top() != '{') return false;
else if (c == ']' && st.top() != '[') return false;
st.pop();
}
}
return st.empty();
}
};4 删除字符串中的所有相邻重复项
给出由小写字母组成的字符串 S，重复项删除操作会选择两个相邻且相同的字母，并删除它们。
在 S 上反复执行重复项删除操作，直到无法继续删除。
在完成所有重复项删除操作后返回最终的字符串。答案保证唯一。
解题思路：
- 1 数据结构：使用栈存储过去元素。
- 2 输入：如果栈不为空，且当前元素与栈顶元素相同，则栈顶元素出栈，否则将该元素进栈。
- 3 输出：栈中元素取反则为最终输出字符串。
代码如下：
class Solution {
public:
string removeDuplicates(string s) {
string result = "";
stack st;
st.push(s[0]);
for(int i=1; i<s.size(); i++){
if (!st.empty() && s[i] == st.top()) st.pop();
else st.push(s[i]);
}
while(!st.empty()){
result += st.top();
st.pop();
}
reverse(result.begin(), result.end());
return result;
}
};5 逆波兰表达式
给你一个字符串数组 tokens ，表示一个根据 逆波兰表示法 表示的算术表达式。
请你计算该表达式。返回一个表示表达式值的整数。
解题思路：
- 1 遇到数字就进栈
- 2 遇到计算符号就取出栈顶2个元素进行计算，将计算结果进栈。
代码如下：
class Solution {
public:
int evalRPN(vector& tokens) {
stack st;
for(auto t:tokens){
if (t=="+" || t=="-" || t=="*" || t=="/"){
int x = stoi(st.top()); st.pop();
int y = stoi(st.top()); st.pop();
int z;
if (t=="+") { z = x + y; st.push(to_string(z));}
else if (t=="-") {z = y - x; st.push(to_string(z));}
else if (t=="*") {z = x * y; st.push(to_string(z));}
else if (t=="/") {z = y / x; st.push(to_string(z));}
}else st.push(t);
}
int result = stoi(st.top());
return result;
}
};6 滑动窗口最大值
给你一个整数数组 nums，有一个大小为 k 的滑动窗口从数组的最左侧移动到数组的最右侧。你只可以看到在滑动窗口内的 k 个数字。滑动窗口每次只向右移动一位。
返回 滑动窗口中的最大值 。
暴力做法：超时
解题思路：从滑动窗口内找到最大值，存储到result数组中。
代码如下：
class Solution {
public:
vector maxSlidingWindow(vector& nums, int k) {
vector result;
int m = nums.size();
for(int i=0; i<m-k+1; i++){
int maxValue = INT_MIN;
for(int j=i; j<i+k; j++){
maxValue = max(maxValue, nums[j]);
}
result.push_back(maxValue);
}
return result;
}
};单调队列：
解题思路：
- 1 输入：
- 当输入元素大于单调队列的首元素时，则将队列清空，push该元素到单调队列。
- 当输入元素小于单调队列的首元素时，则push该元素到单调队列。
- 2 输出：
7 前k个高频元素
给你一个整数数组 nums 和一个整数 k ，请你返回其中出现频率前 k 高的元素。你可以按 任意顺序 返回答案。
解题思路：
- 1 统计元素的频率 – 字典
- 2 对元素的频率进行排序 – vector排序/ 优先级队列
- 3 返回前k个元素
vector排序：
class Solution {
public:
vector topKFrequent(vector& nums, int k) {
unordered_map<int, int> my_map;
vector result;
for(auto num:nums) my_map[num]++;
vector<pair<int, int>> vec(my_map.begin(), my_map.end());
sort(vec.begin(), vec.end(), [](pair<int, int> a, pair<int, int> b){return a.second > b.second;});
for(int i=0; i<k; i++) result.push_back(vec[i].first);
return result;
}
};优先级队列：