【栈数据结构应用解析：常见算法题详细解答】—— Leetcode

用户11286421

发布于 2025-03-15 21:01:17

7200

代码可运行

文章被收录于专栏：学习学习

运行总次数：0

代码可运行

栈的模拟实现

#include <iostream>

using namespace std;

const int N = 1e5 + 10;

// 创建栈
int stk[N], n;

// 进栈 - 本质就是顺序表里面的尾插
void push(int x)
{
    stk[++n] = x;
}

// 出栈 - 顺序表的尾删操作
void pop()
{
    n--;
}

// 查询栈顶元素
int top()
{
    return stk[n];
}

// 判断是否为空
bool empty()
{
    return n == 0;
}

// 查询有效元素的个数
int size()
{
    return n;
}

int main()
{
    for(int i = 1; i <= 10; i++)
    {
        push(i);
    }

    // 当栈不为空的时候
    while(size()) // while(!empty()) 
    {
        cout << top() << endl;
        pop();
    }


    return 0;
}

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

思路：我们通过模拟栈遍历字符串 s，逐个字符处理。当遇到当前字符和 ret（结果字符串）末尾的字符相同时，说明这两个字符相同且相邻，因此可以将末尾的字符移除（使用 pop_back()），实现删除重复字符的效果。否则，将当前字符添加到 ret 的末尾。最终返回 ret 作为结果。这个方法有效地将相邻的重复字符一一删除，直到整个字符串处理完成。

class Solution 
{
public:
    string removeDuplicates(string s) 
    {
        // 创建一个空的字符串 ret 用于存储结果
        string ret;

        // 遍历输入字符串 s 中的每一个字符
        for(char ch : s)
        {
            // 如果 ret 非空，并且 ret 的最后一个字符等于当前字符
            if(ret.size() && ret.back() == ch) 
                // 移除 ret 末尾的字符（即删除相邻的重复字符）
                ret.pop_back();
            else 
                // 否则，将当前字符添加到 ret 末尾
                ret += ch;
        }

        // 返回最终去重后的字符串
        return ret;
    }
};

比较含退格的字符串

思路：本题要求我们比较两个字符串 s 和 t 在应用退格符 # 后是否相同。退格符 # 表示删除字符串中前一个有效字符。如果遇到 #，我们就模拟删除操作，即当字符串非空时，删除最后一个有效字符。最终通过比较处理后的两个字符串来判断它们是否相等。此方法是通过两个字符串 s1 和 s2 来分别存储 s 和 t 经过退格操作后的结果，最后直接比较这两个字符串。

class Solution 
{
public:
    bool backspaceCompare(string s, string t) 
    {
        // 创建两个空字符串 s1 和 s2 用于存储去除退格符后的结果
        string s1, s2;

        // 遍历字符串 s 处理退格符
        for(char ch : s)
        {
            if(ch == '#') // 如果遇到退格符
            {
                if(s1.size()) // 如果 s1 非空
                {
                    s1.pop_back(); // 删除 s1 最后一个字符
                }
            } 
            else s1 += ch; // 否则，将当前字符添加到 s1
        } 

        // 遍历字符串 t 处理退格符
        for(char ch : t)
        {
            if(ch == '#') // 如果遇到退格符
            {
                if(s2.size()) // 如果 s2 非空
                {
                    s2.pop_back(); // 删除 s2 最后一个字符
                }
            } 
            else s2 += ch; // 否则，将当前字符添加到 s2
        } 

        // 比较两个处理后的字符串是否相同
        if(s2 == s1) return true;
        else return false;
    }
};

基本计算器||

思路：这道题目要求我们计算一个字符串表示的算式，支持加、减、乘、除四种基本运算，并且按照优先级顺序处理。为了正确计算，我们需要用栈来处理运算符的优先级。基本的思路如下：

遍历字符串：我们遍历字符串的每一个字符，遇到空格时跳过，遇到数字时读取完整的数字，遇到运算符时处理当前运算，并记录当前运算符。
使用栈存储中间结果：对于加法和减法，我们将结果加入栈中；对于乘法和除法，我们需要在栈顶进行计算（因为乘法和除法的优先级更高）。
最终计算：计算完所有数字和运算符后，栈中的值就是我们需要的结果，将栈中的值加和得到最终答案。

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 
                    st.back() /= tmp; // 除法：栈顶元素与当前数字相除
            }
            else 
            {
                // 如果是运算符，更新当前操作符
                op = s[i];
                i++;
            }
        }
        
        // 计算栈中所有数字的和
        int ret = 0;
        for(auto ch : st) 
            ret += ch;

        return ret;
    }
};

