栈和队列
- 《代码随想录》
- 使用两个栈来模拟队列,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方法)。
- 不要以为单调队列就是对窗口里的数进行排序,如果是那样的话,跟优先级队列又有什么区别呢。
- 详见代码中的注释,看不懂就多看下面的动画演示。
![在这里插入图片描述](https://img-blog.csdnimg.cn/b7c19ce3bbf4411fa1b3f5dfb7073224.gif#pic_center)
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;
}
};
评论区