算法总结-栈和队列
1.栈实现队列
思路：两个栈实现，一个出一个进。
pop() 把sin的元素出栈赋值给sout，赋值完后sout pop的第一个就是队头元素
peek() 直接调用上述实现的pop函数
class MyQueue {
public:
MyQueue() {
}
stack<int> sin;
stack<int> sout;
void push(int x) {
sin.push(x);
}
int pop() {
if(sout.empty())
{
while(!sin.empty())
{
sout.push(sin.top());
sin.pop();
}
}
int res=sout.top();
sout.pop();
//两个栈实现 弹出后另外一个栈不需要赋值了 后续直接用sout操作
return res;
}
int peek() {
int res=this->pop();
//这里是sout再push进来
sout.push(res);
return res;
}
bool empty() {
return sin.empty()&&sout.empty();
}
};2.队列实现栈
思路：单个队列实现。
pop：把队列的头元素依次插入到队尾，除了最后一个（这个元素是要pop出去的）。
top：直接调用队列的back方法
class MyStack {
public:
MyStack() {
}
queue<int> q1;
void push(int x) {
q1.push(x);
}
int pop() {
int size=q1.size();
size--;
while(size--)
{
q1.push(q1.front());
q1.pop();
}
int res=q1.front();
//记得要pop
q1.pop();
return res;
}
int top() {
int res=q1.back();
return res;
}
bool empty() {
return q1.empty();
}
};思路：用栈来实现，遍历s对于每一个左括号，栈里push进一个相应的右括号。两种失败情况，如果栈的top和s[i]相等就返回true
class Solution {
public:
bool isValid(string s) {
stack<char> sk;
for(int i=0;i<s.size();i++)
{
if(s[i]=='(')
{
sk.push(')');
}
else if(s[i]=='[')
{
sk.push(']');
}
else if(s[i]=='{')
{
sk.push('}');
}
// 第三种情况：遍历字符串匹配的过程中，栈已经为空了，没有匹配的字符了，说明右括号没有找到对应的左括号 return false
// 第二种情况：遍历字符串匹配的过程中，发现栈里没有我们要匹配的字符。所以return false
else if(sk.empty()||sk.top()!=s[i])
{
return false;
}
else
{
//sk.top()==s[i] 栈弹出
sk.pop();
}
}
return sk.empty();
}
};1047. 删除字符串中的所有相邻重复项
注意 push的逻辑
class Solution {
public:
string removeDuplicates(string s) {
stack<char> sk;
for(int i=0;i<s.size();i++)
{
//注意 push的逻辑
if(sk.empty()||sk.top()!=s[i])
{
sk.push(s[i]);
}
else{
sk.pop();
}
}
string res="";
while(!sk.empty())
{
res+=sk.top();
sk.pop();
}
reverse(res.begin(),res.end());
return res;
}
};用2 减去 1
要用stoll把string转成int
class Solution {
public:
int evalRPN(vector<string>& tokens) {
stack<int> sk;
for(int i=0;i<tokens.size();i++)
{
if(tokens[i]=="+"||tokens[i]=="-"||tokens[i]=="*"||tokens[i]=="/")
{
int num1=sk.top();
sk.pop();
int num2=sk.top();
//这里也要pop掉
sk.pop();
if(tokens[i]=="+")
sk.push(num2+num1);
if(tokens[i]=="-")
sk.push(num2-num1);
if(tokens[i]=="*")
sk.push(num2*num1);
if(tokens[i]=="/")
sk.push(num2/num1);
}
else{
//字符串要转成 int
sk.push(stoll(tokens[i]));
}
}
return sk.top();
}
};deque双端队列
思路 用deque模拟滑动窗口动，封装好pop、push、front方法
class Solution {
public:
class Mydeque
{
public:
deque<int> de;
void pop(int value)
{
//窗口移除的元素是第一个元素 那么pop 其他的都不操作
if(!de.empty()&&value==de.front())
{
de.pop_front();
}
}
void push(int value)
{
//先pop 循环判断 值大于最后一个值就pop
while(!de.empty() &&value>de.back())
{
de.pop_back();
}
//再push
de.push_back(value);
}
int front()
{
return de.front();
}
};
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
Mydeque que;
vector<int> result;
for(int i=0;i<k;i++)
{
que.push(nums[i]);
}
result.push_back(que.front());
for(int i=k;i<nums.size();i++)
{
que.pop(nums[i-k]);
que.push(nums[i]);
result.push_back(que.front());
}
return result;
}
};小顶堆队列
先用哈希map存储每个元素的频率
放入队列中 控制队列大小
小顶堆=>反向输出到结果集
class Solution {
public:
class mycmp{
// public:
public:
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) {
//<int,int>
unordered_map<int,int> map;
vector<int> result(k);
for(int i=0;i<nums.size();i++)
{
map[nums[i]]++;
}
priority_queue<pair<int,int>,vector<pair<int,int>>,mycmp> pri_que;
for(unordered_map<int,int>:: iterator it=map.begin();it!=map.end();it++)
{
pri_que.push(*it);
if(pri_que.size()>k)
{
pri_que.pop();
}
}
for(int i=k-1;i>=0;i--)
{
//pri_que.top().first;
result[i]=pri_que.top().first;
pri_que.pop();
}
return result;
}
};原文地址：https://blog.csdn.net/qq_66230764/article/details/139768264
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！