一：基础操作复习：

特点：先进后出，栈顶可操作，栈底固定；

优点：栈顶操作插入删除的时间复杂度都是O(1)；

应用：逆序输出，括号匹配，（进制转换，函数调用栈—未学）；

基础操作：

stack<int> a;
a.push(x);//把x压入栈顶
a.pop();//删除栈顶元素
top();//返回栈顶元素
empty();//判断栈是否为空，若为空返回false，否则返回true；
size();//返回栈中元素个数

二：逆波兰表达式求值：

附题：P1449 后缀表达式 - 洛谷

思路：

1.建立栈，输入字符串；

2.遍历整个字符串；

（1）：遇到 ' . ' 跳过；

（2）：处理多位数；（注意自增的i处理问题！）

（3）：如果遇见运算符号，调出前两个入栈的元素做计算，所得结果再次压进去；

（4）：遇见@，break；

3.输出栈顶即为答案；

附代码：

#include <bits/stdc++.h>
using namespace std;

int main()
{
	stack<int> stk;
	string s;
	getline(cin, s);
	// 遍历整个字符串，遇到.跳过
	for (int i = 0; i < s.size(); i++)
	{ // 使用 for 循环替代 while 循环
		if (s[i] == '.')
		{
			continue;
		}
		if (s[i] >= '0' && s[i] <= '9')
		{ // 处理多位数
			int num = 0;
			while (i < s.size() && s[i] >= '0' && s[i] <= '9')
			{ // 内部 while 循环处理多位数
				// 一直累加直到遇见符号停止
				num = num * 10 + (s[i] - '0');
				i++;
			}
			stk.push(num);
			i--; // 因为 for 循环会自增 i，这里需要回退一步
		}
		else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
		{
			int a = stk.top();
			stk.pop();
			int b = stk.top();
			stk.pop();
			if (s[i] == '+')
				stk.push(b + a);
			else if (s[i] == '-')
				stk.push(b - a);
			else if (s[i] == '*')
				stk.push(b * a);
			else if (s[i] == '/')
				stk.push(b / a);
		}
		else if (s[i] == '@')
		{
			break;
		}
	}
	cout << stk.top();
	return 0;
}

三：单调栈：

定义：栈内元素始终保持单调递增或者单调递减

• 单调递增栈：栈内元素从栈底到栈顶递增；

• 单调递减栈：栈内元素从栈底到栈顶递减；

应用：

1：找到数组中每个元素的下一个更大（或更小）元素；

2：解决滑动窗口中的最大值问题；

操作规则：

1.遍历数组，对每个元素判断是否破坏栈的单调性；

2.如果破坏单调性，则弹出栈顶元素，直到满足单调性，再压入当前元素；

可以通过弹出元素的过程，找到当前元素与栈顶元素之间的大小关系；

模板；

stack<int> stk; // 定义一个栈
for (int i = 0; i < nums.size(); i++) {
    // 维护单调性：弹出比当前元素小的栈顶元素
    while (!stk.empty() && nums[i] > nums[stk.top()]) {
        int top = stk.top(); // 栈顶元素
        stk.pop(); // 弹出栈顶
        // 在这里处理栈顶元素的结果（例如记录下一个更大元素）
    }
    stk.push(i); // 将当前元素的下标压入栈
}