栈算法相关的常见算法题目如下：

括号匹配问题

给定一个只包括(、)、{、}、[、]的字符串s，判断字符串是否有效。有效字符串需满足：左括号必须用相同类型的右括号闭合，左括号必须以正确的顺序闭合。例如输入s = "()(){}"，输出true。

最小栈问题

设计一个支持push、pop、top操作，并能在常数时间内检索到最小元素的栈。需要实现MinStack类，包含MinStack()初始化堆栈对象、void push(int val)将元素val推入堆栈、void pop()删除堆栈顶部的元素、int top()获取堆栈顶部的元素、int getMin()获取堆栈中的最小元素等操作。

最大栈问题

设计一个最大栈数据结构，既支持栈操作，又支持查找栈中最大元素。实现MaxStack类，包含MaxStack()初始化栈对象、void push(int x)将元素x压入栈中、int pop()移除栈顶元素并返回这个元素、int top()返回栈顶元素，无需移除、int peekMax()检索并返回栈中最大元素，无需移除、int popMax()检索并返回栈中最大元素，并将其移除等操作。

表达式求值问题

给定一个包含+、-、*、/的表达式字符串，计算表达式的值。例如给定字符串"3+2*2"，返回7。

字符串解码问题

给定一个经过编码的字符串，返回它解码后的字符串。编码规则为k[encoded_string]，表示其中方括号内部的encoded_string正好重复k次。例如输入s = "3[a2[c]]"，输出"accaccacc"。

逆波兰表达式求值问题

逆波兰表达式是一种后缀表达式，将运算符紧跟在操作数之后。给定一个逆波兰表达式，计算其结果。例如输入["2","1","+","3","*"]，返回9，即(2 + 1) * 3 = 9。

直方图最大矩形面积问题

给定一个直方图，求最大的矩形面积。例如给定直方图高度数组[2,1,5,6,2,3]，最大矩形面积为10。

迷宫问题

在迷宫中寻找从起点到终点的路径，可以用栈来记录路径，方便回溯。

比较含退格的字符串问题

比较两个字符串在退格后是否相同。例如输入s = "ab#c"，t = "ad#c"，返回true，因为退格后都为"ac"。

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

给定一个字符串，删除其中所有相邻的重复项。例如输入s = "abbaca"，返回"ca"。

#include <iostream>
#include <stack>
using namespace std;

int main() {
	// 定义一个整数变量 n，用于存储输入的十进制数
	int n;
	// 从标准输入读取一个十进制数
	cin >> n;
	// 定义一个存储整数的栈 st，用于存储二进制转换的结果
	stack<int> st;
	
	// 除 R 取余，倒序取整，将十进制数转换为二进制数
	while (n!= 0) {
		// 将 n 除以 2 的余数压入栈中
		st.push(n % 2);
		// 将 n 更新为 n 除以 2 的商
		n /= 2;
	}
	
	// 遍历栈，将栈中的元素依次弹出并输出
	while (!st.empty()) {
		// 输出栈顶元素
		cout << st.top();
		// 弹出栈顶元素
		st.pop();
	}
	// 输出换行符
	cout << endl;
	
	return 0;
}

以下是在 C++ 中实现栈的基本操作（入栈和出栈）的代码示例：

#include <iostream>
#include <stack>
using namespace std;

int main() {
    // 定义一个存储整数的栈
    stack<int> myStack;

    // 入栈操作
    cout << "入栈操作：" << endl;
    myStack.push(1);
    cout << "元素 1 入栈。" << endl;
    myStack.push(2);
    cout << "元素 2 入栈。" << endl;
    myStack.push(3);
    cout << "元素 3 入栈。" << endl;

    // 输出栈的大小
    cout << "栈的当前大小：" << myStack.size() << endl;

    // 出栈操作
    cout << "出栈操作：" << endl;
    if (!myStack.empty()) {
        cout << "栈顶元素：" << myStack.top() << " 正在出栈。" << endl;
        myStack.pop();
    }
    if (!myStack.empty()) {
        cout << "栈顶元素：" << myStack.top() << " 正在出栈。" << endl;
        myStack.pop();
    }
    if (!myStack.empty()) {
        cout << "栈顶元素：" << myStack.top() << " 正在出栈。" << endl;
        myStack.pop();
    }

    // 再次输出栈的大小
    cout << "栈的当前大小：" << myStack.size() << endl;

    return 0;
}

代码解释：

1. 头文件和命名空间：

   • #include <iostream>：提供输入输出功能，使用 cout 进行输出。
   • #include <stack>：使用 stack 容器。
   • using namespace std;：使用 std 命名空间，方便使用 stack、cout 等。

