栈和队列
- 《代码随想录》
- 使用两个栈来模拟队列，stIn用来输入，stOut用来输出。
- push: 直接将元素push进stIn
- pop: 将stIn中的元素导入stOut,再由stOut上pop出来。如果stOut()非空，直接从stOut中取，否则先从stIn中push进stOut。
- peek: 复用pop,取出第一个，然后再push进stOut。
- empty: 元素分开存储在stIn和stOut两个栈中，所以要同时判断是否为空。
- 补充:
实际开发中，一定要懂得复用，功能相近的函数要抽象出来，不要大量的复制粘贴，很容易出问题。
class MyQueue {
public:
stack<int>stIn;// 输入栈
stack<int>stOut;// 输出栈
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
if(stOut.empty()){
while(!stIn.empty()){
stOut.push(stIn.top());
stIn.pop();
}
}
int ret = stOut.top();
stOut.pop();
return ret;
}
int peek() {
int ret = pop();// 直接调用pop，然后在把对应元素push回去
stOut.push(ret);
return ret;
}
bool empty() {
return stIn.empty() && stOut.empty();
}
};
- 两个队列实现栈
- que2起到辅助作用，备份，详见下方que1=que2。
- 在pop的时候保存去掉最后一个元素之后的队列。重新赋值个que1,然后情况que2。
class MyStack {
public:
queue<int>que1;
queue<int>que2;// 起辅助作用
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
size--;
while(size--){
que2.push(que1.front());
que1.pop();
}
int ret = que1.front();
que1.pop();
que1 = que2;// que2作用
// 清空que2
while(!que2.empty()){
que2.pop();
}
return ret;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
};
- 其实使用一个栈即可
- 将队列前面的push->pop到后面，只剩之前最后一个元素不动，然后队列pop即可。
class MyStack {
public:
queue<int>que1;
MyStack() {
}
void push(int x) {
que1.push(x);
}
int pop() {
int size = que1.size();
size--;
while(size--){
que1.push(que1.front());
que1.pop();
}
int ret = que1.front();
que1.pop();
return ret;
}
int top() {
return que1.back();
}
bool empty() {
return que1.empty();
}
};
- 方法一
- 这个方法写法有点乱，判断是否可以组成一个完整的一组括号，最后判断栈是否为空，为空则说明全部匹配成功。
- 左括号直接push进，遇到右括号进行判断，若与栈顶无法组成完整括号，直接return false。
- 注意括号是一层一层包含的。例如:"{[]()}。所以"[(])"为括号的非法包含。
class Solution {
public:
bool isValid(string s) {
stack<char>st;
for(char& c:s){
// if(st.empty())st.push(c);
if(c == ')'){
if(!st.empty() && st.top() == '(')st.pop();// 是否可以匹配
else{
return false;// 无法匹配
//st.push(c);
}
}else if(c == ']'){
if(!st.empty() && st.top() == '[')st.pop();
else{
return false;
//st.push(c);
}
}else if(c == '}'){
if(!st.empty() && st.top() == '{')st.pop();
else{
return false;
//st.push(c);
}
}else{
st.push(c);
}
}
return st.empty();
}
};
- 方法二
- 同方法一，但是push进的是对应左括号的右括号，遇到右括号如果与栈顶相等再pop出去，反之return false了。
- 注意括号是一层一层包含的。例如:"{[]()}。所以"[(])"为括号的非法包含。
class Solution {
public:
bool isValid(string s) {
// 奇数长度，肯定不符合
if(s.size() % 2 != 0)return false;
stack<int>st;
for(char& c:s){
if(c == '(')st.push(')');
else if(c == '[')st.push(']');
else if(c == '{')st.push('}');
else if(st.empty() || c != st.top())return false;// 如果为空，则说明还没有左括号呢，此时这个c为右括号，无法匹配成功。
else st.pop();// c == st.top(),到这里肯定是非空
}
return st.empty();
}
};
- 栈的简单使用
- 补充:
- 递归的实现就是: 每一次调用递归都会把函数的局部变量、参数值和返回地址等压入调用栈中，然后递归返回的时候，从栈顶弹出上一次的各项参数，所以这就是为什么递归可以返回上一层位置的原因。
- 在企业项目开发中，尽量不要使用递归！在项目比较大的时候，由于参数多，全局变量等等，使用递归很容易判断不充分return的条件，非常容易无限递归(或者递归层级过深)，造成栈溢出错误(这种问题还不好排查)。
class Solution {
public:
string removeDuplicates(string s) {
stack<char>st;
for(char& c:s){
if(!st.empty() && st.top() == c)st.pop();// 注意条件控制，栈要非空。
else st.push(c);
}
string ret;
while(!st.empty()){
ret += st.top();
st.pop();
}
reverse(ret.begin(),ret.end());
return ret;
}
};
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<long long>st;
int ret = 0;
for(string &s:tokens){
// 如果是符号，则取出两个数，然后进行运算->push回去
if(s == "+" || s == "-" || s == "*" || s == "/"){
long long num1 = st.top();
st.pop();
long long num2 = st.top();
st.pop();
// 注意运算符是谁对谁后一个对前一个
if(s == "+")st.push(num2+num1);
else if(s == "-")st.push(num2-num1);
else if(s == "*")st.push(num2*num1);
else if(s == "/")st.push(num2/num1);
}else st.push(stoll(s));
}
return st.top();// 栈中剩的最后一个值为最终结果
}
};
- 单调队列
- 放进去窗口的元素，然后随着窗口的移动，单调队列也一进一出，每次移动后，队列告诉我们里面的最大值(front方法)是什么。
- 队列没有必要维护窗口中的所有元素，而只需要维护有可能成为窗口最大值的元素就可以了，同时保证队列里的元素数值是由大到小的(push方法)。
- 不要以为单调队列就是对窗口里的数进行排序，如果是那样的话，跟优先级队列又有什么区别呢。
- 详见代码中的注释，看不懂就多看下面的动画演示。
class Solution {
public:
class myQueue{
deque<int>que;
public:
void pop(int v){ // 如果当前要pop的元素是队头的，即最大的，那就pop,否则继续保留最大的。
if(!que.empty() && v == que.front()){
que.pop_front();
}
}
// 从后面开始，如果要放入窗口的元素大于后面的。
// 那就pop出来，最终将v push进去，要么为最大的，要么队列中v前面有最大的。
// 使得，队头的元素肯定为当前窗口的最大值。
void push(int v){
while(!que.empty() && v > que.back()){
que.pop_back();
}
que.push_back(v);
}
// 取得队头元素，即当前窗口的最大值。
int front(){
return que.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
vector<int>ret;
myQueue que;
// 先往里面弄k个，这样下面才能统一管理
for(int i = 0; i < k ;i++){
que.push(nums[i]);
}
ret.push_back(que.front());
for(int i = k ;i < nums.size();i++){
// 下面两步为窗口的移动，这两步的先后顺序无影响。
que.pop(nums[i-k]);// 去掉最左边元素
que.push(nums[i]);// 去掉最右边元素
// 收集结果
ret.push_back(que.front());
}
return ret;
}
};
- 这个题在一刷的时候漏掉了。
- 方法:
- 先统计每个元素出现的频率。
- 使用一个小顶堆，按照元素出现的频率排序，小顶指的是，最小的出现频率在堆顶。
- 使用k控制堆中的元素数量，保持堆中有k个元素，这k个元素即是数组中前k个高频元素。
- 小插曲: 结果让返回前k个出现的高频元素，我开始还理解错了，以为是跟上面那个题似的，维护一个k个的窗口， 每次保存窗口内出现频率最高的元素~。
class Solution {
public:
// 小顶堆排序
class myComparion{
public:
// k v:元素-频率，按照频率排序，堆顶为频率小的——小顶堆。
bool operator()(const pair<int,int>& lhs,const pair<int,int>& rhs){
return lhs.second > rhs.second;
}
};
vector<int> topKFrequent(vector<int>& nums, int k) {
// 统计元素出现的频率
unordered_map<int,int>map;// map[nums[i]]对应元素出现的次数
for(int i = 0; i < nums.size();i++){
map[nums[i]]++;
}
// 小顶堆
// k-v 元素-频率
priority_queue<pair<int,int>,vector<pair<int,int>>,myComparion>pri_que;
// 用固定大小为k的小顶堆，扫描所有频率的数值
for(unordered_map<int,int>::iterator it = map.begin();it != map.end();it++){
pri_que.push(*it);
if(pri_que.size() > k){// 如果堆中的元素数量大于k,则弹出堆顶元素，即
pri_que.pop();
}
}
// 找出前k个高频元素，因为小顶推先弹出的是最小的，所以倒叙来输出到数组中
// 我们要的是从频率高的到频率低的。
vector<int>ret(k);
for(int i = k-1;i >=0 ;i--){// 实际上队列中最多也就维持了k个元素，如上面循环中所示。
ret[i] = pri_que.top().first;
pri_que.pop();
}
return ret;
}
};