C++ 栈OJ_栈 c++ oi-CSDN博客

本文链接：https://blog.csdn.net/m0_73800602/article/details/136578762

本文详细介绍了栈在算法中的应用，包括中缀表达式转后缀表达式、括号匹配、深度优先搜索、逆波兰表达式计算、函数调用实现、迷宫求解以及字符串处理问题，展示了栈的后进先出特性和在解决这些问题中的作用。

摘要生成于 C知道，由 DeepSeek-R1 满血版支持，前往体验 >

栈的应用场景：

1、 1047. 删除字符串中的所有相邻重复项

栈的应用场景：

表达式求值：栈常用于中缀表达式转换为后缀表达式，或者用于计算后缀表达式的值。栈可以帮助处理运算符的优先级和结合性。
括号匹配：栈可以用来检查表达式中的括号是否匹配。遍历表达式，遇到左括号时将其入栈，遇到右括号时与栈顶元素匹配，如果匹配则出栈，否则括号不匹配。
深度优先搜索（DFS）：在树或图的深度优先搜索中，栈通常用于存储待访问的节点。每次访问一个节点时，将其邻居节点入栈，以便后续继续深度遍历。
逆波兰表达式：栈可以用于计算逆波兰表达式（后缀表达式）。遍历表达式，遇到操作数则入栈，遇到操作符则从栈中弹出操作数进行计算。
函数调用：在编程语言中，函数调用的实现通常使用栈。每次调用函数时，将函数参数、返回地址等信息压入栈中，函数返回时再从栈中弹出这些信息。
迷宫求解：栈可以用于迷宫求解算法中，记录走过的路径。在搜索迷宫的过程中，将当前位置入栈，如果遇到死路则回溯到上一个位置。

这些是栈在算法中常见的应用场景，栈的特性使其在处理递归、回溯、以及需要后进先出（LIFO）顺序的问题时非常有用。

1、 1047. 删除字符串中的所有相邻重复项

思路：符合后进先出，⽤数组模拟栈。

class Solution {
public:
    string removeDuplicates(string s) {
        string ret;
        for (auto ch : s) {
            //有元素才能删除
            if (ret.size() && ret.back() == ch) {
                ret.pop_back();
            } else {
                ret += ch;
            }
        }
        retu