【算法系列】栈

leetcode题目

一、删除字符串中的所有相邻重复项

二、比较含退格的字符串

三、基本计算器 II

四、字符串解码

五、验证栈序列

六、有效的括号

七、最小栈

八、逆波兰表达式求值

九、用栈实现队列

十、用队列实现栈

leetcode题目

一、删除字符串中的所有相邻重复项

1047. 删除字符串中的所有相邻重复项 - 力扣（LeetCode）https://leetcode.cn/problems/remove-all-adjacent-duplicates-in-string/1.题目解析

删除字符串中所有相邻的重复项

2.算法分析

显然该题是要用栈，遍历字符串，当遍历到的元素和栈顶元素一样时，就让栈顶元素出栈，否则就让遍历到的元素入栈；本题如果创建一个栈，最后还要把栈的元素都依次插入到字符串中，还得逆序字符串，因此我们直接用字符串模拟栈~

3.算法代码

class Solution {
public:
    string removeDuplicates(string s) 
    {
        string ret; //模拟栈
        for(auto ch : s)
        {
            if(ret.size() && ch == ret.back()) ret.pop_back();
            else ret.push_back(ch);
        }
        return ret;
    }
};

二、比较含退格的字符串

844. 比较含退格的字符串 - 力扣（LeetCode）https://leetcode.cn/problems/backspace-string-compare/1.题目解析

本质和题目一是一样的

2.算法分析

依旧是用字符串模拟栈，解法和题目是一样的~

3.算法代码

class Solution {
public:
    bool backspaceCompare(string s, string t) 
    {
        return changeStr(s) == changeStr(t);
    }

    string changeStr(string& s)
    {
        string ret;
        for(char ch : s)
        {
            if(ch != '#') ret += ch;
            else 
            {
                if(ret.size())
                    ret.pop_back(); 
            }
        }
        return ret;
    }
};

三、基本计算器 II

227. 基本计算器 II - 力扣（LeetCode）https://leetcode.cn/problems/basic-calculator-ii/1.题目解析

给定一个字符串(包含加减乘除运算), 字符串中可能有空格，求最终结果

2.算法分析

利用栈来模拟计算过程(栈+变量op)

大家可以根据下面的总结去分析一下这个例子： 4-3+6*4/2-123+34

1.遇到操作符, 更新操作符 op (开始置成'+')

2.遇到数字:

2.1 先把数字提取出来 tmp

2.2 分情况讨论，根据op的符号:

   2.2.1 op == '+', tmp入栈

     2.2.2 op == '-', -tmp入栈

     2.2.3 op == '*', 直接乘到栈顶元素上

     2.2.4 op == '/', 直接除到栈顶元素上

最后把栈中的所有元素加起来就可以了~

3.算法代码

class Solution {
public:
    int calculate(string s)
    {
        vector<int> st; //数组模拟栈
        int i = 0, n = s.size();
        char op = '+';
        while(i < n)
        {
            if(s[i] == ' ') i++; //跳过空格
            else if(s[i] >= '0' && s[i] <= '9') //数字字符
            {
                int tmp = 0;
                //提取数字
                while(i < n && s[i] >= '0' && s[i] <= '9') 
                    tmp = tmp * 10 + (s[i++] - '0');
                if(op == '+') st.push_back(tmp);
                else if(op == '-') st.push_back(-tmp);
                else if(op == '*') st.back() *= tmp;
                else if(op == '/') st.back() /= tmp;
            }
            else
                op = s[i++];
        }
        //将栈中的所有元素加起来，就是最终结果
        int ret = 0;
        for(auto x : st)
            ret += x;
        return ret;
    }
};

四、字符串解码

394. 字符串解码 - 力扣（LeetCode）https://leetcode.cn/problems/decode-string/description/1.题目解析

k[encoded_string]，表示将encoded_string重复k次，给定的字符串中可能有多个[ ], 求最终解码后字符串

2.算法分析

用双栈模拟字符串解码过程大家可以用下面的方法去分析一下这个例子:

eg: 1 [ a 2 [ b c ] ] d e 3 [ f ]

注意:字符串栈开始放一个空字符串，就是为了防止放到"字符串栈"栈顶的字符串后面时栈为空而非法访问报错~

1.遇到数字：把数字提取出来, 放入"数字栈"

2.遇到 '['：把后面的字符串提取出来，放入"字符串栈"中