2. 定义栈：

   • stack<int> myStack;：创建一个存储整数的栈。

3. 入栈操作：

   • myStack.push(1);：将元素 1 压入栈中，同理可以将其他元素入栈。
   • cout << "元素 1 入栈。" << endl;：输出入栈信息。

4. 输出栈的大小：

   • cout << "栈的当前大小：" << myStack.size() << endl;：使用 size() 方法获取栈的当前元素数量。

5. 出栈操作：

   • if (!myStack.empty())：在出栈之前，先检查栈是否为空，因为对空栈进行出栈操作会导致未定义行为。
   • cout << "栈顶元素：" << myStack.top() << " 正在出栈。" << endl;：使用 top() 方法获取栈顶元素并输出。
   • myStack.pop();：使用 pop() 方法将栈顶元素出栈。

注意事项：

• 在进行 pop() 操作前，一定要使用 empty() 方法检查栈是否为空，否则会导致程序错误。
• top() 方法返回栈顶元素，但不会将其从栈中移除；而 pop() 方法会移除栈顶元素。

如果你想将这些操作封装在函数中，可以这样做：

#include <iostream>
#include <stack>
using namespace std;

// 入栈函数
void pushToStack(stack<int>& s, int value) {
    s.push(value);
    cout << "元素 " << value << " 入栈。" << endl;
}

// 出栈函数
void popFromStack(stack<int>& s) {
    if (!s.empty()) {
        cout << "栈顶元素：" << s.top() << " 正在出栈。" << endl;
        s.pop();
    } else {
        cout << "栈为空，无法出栈。" << endl;
    }
}

int main() {
    stack<int> myStack;

    // 入栈操作
    pushToStack(myStack, 1);
    pushToStack(myStack, 2);
    pushToStack(myStack, 3);

    // 输出栈的大小
    cout << "栈的当前大小：" << myStack.size() << endl;

    // 出栈操作
    popFromStack(myStack);
    popFromStack(myStack);
    popFromStack(myStack);
    popFromStack(myStack); // 尝试对空栈出栈

    return 0;
}

代码解释：

1. 入栈函数 pushToStack：

   • void pushToStack(stack<int>& s, int value)：接收一个栈的引用和要入栈的值。
   • s.push(value);：将值压入栈中。
   • cout << "元素 " << value << " 入栈。" << endl;：输出入栈信息。

2. 出栈函数 popFromStack：

   • void popFromStack(stack<int>& s)：接收一个栈的引用。
   • 先检查栈是否为空，不为空时输出栈顶元素并出栈，为空时输出相应信息。

通过这些示例，你可以掌握 C++ 中栈的基本操作，包括入栈、出栈操作，以及如何将它们封装在函数中，使代码更具可读性和可维护性。

以下是一个使用 C++ 栈来解决括号匹配问题的示例代码：

#include <iostream>
#include <stack>
#include <string>

using namespace std;

// 函数用于检查括号是否匹配
bool isBalanced(string str) {
    stack<char> s;
    for (char c : str) {
        if (c == '(' || c == '[' || c == '{') {
            s.push(c);  // 将左括号压入栈中
        } else if (c == ')') {
            if (s.empty() || s.top()!= '(') {
                return false;  // 不匹配的右括号或栈为空
            }
            s.pop();  // 匹配成功，弹出栈顶元素
        } else if (c == ']') {
            if (s.empty() || s.top()!= '[') {
                return false;  // 不匹配的右中括号或栈为空
            }
            s.pop();  // 匹配成功，弹出栈顶元素
        } else if (c == '}') {
            if (s.empty() || s.top()!= '{') {
                return false;  // 不匹配的右大括号或栈为空
            }
            s.pop();  // 匹配成功，弹出栈顶元素
        }
    }
    return s.empty();  // 最终栈应为空表示括号匹配
}

int main() {
    string str1 = "([{}])";
    string str2 = "([)]";
    if (isBalanced(str1)) {
        cout << str1 << " 的括号是匹配的。" << endl;
    } else {
        cout << str1 << " 的括号不匹配。" << endl;
    }
    if (isBalanced(str2)) {
        cout << str2 << " 的括号是匹配的。" << endl;
    } else {
        cout << str2 << " 的括号不匹配。" << endl;
    }
    return 0;
}

代码解释：

1. 头文件和命名空间：

   • #include <iostream>：提供输入输出功能，使用 cout 和 cin。
   • #include <stack>：使用 stack 容器。
   • #include <string>：处理字符串。
   • using namespace std;：使用 std 命名空间。

