当前位置: 萬仟网 > IT编程>脚本编程>vue.js > 栈的应用实例

栈的应用实例

2020年07月14日  | 萬仟网IT编程  | 我要评论

栈的应用实例

一.有效的括号
题目描述

在这里插入图片描述
在这里插入图片描述

解题思路:
  • 根据问题分析,若要判断当前左括号是否存在一个右括号与之对应。则需要判断该括号右边字符串的左括号是否有对应。根据这样的原则,可以使用栈。栈的一大特点是后进先出(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

如对本文有疑问, 点击进行留言回复!!

相关文章:

验证码:
Copyright © 2017-2020  萬仟网 保留所有权利. 粤ICP备17035492号-1
站长QQ:2386932994 | 联系邮箱:2386932994@qq.com