专题一:栈系列
1. 中缀表达式转后缀表达式(逆波兰式)
2. 有效的括号
算法原理
class Solution
{
public:
bool isValid(string s)
{
stack<char> st;
for(const auto ch : s)
{
if(ch == '(' || ch == '[' || ch == '{') st.push(ch);
else
{
// 1、右括号多
if(st.empty()) return false;
char top = st.top();
if(top == '(' && ch == ')' || top == '[' && ch == ']' || top == '{' && ch == '}')
st.pop();
else
return false; // 2、括号不匹配
}
}
return st.empty(); // 3、最后若栈为空,说明左括号全部正确匹配完成
}
};
3. 用栈实现队列
算法原理
class MyQueue
{
private:
stack<int> st1; //负责入队列
stack<int> st2; //负责出队列
public:
// 构造函数,什么都不需要做
MyQueue()
{}
// 入队列
void push(int x)
{
st1.push(x);
}
// 出队列
int pop()
{
// 队列为空,则返回-1
if(st1.empty() && st2.empty()) return -1;
// 若 st2 为空,则需要从 st1 中把元素更新过来
if(st2.empty())
{
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
}
// st2 栈顶元素即使队列的对首元素,删除即可
int ans = st2.top();
st2.pop();
return ans;
}
int peek()
{
// 队列为空,则返回-1
if(st1.empty() && st2.empty()) return -1;
// 若 st2 为空,则需要从 st1 中把元素更新过来
if(st2.empty())
{
while(!st1.empty())
{
st2.push(st1.top());
st1.pop();
}
}
// st2 栈顶元素即使队列的对首元素,返回即可
return st2.top();
}
// 队列判空
bool empty()
{
return st1.empty() && st2.empty();
}
};
4. 最小栈
算法原理
class MinStack
{
private:
stack<int> st; //存放栈元素
stack<int> minSt;//存放st中,最小元素序列
public:
// 默认构造函数
MinStack()
{}
// 栈中插入元素
void push(int val)
{
st.push(val);
// 1、若最小栈为空(说明是第一个插入元素),此时 val 直接入最小栈
// 2、若最小栈不为空,则比较最小栈栈顶元素,再决定是否插入最小栈
if(minSt.empty()) minSt.push(val);
else
{
if(val <= minSt.top()) minSt.push(val);
}
}
// 弹出栈顶元素
void pop()
{
// 若栈顶元素为栈中最小元素,则需要同步更新最小栈
if(st.top() == minSt.top()) minSt.pop();
// 弹出栈顶元素
st.pop();
}
// 获取栈顶元素
int top()
{
return st.top();
}
// 获取栈中最小元素
int getMin()
{
return minSt.top();
}
};
原文地址:https://blog.csdn.net/m0_51064412/article/details/134781905
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。
如若转载,请注明出处:http://www.7code.cn/show_41804.html
如若内容造成侵权/违法违规/事实不符,请联系代码007邮箱:suwngjj01@126.com进行投诉反馈,一经查实,立即删除!
声明:本站所有文章,如无特殊说明或标注,均为本站原创发布。任何个人或组织,在未征得本站同意时,禁止复制、盗用、采集、发布本站内容到任何网站、书籍等各类媒体平台。如若本站内容侵犯了原著者的合法权益,可联系我们进行处理。