2. isBalanced 函数：

   • stack<char> s;：创建一个存储字符的栈。
   • 遍历输入的字符串 str 中的每个字符 c：
     • 如果 c 是左括号 (, [, 或 {，将其压入栈中。
     • 如果 c 是右括号 ), ], 或 }，检查栈是否为空或者栈顶元素是否与之匹配。如果不匹配或者栈为空，返回 false。
     • 若匹配，将栈顶元素弹出。
   • 最终，如果栈为空，返回 true，表示括号匹配，否则返回 false。

3. main 函数：

   • 定义两个测试字符串 str1 和 str2。
   • 调用 isBalanced 函数检查括号是否匹配，并输出结果。

这个示例展示了如何使用栈来解决括号匹配问题，栈在处理这类具有后进先出特性的问题时非常有用。以下是另一个示例，使用栈来实现逆波兰表达式（后缀表达式）求值：

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
#include <cstdlib>  // 用于 atoi 函数

using namespace std;

// 计算后缀表达式的值
int evaluatePostfix(string exp) {
    stack<int> s;
    stringstream ss(exp);
    string token;
    while (ss >> token) {
        if (isdigit(token[0])) {
            s.push(atoi(token.c_str()));  // 将数字字符串转换为整数并压入栈中
        } else {
            int operand2 = s.top(); s.pop();
            int operand1 = s.top(); s.pop();
            if (token == "+") s.push(operand1 + operand2);
            else if (token == "-") s.push(operand1 - operand2);
            else if (token == "*") s.push(operand1 * operand2);
            else if (token == "/") s.push(operand1 / operand2);
        }
    }
    return s.top();  // 最终结果在栈顶
}

int main() {
    string exp = "2 3 + 4 *";  // 后缀表达式 (2 + 3) * 4
    cout << "后缀表达式 " << exp << " 的结果是: " << evaluatePostfix(exp) << endl;
    return 0;
}

代码解释：

1. evaluatePostfix 函数：
   • stack<int> s;：创建一个存储整数的栈。
   • stringstream ss(exp);：将字符串 exp 按空格分隔为多个部分。
   • 遍历分隔后的元素 token：
     • 如果是数字，将其转换为整数并压入栈中。
     • 如果是运算符，从栈中弹出两个操作数，根据运算符计算结果，将结果压入栈中。
   • 最终返回栈顶元素，即为结果。

这些示例展示了栈在不同问题中的应用，你可以根据这些示例理解栈的使用方法，并将其应用到其他问题中，如实现深度优先搜索算法等。

#include <iostream>
#include <stack>
using namespace std;

// 定义一个存储整数的栈 st
stack<int > st;

int main() {
	// 将元素 56 压入栈 st 中
	st.push(56);
	// 将元素 67 压入栈 st 中
	st.push(67);
	// 将元素 123 压入栈 st 中
	st.push(123);
	
	// 输出栈顶元素的值，此时为 123
	cout<<st.top()<<endl;
	// 弹出栈顶元素，此时栈顶元素从 123 变为 67
	st.pop();
	// 输出新的栈顶元素的值，此时为 67
	cout<<st.top()<<endl;
	return 0;
}

以下是一份适用于信息学竞赛算法比赛的 C++ 栈（stack）教程：

一、什么是栈？

栈是一种特殊的数据结构，它遵循“后进先出（LIFO, Last In First Out）”的原则。可以把栈想象成一个一端封闭的管道，你只能从开口的一端放入或取出物品。就像叠罗汉，最后一个站上去的人会是第一个下来的人。

二、在 C++ 中使用栈

首先，你需要包含相应的头文件，并且使用 std 命名空间：

#include <iostream>
#include <stack>
using namespace std;

三、栈的基本操作

1. 创建一个栈

你可以创建一个存储整数的栈，像这样：

stack<int> st;

你可以创建存储其他类型的栈，比如存储字符：

stack<char> charStack;

或者存储自定义结构体：

struct Point {
    int x, y;
};
stack<Point> pointStack;

2. 元素入栈（push）

使用 push() 操作可以将元素添加到栈顶：

st.push(5);  // 把 5 这个元素放入栈中
st.push(10); // 再把 10 放进去
st.push(15); // 再放 15

这样，栈里现在的元素从上到下就是 15，10，5。

3. 查看栈顶元素（top）

使用 top() 操作可以查看栈顶元素，但不会将它从栈中取出：

if (!st.empty()) {
    cout << "栈顶元素是: " << st.top() << endl; 
}

