栈的应用实例
程序员文章站
2022-07-03 18:26:52
栈的应用实例一.有效的括号题目描述解题思路：根据问题分析，若要判断当前左括号是否存在一个右括号与之对应。则需要判断该括号右边字符串的左括号是否有对应。根据这样的原则，可以使用栈。栈的一大特点是后进先出(last-in first-out)，这样可以先判断最右边的左括号。故遍历字符串，将所有左括号压入栈底，当遇到右括号时拿出栈中顶端元素进行判断。若不能匹配则该字符串不满足要求，匹配则推出栈顶元素。在遍历完字符串后，判断栈是否为空。为空则满足，否则不满足。我们可以对所给出的括号序列进行遍历的操作...
栈的应用实例
一.有效的括号
题目描述
解题思路：
- 根据问题分析，若要判断当前左括号是否存在一个右括号与之对应。则需要判断该括号右边字符串的左括号是否有对应。根据这样的原则，可以使用栈。栈的一大特点是后进先出(last-in first-out)，这样可以先判断最右边的左括号。故遍历字符串，将所有左括号压入栈底，当遇到右括号时拿出栈中顶端元素进行判断。若不能匹配则该字符串不满足要求，匹配则推出栈顶元素。在遍历完字符串后，判断栈是否为空。为空则满足，否则不满足。
- 我们可以对所给出的括号序列进行遍历的操作，如果碰到是左边的情况，就将其进行入栈的操作，如果碰到的是右边的情况，那么我们首先可以来看栈是不是空的，如果栈是空的，那么一定不会匹配成功，如果栈不是空的，那么我们可以用右边的括号与当前的栈顶元素来进行匹配的操作，如果匹配成功，就把当前的栈顶元素弹出，如果没有匹配成功的话，那么就说明当前所给出的括号序列是不匹配的，直接跳出就好了，代码如下所示：
代码如下所示：
代码一：
class Solution {
public:
bool isValid(string s) {
stack<char> p;
for (auto c : s)
{
switch (c){
case '(':
case '{':
case '[':
p.push(c);
break;
case ')':
if (p.empty())
return false;
if (p.top() != '(')
return false;
p.pop();
break;
case '}':
if (p.empty())
return false;
if (p.top() != '{')
return false;
p.pop();
break;
case ']':
if (p.empty())
return false;
if (p.top() != '[')
return false;
p.pop();
break;
}
}
return p.empty() ? true : false;
}
};
代码二：
class Solution {
public:
bool isValid(string s)
{
stack<char> st;
for(auto x:s)
{
if(x == '(' || x == '{' || x == '[') st.push(x);
else
{
if(st.empty())
return false;
if(x == ')' && st.top() == '('
|| x == '}' && st.top() == '{'
|| x == ']' && st.top() == '[')
st.pop();
else
return false;
}
}
if(st.empty())
return true;
else
return false;
}
};
二.逆波兰表达式求值
题目描述：
解体思路：
- 从前往后遍历数组
- 遇到数字则压入栈中
- 遇到符号，则把栈顶的两个数字拿出来运算，把结果再压入栈中
- 遍历完整个数组，栈顶数字即为最终答案
代码一：
class Solution {
public:
int evalRPN(vector<string>& tokens)
{
stack<int> nums;
for(const string& s: tokens)
{
if(s == "+" || s == "-" || s == "*" || s == "/")
{
int a = nums.top();
nums.pop();
int b = nums.top();
nums.pop();
if(s == "+")
nums.push(b + a);
else if(s == "-")
nums.push(b - a);
else if(s == "*")
nums.push(b * a);
else if(s == "/")
nums.push(b / a);
}
else
nums.push(atoi(s.c_str()));
//asoi：asiii to int参数 str 所指向的字符串转换为一个整数
// s.push(atoi(a.c_str()));
// a.str()就是把a从string转换为c风格字符串，因为atoi只认这个。
// atoi()就是把刚刚的c风格字符串转换成整型。
// 在也可以直接用s.push(stoi(a))
}
return nums.top();
}
};
代码二：
class Solution {
public:
int ans;
int evalRPN(vector<string>& tokens)
{
stack<int> ret;
int a, b;
for (auto c : tokens)
{
if (c == "+")
{
a = ret.top();
ret.pop();
b = ret.top();
ret.pop();
ret.push(b + a);
}
else if (c == "-")
{
a = ret.top();
ret.pop();
b = ret.top();
ret.pop();
ret.push(b - a);
}
else if (c == "*")
{
a = ret.top();
ret.pop();
b = ret.top();
ret.pop();
ret.push(b * a);
}
else if (c == "/")
{
a = ret.top();
ret.pop();
b = ret.top();
ret.pop();
ret.push(b / a);
}
else
ret.push(atoi(c.c_str()));
//asoi：asiii to int参数 str 所指向的字符串转换为一个整数
// s.push(atoi(a.c_str()));
// a.str()就是把a从string转换为c风格字符串，因为atoi只认这个。
// atoi()就是把刚刚的c风格字符串转换成整型。
// 在也可以直接用s.push(stoi(a))
}
ans = ret.top();
return ans;
}
};
三.实现一个最小栈
题目描述：
解题思路：
- 要做出这道题目，首先要理解栈结构先进后出的性质。
- 对于栈来说，如果一个元素 a 在入栈时，栈里有其它的元素 b, c, d，那么无论这个栈在之后经历了什么操作，只要 a 在栈中，b, c, d 就一定在栈中，因为在 a 被弹出之前，b, c, d 不会被弹出。
- 因此，在操作过程中的任意一个时刻，只要栈顶的元素是 a，那么我们就可以确定栈里面现在的元素一定是 a, b, c, d。
- 那么，我们可以在每个元素 a 入栈时把当前栈的最小值 m 存储起来。在这之后无论何时，如果栈顶元素是 a，我们就可以直接返回存储的最小值 m。
代码如下所示：
class MinStack {
public:
stack<int> s;//数据栈
stack<int> min;//辅助栈
/** initialize your data structure here. */
MinStack()
{
}
void push(int x)
{
s.push(x);
if(min.empty()||x<=min.top())
{
min.push(x);
}
}
void pop() {
if(s.top()==min.top())
min.pop();
s.pop();
}
int top()
{
return s.top();
}
int getMin()
{
return min.top();
}
};
四.验证栈序列
题目描述：
代码如下所示：
class Solution {
public:
bool validateStackSequences(vector<int>& pushed, vector<int>& popped) {
if(pushed.size() == 0 && popped.size() == 0)
return true; //两个序列都为空
if(pushed.size() == 0 || popped.size() == 0)
return false; //只有一个序列为空
stack<int> s;
int j = 0; //用于popped的index
for(auto c : pushed)
{
//首先压栈
s.push(c);
while(!s.empty() && j < popped.size() && s.top() == popped[j])
{
//栈非空才能出栈
//j<popped.size()才能判断是否越界
//st.top()==popped[j]才能判断是否能出栈
s.pop(); //出栈
++j; //指向下一个popped的值
}
}
return s.empty(); //最后判断是否栈空
}
};
本文地址：https://blog.csdn.net/weixin_43831728/article/details/107287389