算法笔记（九）——栈

栈是一种先进后出的数据结构，其操作主要有
进栈、压栈（Push）
出栈（Pop）

常见的使用栈的算法题

• 中缀转后缀
• 逆波兰表达式求值
• 括号匹配
• 深度优先搜索

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

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

思路

• 用栈的思想来模拟
• 遍历字符串，如果栈为空或栈顶元素和进栈元素不相同，字符进栈
• 否则，即栈顶元素和进栈元素相同，则pop栈顶元素
• 但是，最后留在栈中的字符就是需要返回的，并且是逆序的，所以我们直接用原来的字符串模拟栈

C++代码

class Solution 
{
public:
    string removeDuplicates(string s) 
    {
        string res;

        for(auto ch : s)
        {
            if(res.size() && res.back() == ch) res.pop_back();
            else res.push_back(ch);
        }

        return res;
    }
};

比较含退格的字符串

题目：比较含退格的字符串

思路

• 利用栈的思想，封装一个check函数来返回退格后的字符串
• chech函数的实现：
• 遍历字符串，如果不是#，直接加到res上；否则，如果res中没有元素，但是遇到了#，直接跳过不用pop_back()

C++代码

class Solution 
{
public:
    string check(string &s)
    {
        string res;
        for(auto ch : s)
        {
            if(ch != '#') res += ch; // 如果不是‘#’。直接加到res上
            else
            {
                if(res.size()) // 如果res中没有元素，但是遇到了‘#’，应该直接跳过不用pop_back()
                    res.pop_back();
            } 
        }
        return res;
    }
    bool backspaceCompare(string s, string t) 
    {
        return check(s) == check(t); // 检查退格后的字符串是否相等
    }
};

基本计算机II

题目：基本计算器 II

思路

• 由于运算符只有('+', '-', '*', '/')这四种，我们使用一个数组来模拟栈，插入每一个数，使用一个前缀字符来进行运算符的标记，初始设为加；
• 当操作符op遇到加减都更新，遇到乘除则与栈顶元素计算，遍历结束后，我们将栈中元素相加；

C++代码

class Solution 
{
public:
    // 1. 遇到操作符，更新操作符op；
    // 2. 遇到数字；
    //      1>. 先将数字提取到tmp中
    //      2>. 根据op分类讨论
    //        ①op == '+', tmp入栈
    //        ②op == '-', -tmp入栈
    //        ③op == '*', 直接和栈顶元素相×
    //        ④op == '/', 直接和栈顶元素相÷
    int calculate(string s) 
    {
        char op = '+';
        int i = 0, n = s.size();
        vector<int> v; // 模拟栈

        while(i < n)
        {
            if(s[i] == ' ') i++;
            else if('0' <= s[i] && s[i] <= '9')
            {
                // 数字提取到tmp中
                int tmp = 0;
                while(i < n && '0' <= s[i] && s[i] <= '9')
                    tmp = 10 * tmp + (s[i++] - '0');

                if(op == '+') v.push_back(tmp);
                else if(op == '-') v.push_back(-tmp);
                else if(op == '*') v.back() *= tmp;
                else v.back() /= tmp;
            }
            else 
            {
                op = s[i];
                i++;
            }
        }

        int res = 0;
        for(auto x : v)
        {
            res += x;
        }
        return res;
    }
};

字符串解码

题目：字符串解码

思路

• 定义两个栈一个字符串、一个int变量
• 遇到数字放入数字栈
• 遇到[，把后面的字符串提取、放入字符串栈
• 遇到]，取出两栈顶元素解析，放入字符串栈的栈顶元素后面
• 遇到字符， 提取字符，放入字符串栈的栈顶元素后面

C++代码

class Solution 
{
public:
    // 两个栈一个字符串、一个int变量
    // 1. 遇到数字放入数字栈；
    // 2. 遇到'['，把后面的字符串提取、放入字符串栈
    // 3. 遇到']'，取出两栈顶元素解析，放入字符串栈的栈顶元素后面
    // 4. 遇到字符， 提取字符，放入字符串栈的栈顶元素后面

    string decodeString(string s) 
    {
        stack<string> ss;
        stack<int> si;
        int i = 0, n = s.size();

        ss.push("");
        while(i < n)
        {
            if(s[i] >= '0' && s[i] <= '9') 
            {
                int t = 0;
                while ('0' <= s[i] && s[i] <= '9')
                    t = 10 * t + (s[i++] - '0');

                si.push(t);
            }
            else if(s[i] == '[') 
            {
                i++;
                string t = "";
                while(s[i] >= 'a' && s[i] <= 'z')
                    t += s[i++];

                ss.push(t);
            }
            else if(s[i] == ']')
            {
                string t = ss.top();
                ss.pop();
                int j = si.top();
                si.pop();

                while(j--)
                {
                    ss.top() += t;
                }
                i++; // 跳过右括号
            }
            else
            {
                string t = "";
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                    t += s[i++];

                ss.top() += t;
            }
        }
        return ss.top();
    }
};

验证栈序列

题目：验证栈序列

思路

用一个栈来模拟这个过程，最后栈为空则说明相匹配，否则说明不匹配

• 用i来遍历pop数组，确定要出栈的元素
• 判断栈顶元素是否等于要出栈的元素，如果相等则出栈，并i++到下一个要出栈的元素上

class Solution 
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        stack<int> s;
        int n = popped.size();
        int i = 0; // 标志位：确定要出栈的元素
        for(auto ch : pushed)
        {
            s.push(ch);
            // 判断栈顶元素是否等于要出栈的元素，如果相等则出栈，并将标志位挪到下一个要出栈的元素上
            while(s.size() && s.top() == popped[i]) 
            {
                s.pop();
                i++;
            }
        }

        return s.empty(); 
    }
};