栈是一种“FILO”的线性数据结构。

栈只有一段能够进出元素，我们称这端为栈顶，另一端为栈底。

进栈：从栈顶插入元素；

出栈：从栈顶取出元素；

可以使用数组实现栈进栈和出栈。

int st[SIZE],top=0;
void push(int x)  //入栈 
{
	st[++top]=x;
}
int top()  //取栈顶 
{
	return st[top];
}
void pop()  //出栈 
{
	--top;
}

也可以使用STL中stack实现进栈和出栈。

#include<stack>st;
st.push(x);  //入栈 
st.top();    //取栈顶 
st.pop();    //出栈 

例1：进出栈序列问题

给定 1-N 这个 N 个整数和一个无限大的栈，每个数都要进栈并出栈一次。如果进栈的顺序为 1,2，...，N ,那么可能的出栈序列有多少种？

P1044 [NOIP2003 普及组] 栈

方法一：递推 $O(N^2)$

只需要计算可能出栈序列有多少种，并不关心具体方案，于是我们可以使用递推直接进行统计。

设 $f_n$ 表示进栈顺序为 $1,2,3,..n$ 时出栈序列总数，根据求解递推的问题的思路，我们想办法把原问题分解成若干个类似的子问题。

考虑出栈序列中“ $1$ ”排的位置，如果最后“ $1$ ”排在出栈第 $k$ 个位置，那整个序列进出栈过程就是：

1. $1$ 进栈；
2. $2 \dots k$ 这 $k-1$ 个数按照某种顺序进出栈。
3. $1$ 出栈，会排在出栈序列第 $k$ 个位置。
4. $k+1 \dots n$ 这 $n-k$ 个数按照某种顺序进出栈。

那个整个问题就会被 $‘1’$ 分成了“ $k-1$ 个数进出栈”和“ $n-k$ 个数进出栈”这两个子问题，可以得到递推公式：

$f_n ={\textstyle \sum_{k=1}^{n}} f_{k-1} *f_{n-k}$

方法二：动态规划 $O(N^2)$

任何一个时刻，决定出栈方案数的是有多少个数尚未入栈、有多少个数还在栈里，这些数具体是哪些并不重要。

那么定义 $f[i][j]$ 表示有 $i$ 个数尚未进栈，有 $j$ 个数还在栈里，有 $n-i-j$ 个数已经出栈的方案总数。

最终状态，所有数已经出栈，顺序确定，所以边界： $f[0][0]=1$

我们需要求出初始状态下，即所有数尚未进栈时，可以到达上述边界的方案总数，所以目标为：$f[N][0]$

每一步两种决策分别是“把一个数进栈”和“把栈顶的数出栈”，所以递推公式就是：

$f[i][j]=f[i-1][j+1]+f[i][j-1]$

方法三：数学 $O(N)$

该问题等价于求第 $N$ 项 $Catalan$ 数， $C_{2N}^{N}/(N+1)$

---

应用一：表达式求值

算术表达式分为前缀、中缀、后缀三种表示方法。

中缀表达式，是最常见的表达式，例如： 3*（5-2）+1

前缀表达式，又叫波兰式，将运算符放在参与运算数字之前，形如“op A B”,op 是运算符，A和B是另外两个前缀表达式，例如：+ * 3 - 5 2 1

后缀表达式，又叫逆波兰式，形如“A B op”,例如： 3 5 2 - * 1 +

前缀和后缀表达式是递归定义的，在求值时，也是先递归求出A和B的值，两者再做op运算，得到结果。 这两种表达式不需要使用括号，运算方案唯一确定，对于计算机求值最容易，可以使用栈来$O(N)$求出它的值。

后缀表达式求值
1.建立一个用于存数的栈，逐一扫描该后缀表达式中的元素。
（1）遇到数字，直接进栈。
（2）遇到运算符，弹出栈顶两个数，进行计算，将结果入栈。
2.扫描完成后，栈中剩下的一个数，就是该表达式的值。

如果想让计算机求解常用的中缀表达式，可以把中缀表达式转化为后缀表达式，再使用上述方法求值。这个转化复杂度为$O(N)$

中缀转后缀表达式
1.读入表达式，给表达式外添加一层括号。（这样最终运算符栈就会被清空）
2.创建一个用于存储运算符的栈，逐一扫描中缀表达式的元素。
（1）遇到数字输出该数字。
（2）遇到左括号，左括号直接入栈。
（3）遇到右括号，不断取出栈顶运算符并输出，直到栈顶为左括号，然后把左括号出栈。
（4）遇到运算符，只要栈顶运算符优先级不低于新符号，就不断取出栈顶符号并输出，直到栈为空或者栈顶优先级低于新符号，最后把新符号进栈。优先级为：乘除》加减》左括号。
3.由于一开始表达式添加了括号，最终操作符栈为空。输出的表达式就是中缀对应的后缀表达式。

也可以直接求中缀表达式的值。

中缀表达式求值
1.读入表达式，给表达式外添加一层括号。
2.创建两个栈，一个用于存储运算符的符号栈，一个用于存储数值的数字栈。然后逐一扫描中缀表达式。
（1）遇到数字直接进入数字栈。
（2）遇到左括号，左括号直接进入运算符栈。
（3）遇到右括号，不断取出两个数字栈顶两数字和操作符栈栈顶运算符，运算结束后，将运算结果压入数字栈，直到栈顶是左括号，然后弹出左括号。（右括号实际并不入栈）
（4）遇到运算符，如果栈顶运算符优先级不低于新运算符，循环取出两个数字栈中数字与一个运算符，运算后压入数字栈，直到运算符栈顶运算符低于新运算符或者运算符栈空。然后将运算符压入符号栈。
3.由于一开始表达式添加了括号，最终操作符栈为空，输出数字栈顶就是中缀表达式的值。