3.遇到 ']': 取出两栈的栈顶元素进行解析，然后放到"字符串栈"栈顶的字符串后面

4.遇到单独的字符：提取出字符串，直接放到"字符串栈"栈顶的字符串后面

遍历完题目所给字符串后，字符串栈的栈顶字符串就是最终解码结果~

3.算法代码

class Solution {
public:
    string decodeString(string s) 
    {
        stack<int> nums;
        stack<string> st;
        st.push(""); //字符串开始放一个空串
        int i = 0, n = s.size();
        while(i < n)
        {
            if(s[i] >= '0' && s[i] <= '9') //遇到数字，提取数字，放入数字栈
            {
                int tmp = 0;
                while(s[i] >= '0' && s[i] <= '9')
                    tmp = tmp * 10 + (s[i++] - '0');
                nums.push(tmp);
            }
            else if(s[i] == '[') //遇到'[', 将'['后面的字符串提取出来，放入字符串栈
            {
                i++;
                string tmp;
                while(s[i] >= 'a' && s[i] <= 'z')
                    tmp += s[i++];
                st.push(tmp);
            }
            else if(s[i] == ']') //遇到']', 取出两栈的栈顶元素，进行解析，然后将结果加入到字符串栈栈顶字符串的后面
            {
                string tmp = st.top();
                st.pop();
                int k = nums.top();
                nums.pop();
                while(k--)
                    st.top() += tmp;
                i++; //跳过']'
            }
            else //遇到单独的字符串，直接提取字符串，加入到字符串栈栈顶元素的后面
            {
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                    tmp += s[i++];
                st.top() += tmp;
            }
        }
        return st.top();
    }
};

五、验证栈序列

946. 验证栈序列 - 力扣（LeetCode）https://leetcode.cn/problems/validate-stack-sequences/description/栈的压入、弹出序列_牛客题霸_牛客网 (nowcoder.com)https://www.nowcoder.com/practice/d77d11405cc7470d82554cb392585106?tpId=13&&tqId=11174&rp=1&ru=/activity/oj&qru=/ta/coding-interviews/question-ranking1.题目解析

给定入栈序列，判断给定的出栈序列是否成立

2.算法分析

借助栈模拟过程即可

1.让pushed元素一直进栈

2.定义i下标遍历popped数组，进栈后判断栈顶元素是否和popped[i] 相等，相等就出栈, 同时i++

所有元素进栈完毕之后，判断 i 是否已经遍历完毕，或者判断栈是否为空即可

3.算法代码

class Solution {
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        stack<int> st;
        int i = 0;
        for(auto x : pushed) 
        {
            st.push(x); //让pushed中的元素一直进栈
            while(st.size() && st.top() == popped[i]) //判断栈顶元素与popped对应位置元素是否相等
            {
                st.pop();
                i++;
            }
        }
        //return st.empty(); 
        return i == popped.size();
    }
};

六、有效的括号

20. 有效的括号 - 力扣（LeetCode）https://leetcode.cn/problems/valid-parentheses/1.题目解析

给定一个包含三类括号的字符串，判断括号是否有效匹配

2.算法分析

用栈模拟括号匹配过程即可

1.遇到左括号，入栈

2.遇到右括号，取栈顶元素和右括号匹配，匹配失败就返回false(注意细节问题，就是当第一个字符就是右括号，栈中还没有元素，取栈顶元素会非法访问，要特殊处理一下)

当遍历完整个字符串之后，如果栈中还有元素，就返回false, 否则返回true

3.算法代码

class Solution {
public:
    bool isValid(string s) 
    {
        int i = 0, n = s.size();
        stack<char> st;
        while(i < n)
        {
            if(s[i] == '(' || s[i] == '{' || s[i] == '[') //左括号就进栈
                st.push(s[i]);
            else //是右括号就取栈顶元素
            {
                //1.开始就是右括号, 返回false
                if(st.empty()) 
                    return false;
                //2.判断括号是否匹配
                char ch = st.top();
                st.pop();
                if(ch == '(' && s[i] != ')'
                || ch == '{' && s[i] != '}'
                || ch == '[' && s[i] != ']')
                    return false;
            }
            i++;
        }
        return st.empty(); //如果栈中还有元素，就返回false
    }
};

七、最小栈

