栈的应用实例

栈的应用实例

一.有效的括号

题目描述

解题思路：

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