例题1：SP4 ONP - Transform the Expression

中缀表达式转后缀表达式的模板题，参考代码：点击

例题2：P1981 [NOIP2013 普及组] 表达式求值

中缀表达式求值，参考代码：点击

---

应用二：单调栈

单调栈即满足单调性的栈结构。

例题3：P2947 [USACO09MAR]Look Up S

给定 $n$ 个数，依次为 $H_i$ ，对于每一个位置 $i$，寻找位置 $j(j>i)$，使得 $H_j>H_i$ 。

分析：如果直接暴力查找，复杂度为 $O(n^2)$ 。我们发现中间矮的，对i之后的也是无效的，那么只需要保留有效高度对应位置。创建一个栈（保存下标位置），$i$ 从大到小，从栈底到栈顶依次递减，对于每一个 $H_i$，如果栈顶小于当前的 $H_i$,循环出栈,直到栈顶大于当前的 $H_i$,此时，栈顶就是当前 $i$ 对应的 $j$ ，如果栈为空，那答案为 $0$。

参考代码：点击

例题4：SP1805 HISTOGRA - Largest Rectangle in a Histogram

题意：给定 $n$ 宽度为 $1$ 的矩形，求包含于这些矩形的最大子矩形面积。

【分析】

可以维护一个从栈到栈顶单调递增的单调栈，以每个矩形的高度作为矩形的高度，并把宽度延伸到右边界，得到一个矩形，在所有这样的矩形面积中最大值就是答案。

如果下个矩形比前面矩形低，那么该矩形与之前矩形一起构成一块较大面积，这个较大矩形的高度不可能超过该矩形自己的高度。即上图中打叉部分是无用的。

而中间灰色三个矩形会依次弹出栈，在弹出栈的同时，高度就是它本身的高度，而宽度应该是之前弹栈宽度之和。

特别地，这个矮的矩形进栈，此时它的宽度是被它弹出栈的宽度之和+它本身的宽度。

算法过程：

创建一个栈，保存高度单调递增的的矩形，从左往右扫描每个矩形：

· 1.如果当前矩形比栈顶矩形高，直接进栈，栈顶矩形宽度为进栈矩形宽度；

· 2.否则不断取出栈顶，栈顶为空或者栈顶矩形的高度比当前矩形小。出栈时累加矩形宽度之和，每弹出一个矩形，就用弹出矩形的高度乘以累计矩形宽度去更新答案。 出栈结束后，把高度为当前矩形高度、宽度为累加矩形宽度+本身宽度入栈。

扫描结束后，我们再按照上述方法弹出栈中剩余矩形，为了简化，增加一个高度为 $0$ 的矩形 $a[n+1]$ ,避免扫描结束后栈中还有剩余矩形。

参考代码如下：

a[n+1]=tp=0;  //最后的高度增加0，可以弹出栈中所有矩形高度 
		
		for(int i=1;i<=n+1;i++)
		{
			if(a[i]>st[tp])
				st[++tp]=a[i],w[tp]=1;   //直接进栈 对应宽度就是本身宽度1 
			else
			{
				int width=0;
				while(st[tp]>a[i])       //栈顶矩形被后面更矮的弹出 高度是本身的高度 宽度是之后所有比它本身高的宽度之和 
				{
					width+=w[tp];        //累加求宽度之和 
					ans=max(ans,(long long)st[tp]*width);   //对应一个矩形 
					tp--;
				}
				st[++tp]=a[i];          //栈中高的被弹出  高度就是本身高度              
				w[tp]=width+1;          //但是宽度是所有弹出高度之和+1 
                //w[tp]本质上保存的是tp这个矩形之前所有比tp矩形高的矩形的宽度和
			}
		}

参考代码：点击

例题5：P6801 [CEOI2020] 花式围栏

题意：给定 $n$ 个矩形，高度为 $h_i$,宽度为 $w_i$,询问各种小矩形的个数。

分析：对于每一个矩形，如果宽度为 $w$,高度为 $h$,那么矩形个数就为 $C_w^2*C_h^2$，利用单调栈可以枚举每一个矩形，单独计算各自矩形个数，累加求和，但是由于矩形有重叠，每次计算需要将重叠的扣除。

栈中压入下标，每次弹出栈计算对应矩形对答案的贡献。 即： $ans+=(C_{h[tp]}^2-(C_{max(h_i,h[st.top()]}^2)*C_{width}^2$ , 其中 $C$ 为求组合,数, $tp$ 为弹栈矩形的下标(此时已经弹出)，$h_i$ 为当前矩形高度。

为何要扣除 $C_{max(h_i,h[st.top()]}^2$ ？就是要扣掉重复部分

为何是 $max(h_i,h[st.top())$ ，当栈顶 $h[st.top()]$ 大于 $h[i]$ ,当然高度是$h[st.top()]$，而当 $h[st.top()]$ 小于 $h[i]$，此时对应高度应该是 $h[i]$,因此要取 $max(h_i,h[st.top())$

参考代码：点击

例题6：P4147 玉蟾宫

题意简化：给定一个 $N*M$ 的由 $'F'$ 和 $‘R’$ 的矩形，求矩形中全部由 ‘F’ 构成的最大子矩形面积。

分析：如果将 $'F'$ 看成 $1$ ，$'R'$ 看作 $0$，对于每一列来说，连续的 $1$ 可以当做一个宽度为 $1$、高度为连续 $1$ 的个数的矩形条，矩形条合在一起求最大矩形。但是由于中间有 $0$，会将上面的矩形断开，枚举每一行，计算每一行矩形条对应的最大矩形面积。

参考代码：点击

---

学习完毕

{{ select(1) }}

• YES
• NO