155. 最小栈 - 力扣（LeetCode）https://leetcode.cn/problems/min-stack/description/1.题目解析

设计一个栈，支持栈的常规操作，并且能够在常数时间内检索到栈中的最小元素

2.算法分析

借助一个栈 _minst, _minst的栈顶元素保存了栈 _st 中的最小值

push: 当_minst为空或插入元素val <= _minst的栈顶元素时候，val插入_minst

pop: 当_st的栈顶元素 == _minst的栈顶元素时，弹出 _minst的栈顶元素

3.算法代码

class MinStack {
public:
    MinStack() {}
    
    void push(int val) {
        _st.push(val);
        if(_minst.empty() || 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();
    }

    stack<int> _st;
    stack<int> _minst;
};

八、逆波兰表达式求值

150. 逆波兰表达式求值 - 力扣（LeetCode）https://leetcode.cn/problems/evaluate-reverse-polish-notation/1.题目解析

给定一个逆波兰表达式(后缀表达式), 求表达式的值

2.算法分析

逆波兰表达式(后缀表达式)，该表达式可以很好的借助栈来模拟计算

1. 遇到数字，入栈

2. 遇到操作符，取出栈顶的两个元素，分别作为右操作数和左操作数，进行计算, 计算结果放入栈中

3.算法代码

class Solution {
public:
    int evalRPN(vector<string>& tokens) {
        stack<int> st;
        for(auto& str : tokens)
        {
            if(str == "+"
            || str == "-"
            || str == "*"
            || str == "/")
            {
                int right = st.top();
                st.pop();
                int left = st.top();
                st.pop();
                switch(str[0])
                {
                    case '+':
                        st.push(left + right);
                        break;
                    case '-':
                        st.push(left - right);
                        break;
                    case '*':
                        st.push(left * right);
                        break;
                    case '/':
                        st.push(left / right);
                        break;  
                }
            }
            else
            {
                st.push(stoi(str));
            }
        }
        return st.top();
    }
};

九、用栈实现队列

232. 用栈实现队列 - 力扣（LeetCode）https://leetcode.cn/problems/implement-queue-using-stacks/1.题目解析

用两个栈实现队列

2.算法分析

定义两个栈，pushst用于压入元素，popst用于弹出元素~

3.算法代码

class MyQueue {
public:
    MyQueue() {}
    
    void push(int x)
    {
        pushst.push(x);
    }
    
    int pop() 
    {
        int top = peek();
        popst.pop();
        return top;
    }
    
    int peek() 
    {
        if(popst.empty())
        {
            while(!pushst.empty())
            {
                int top = pushst.top();
                pushst.pop();
                popst.push(top);
            }
        }
        return popst.top(); 
    }
    
    bool empty() 
    {
        return popst.empty() && pushst.empty();
    }
private:
    stack<int> pushst;
    stack<int> popst;
};

十、用队列实现栈

225. 用队列实现栈 - 力扣（LeetCode）https://leetcode.cn/problems/implement-stack-using-queues/description/1.题目解析

用两个队列实现栈

2.算法分析

两个队列，使用时保持一个队列为空，一个队列不为空

push: 哪个队列不为空，push到哪个队列

pop: 哪个队列不为空，哪个队列就一直pop元素到另外一个队列，直到原本不为空的队列只剩下一个元素，返回该元素并从队列中pop即可

top: 哪个队列不为空，就返回哪个队列的back()

empty: 当栈中有元素时始终有1个队列为空，1个不为空，只有两队列都为空时，栈才为空

3.算法代码

class MyStack {
public:
    MyStack() {}
    
    void push(int x)
    {
        if(!q1.empty())
            q1.push(x);
        else 
            q2.push(x);
    }
    
    int pop() 
    {
        if(!q1.empty())
        {
            while(q1.size() > 1)
            {
                q2.push(q1.front());
                q1.pop();
            }
            int top = q1.front();
            q1.pop();
            return top;
        }
        else
        {
            while(q2.size() > 1)
            {
                q1.push(q2.front());
                q2.pop();
            }
            int top = q2.front();
            q2.pop();
            return top;  
        }
    }
    
    int top() 
    {
        if(!q1.empty())
            return q1.back();
        else 
            return q2.back();
    }
    
    bool empty() 
    {
        return q1.empty() && q2.empty();
    }
private:
    queue<int> q1;
    queue<int> q2;
};