栈与队列理论基础
- 栈stack：先进后厨
- 队列queue：先进先出
- STL（C++标准库）
- STL 栈和队列属于容器适配器（container adapter）
- 优先队列priority_queue：
- 默认大根堆，如果是pair<a,b>，默认比较a大小
- 如果需要比较b大小，且小根堆，可以如下实现
232.用栈实现队列
- pop操作时，当out栈为空时，需要将in栈全部取出并放入out
#include<bits/stdc++.h>
using namespace std;
class MyQueue {
public:
stack<int> stIn, stOut;
MyQueue() {
}
void push(int x) {
stIn.push(x);
}
int pop() {
//只有Out栈为空时，需要把In栈全部放到Out栈
if(stOut.empty()){
while(!stIn.empty()){
stOut.push(stIn.top());
stIn.pop();
}
}
int a = stOut.top();
stOut.pop();
return a;
}
int peek() {
int a = this->pop();
stOut.push(a);
return a;
}
bool empty() {
return stIn.empty()&&stOut.empty();
}
};
225. 用队列实现栈
- pop操作时，把除最后一个元素外所有元素取出队列再放进，此时再取出下一个元素即模拟可栈后进先出。
#include<bits/stdc++.h>
using namespace std;
class MyStack {
public:
queue<int> que;
MyStack() {
}
void push(int x) {
que.push(x);
}
int pop() {
int size = que.size();
while(size>1){
que.push(que.front());
que.pop();
size--;
}
int ans = que.front();
que.pop();
return ans;
}
int top() {
return que.back();
}
bool empty() {
return que.empty();
}
};
20. 有效的括号
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
bool isValid(string s) {
stack<char> st;
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();
}
};
删除字符串中的所有相邻重复项
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
string removeDuplicates(string s) {
stack<char> st;
for(int i=0;i<s.size();i++){
if(st.empty()||st.top()!=s[i]) st.push(s[i]);
else st.pop();
}
string ans = "";
while(!st.empty()){
ans += st.top();
st.pop();
}
reverse(ans.begin(),ans.end());
return ans;
}
};
- C++中，std::string类提供类似入栈、出栈接口
class Solution {
public:
string removeDuplicates(string s) {
string stk;
for (char ch : s) {
if (!stk.empty() && stk.back() == ch) {
stk.pop_back();
} else {
stk.push_back(ch);
}
}
return stk;
}
};
150. 逆波兰表达式求值
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> st;
for(string token: tokens){
if(token!="+"&&token!="-"&&token!="*"&&token!="/"){
int t = stoi(token);//stoi函数，string to int 缩写
st.push(t);
}
else{
int num1 = st.top();
st.pop();
int num2 = st.top();
st.pop();
if(token=="+") st.push(num2+num1);
if(token=="-") st.push(num2-num1);
if(token=="*") st.push(num2*num1);
if(token=="/") st.push(num2/num1);
}
}
int ans = st.top();
st.pop();
return ans;
}
};
239. 滑动窗口最大值
- 优先队列priority_queue
- 需要存下标，判断是否在窗口内
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
priority_queue<pair<int, int>> que;//pair<nums[i], i>
for(int i=0;i<k;i++){
que.emplace(nums[i], i);
}
vector<int> ans = {que.top().first};
//开始滑动
for(int i=k;i<nums.size();i++){
que.emplace(nums[i], i);
//当优先队列队首值（最大值）index没在窗口范围内，出队列，保证最大值索引在窗口内
while(que.top().second<=i-k){
que.pop();
}
ans.push_back(que.top().first);
}
return ans;
}
};
- 单调队列
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
int n = nums.size();
deque<int> q;
for (int i = 0; i < k; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
}
vector<int> ans = {nums[q.front()]};
for (int i = k; i < n; ++i) {
while (!q.empty() && nums[i] >= nums[q.back()]) {
q.pop_back();
}
q.push_back(i);
while (q.front() <= i - k) {
q.pop_front();
}
ans.push_back(nums[q.front()]);
}
return ans;
}
};
347.前 K 个高频元素
- 使用优先队列定义小根堆并自定义比较方式时需注意：
-
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> minHeap(cmp);
-
static bool cmp(pair<int, int> &m, pair<int, int> &n)
- 即decltype(&cmp)里的‘&’不能少，且cmp函数需要是static静态函数，否则decltype推断时报错
-
#include<bits/stdc++.h>
using namespace std;
class Solution {
public:
static bool cmp(pair<int, int> &m, pair<int, int> &n) {
return m.second > n.second;
}
vector<int> topKFrequent(vector<int>& nums, int k) {
priority_queue<pair<int, int>, vector<pair<int, int>>, decltype(&cmp)> minHeap(cmp);//小根堆
unordered_map<int, int> map;
for(int i=0;i<nums.size();i++){
map[nums[i]]++;
}
for(auto it: map){
if(minHeap.size()==k){
if(minHeap.top().second<it.second){
minHeap.pop();
minHeap.emplace(it.first, it.second);
}
}
else{
minHeap.emplace(it.first, it.second);
}
}
vector<int> ans;
while(!minHeap.empty()){
ans.push_back(minHeap.top().first);
minHeap.pop();
}
return ans;
}
};
栈与队列总结篇
- 站和队列是容器适配器
- 默认情况下栈和队列的底层容器是deque双端队列，
- 栈的经典应用：括号匹配、逆波兰表达式
- 队列经典应用：滑动窗口最大值（单调队列）、求前k个高频元素（优先级队列）
标签：队列,随想录,pop,st,int,que,push,刷题 From： https://www.cnblogs.com/daxiawan2022/p/17686132.html