注意：使用 top() 前，一定要先检查栈是否为空，因为对空栈使用 top() 会导致程序出错哦！

4. 元素出栈（pop）

使用 pop() 操作可以将栈顶元素移除：

if (!st.empty()) {
    st.pop(); // 移除栈顶元素
}

注意：同样，使用 pop() 前要确保栈不为空，否则会出错。

5. 检查栈是否为空（empty）

使用 empty() 操作可以检查栈是否为空：

if (st.empty()) {
    cout << "栈是空的。" << endl;
} else {
    cout << "栈不是空的。" << endl;
}

6. 查看栈的大小（size）

使用 size() 操作可以查看栈中元素的数量：

cout << "栈中元素的数量是: " << st.size() << endl;

四、栈的应用

1. 括号匹配问题

在信息学竞赛中，栈经常用来解决括号匹配问题，例如判断一个表达式中的括号是否匹配：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

bool isBalanced(string str) {
    stack<char> st;
    for (char c : str) {
        if (c == '(' || c == '[' || c == '{') {
            st.push(c);
        } else if (c == ')') {
            if (st.empty() || st.top()!= '(') return false;
            st.pop();
        } else if (c == ']') {
            if (st.empty() || st.top()!= '[') return false;
            st.pop();
        } else if (c == '}') {
            if (st.empty() || st.top()!= '{') return false;
            st.pop();
        }
    }
    return st.empty();
}

int main() {
    string expression = "(([{}]))";
    if (isBalanced(expression)) {
        cout << "括号匹配" << endl;
    } else {
        cout << "括号不匹配" << endl;
    }
    return 0;
}

解释：

• 遍历字符串中的每个字符。
• 遇到左括号 (, [, { 就入栈。
• 遇到右括号时，检查栈顶元素是否与之匹配，如果不匹配或栈为空，则括号不匹配；如果匹配，就出栈。
• 最后检查栈是否为空，如果为空则括号匹配，否则不匹配。

2. 函数调用模拟

栈还可以模拟函数调用的过程，例如：

#include <iostream>
#include <stack>
#include <string>
using namespace std;

void funcA() {
    cout << "进入函数 A" << endl;
}

void funcB() {
    cout << "进入函数 B" << endl;
    funcA();
    cout << "离开函数 B" << endl;
}

int main() {
    stack<string> callStack;
    callStack.push("funcB");
    while (!callStack.empty()) {
        string func = callStack.top();
        callStack.pop();
        if (func == "funcB") {
            funcB();
        } else if (func == "funcA") {
            funcA();
        }
    }
    return 0;
}

解释：

• 我们将函数名称压入栈中，然后依次弹出调用，模拟函数调用的过程。

3. 简单的计算表达式求值（后缀表达式）

后缀表达式是一种不需要括号的表达式表示方式，例如 2 3 + 4 * 表示 (2 + 3) * 4。可以使用栈来计算后缀表达式的值：

#include <iostream>
#include <stack>
#include <string>
#include <sstream>
using namespace std;

int evaluatePostfix(string exp) {
    stack<int> st;
    stringstream ss(exp);
    string token;
    while (ss >> token) {
        if (isdigit(token[0])) {
            st.push(stoi(token));
        } else {
            int operand2 = st.top(); st.pop();
            int operand1 = st.top(); st.pop();
            if (token == "+") st.push(operand1 + operand2);
            else if (token == "-") st.push(operand1 - operand2);
            else if (token == "*") st.push(operand1 * operand2);
            else if (token == "/") st.push(operand1 / operand2);
        }
    }
    return st.top();
}

int main() {
    string exp = "2 3 + 4 *";
    cout << evaluatePostfix(exp) << endl; // 输出 20
    return 0;
}

解释：

• 遍历后缀表达式的元素。
• 如果是数字，入栈。
• 如果是运算符，从栈中弹出两个操作数，根据运算符进行计算，结果入栈。

五、总结

• 栈是一种非常有用的数据结构，在信息学竞赛中可以解决很多问题，如括号匹配、函数调用模拟、表达式求值等。
• 掌握 push()，pop()，top()，empty()，size() 这些基本操作，你就可以开始使用栈解决很多有趣的算法问题啦 。

希望这个教程可以帮助你在信息学竞赛中更好地运用栈这个强大的数据结构，让你在比赛中取得好成绩哦 ！

注意事项

• 在使用 top() 和 pop() 操作时，要确保栈不为空，否则程序会出错。
• 对于不同的问题，灵活运用栈的特性，比如存储不同类型的数据，实现不同的算法逻辑。