栈 (stack)

表达式求值
括号匹配（1种括号，只需要计数，多种需要栈）
单调栈（求凸包，求最大矩形）

中缀表达式：需要括号
后缀表达式
8 3 2 6 * + 5 / - 4 +
遇到数值入栈
遇到符号，拿出需要的操作数（一般是2），进行运算，放回去
最后应该剩下恰好一个数字。

CF81A Plug-in

https://codeforces.com/problemset/problem/81/A
输入一个字符串，把所有连续相同的2个字符删掉，问最后剩下什么。

Luogu P1165 日志分析

https://www.luogu.com.cn/problem/P1165
维护一个栈，支持加入，删除，询问栈中的最大值。

Luogu P1449 后缀表达式

https://www.luogu.com.cn/problem/P1449
输入一个后缀表达式，求值。

Luogu P5788 【模板】单调栈

https://www.luogu.com.cn/problem/P5788
输入一个数字，对于每个位置i，找到i之后第一个大于a[i]的位置。

agc005_a STring

https://atcoder.jp/contests/agc005/tasks/agc005_a
输入一个字符串，如果ST是这个字符串的子串，删去这个子串，直到ST不是这个字符串的子串。

stack:

表达式求值
括号匹配（1种括号，只需要计数，多种需要栈）
单调栈（求凸包，求最大矩形）

中缀表达式
需要括号

后缀表达式
8 3 2 6*+5/-4+
遇到数值入栈
遇到符号，拿出需要的操作数（一般是2），进行运算，放回去
最后应该剩下恰好一个数字。

维护一个数值栈
8 3 2 6
8 3 12
8 15
8 15 5
8 3
5
5 4
9

2类做法

O(n^2) 直接递归
找到最后一个执行的运算是什么
然后两边递归处理

按运算符优先级枚举，先枚举低优先级的（先枚举加减，再乘除，再乘方）
根据运算符结合性，如果加法这种的，从右向左扫
如果是乘方，从左向右
括号内的不算
特殊情况整体被一个括号包住了
(a + b + c)

a + b + c = (a + b) + c
a ** b ** c = a ** (b ** c)

栈
需要一个数值栈
需要一个符号栈

优先级小的可以让优先级大的运算
优先级相等（取决于结合性）
如果没有括号，这样做就可以了

a + b * c *

数值栈:a b c
符号栈:+ *

括号的处理
任何运算都不能让左括号(出栈，括号优先级最低
只有右括号遇到左括号会消掉
(a + b)

Stack

LIFO

expression evaluation
Catalan Number
Monotonic Stack

The number of paths from (0, 0) to (n, n) without touching (y = x + 1) =

The number of paths from (0, 0) to (n, n) - The number of paths from (0, 0) to (n, n) touching (y = x + 1)

C(2n, n) - C(2n, n-1) = C(2n,n) / (n+1)

http://oeis.org/A000108

(a + b) mod p = ((a mod p) + (b mod p)) mod p

(a- b) mod p = ((a mod p) - (b mod p)) mod p

(a * b) mod p = ((a mod p) * (b mod p)) mod p

(a / b) mod p = ((a mod p) * inv(b mod p)) mod p

2 * 1/2 = 1

x / 2 = x * (1/2)

2 * 4 mod 7 = 1

x / 2 mod 7 = x * 4 mod 7

Divided (1, 2, 3, .., n) to some sets.

The sets can not intersect with each other.

(1, 3) (2, 4)

(1, 4) (2) (3)

stated-compressed DP

P3668 [USACO17OPEN]Modern Art 2 G

1 2 1 2

vector we can access the i-th element.

stackwe can only access the top. we need to access the top two of the stack.

queue we can only access the front.

P6182 [USACO10OPEN]Time Travel S

The operations formed a tree.

栈

名称

栈(stack)是一种后进先出(LIFO, last in first out)的数据结构，这是一种非常基础的数据结构，在很多地方，尤其是DFS和单调栈中有广泛的应用。

实现

可以使用C++ STL中的stack实现，也可以自己模拟。

通常用一个数组和一个指针模拟一个栈，数组用于存储元素，指针top表示栈顶，入队时将top向后移动，出队时将top向前移动。

栈并不需要支持访问任意元素，所以在某些情况下会用链表模拟栈。（比如NOIP初赛）

具体使用

栈的用途比队列多一些。

表达式求值

凸包/凸壳

可以用来求凸包，但是因为凸包需要访问最后 $2$ 个元素，用以判断折线的方向，所以不能用STL的Stack

单调栈

可以用来解决最大矩形面积的问题。

递归

递归算法都会用到栈，只不过系统会自动维护。
如果想使用非递归算法，那么就需要自己实现栈了。

参考题目

Luogu P1175
表达式求值

Luogu P5155
凸壳

Luogu P1044
出栈序列数目，Catalan数。

Luogu P1739
判断括号是否匹配

Luogu P1449
后缀表达式求值

Luogu P1981
中缀表达式求值

Luogu P2947
用栈

Luogu P2866
用栈

POJ 1964
最大矩形面积

POJ 2559
最大矩形面积