字符串解码

思路：这道题目要求解码一个类似 “3[a2[c]]” 的字符串。通过递归或栈的方式，可以逐步处理字符串中的数字、字母和括号。基本思路如下：

栈的使用：我们使用两个栈来辅助解码：

st 栈用于存储解码过程中的中间字符串。 nums 栈用于存储数字（即每次遇到数字时，记录数字，表示该数字代表后续括号中的字符串重复次数）。数字处理：当我们遇到数字时，我们会计算出当前数字（可能是多位数），并将其压入 nums 栈。左括号 [ 处理：当我们遇到左括号时，表示一个新的子字符串的开始，此时将当前已处理的字符串压入 st 栈，开始处理新的一段字符串。右括号 ] 处理：当我们遇到右括号时，表示当前子字符串的结束。此时，弹出 st 栈顶的字符串和 nums 栈顶的数字。数字 k 代表当前子字符串应该重复的次数。我们将字符串重复 k 次后，合并到栈顶的字符串。字母处理：当我们遇到字母时，将其直接添加到栈顶的字符串中。

最后，栈中存储的是解码后的字符串，返回栈顶的字符串即为最终结果。

class Solution 
{
public:
    string decodeString(string s) 
    {
        // 栈 st 用于存储解码过程中的中间字符串，栈 nums 用于存储数字
        stack<string> st;
        stack<int> nums;
        
        st.push("");  // 初始栈顶为空字符串
        int i = 0, n = s.size();
        
        while(i < n)
        {
            // 处理数字：获取一个完整的数字（可能是多位数）
            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');
                }
                nums.push(tmp); // 将数字压入 nums 栈
            }
            // 处理左括号 '['，表示进入一个新的子字符串
            else if(s[i] == '[')
            {
                i++;
                string tmp = "";
                // 读取子字符串中的字母
                while(s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.push(tmp); // 将字母子串压入栈中
            }
            // 处理右括号 ']'，表示子字符串结束，进行重复操作
            else if(s[i] == ']')
            {
                string tmp = st.top();
                st.pop();  // 弹出栈顶字符串（当前子字符串）
                int k = nums.top();
                nums.pop();  // 弹出栈顶数字（重复次数）

                // 重复当前子字符串 k 次，并合并到栈顶字符串中
                while(k--)
                {
                    st.top() += tmp;
                }
                i++; // 处理下一个字符
            }
            // 处理字母，直接添加到栈顶字符串
            else
            {
                string tmp;
                while(i < n && s[i] >= 'a' && s[i] <= 'z')
                {
                    tmp += s[i];
                    i++;
                }
                st.top() += tmp; // 将字母添加到栈顶字符串中
            }
        }
        
        return st.top();  // 最终返回栈顶的解码结果
    }
};

验证栈序列

思路：
模拟栈的操作：我们遍历 pushed 序列，将每个元素压入栈中。每次压栈后，检查栈顶元素是否与 popped[j] 相等。如果相等，说明栈顶元素可以被弹出，接着弹出栈顶元素，并将 j 增加。一直进行上述操作，直到遍历完整个 pushed 序列。
最终判断：如果遍历完 pushed 序列后，栈为空，且 j 达到了 popped 序列的末尾，说明 popped 是可能的弹出序列。如果栈不为空，或者 j 没有达到 popped 的末尾，则说明不可能通过栈操作生成 popped。

class Solution 
{
public:
    bool validateStackSequences(vector<int>& pushed, vector<int>& popped) 
    {
        int i = 0, j = 0, n = popped.size();  // i 是 pushed 的索引，j 是 popped 的索引
        stack<int> st;  // 栈，用于模拟压栈和弹栈操作
        
        // 遍历 pushed 序列
        while(i < n)
        {
            st.push(pushed[i++]);  // 将当前元素压入栈中
            
            // 检查栈顶元素是否等于 popped[j]
            while(st.size() && st.top() == popped[j])
            {
                st.pop();  // 如果栈顶元素等于 popped[j]，则弹出栈顶
                j++;  // 更新 popped 序列的索引
            }
        }
        
        // 如果栈为空，且所有元素都能匹配成功，则返回 true
        return st.empty();
    }
};

栈算法的核心思路：