栈

概述

栈是 OI 中常用的一种线性数据结构，它的特点是先进后出。

想象一下手枪弹架上弹的过程，先压入的子弹在弹夹最底部，后压入的子弹在上方。因此可以说先进入的子弹最后打出。

实现

数组模拟栈

创建一个数组用来储存元素，根据数据范围设定大小，例如 int stk[N];。

在栈中，我们更关心栈顶元素是谁，即关心栈顶元素所处数组的位置（下标）。

使用一个名为 $\textbf{top}$ 的变量指向栈顶元素的下标，初始化 $\textbf{top = 0}$ 意为栈内没有元素。（同时根据 $\textbf{top}$ 的值可以获取栈内有几个元素）

• 加入元素：首先让 $\textbf{top}$ 变量向右移动一位，然后对当前位置的元素赋值，通常写成 $\textbf{stk[++top] = x;}$
• 弹出栈顶：在数组中并不需要真的实现 删除，因此执行 $\textbf{top = top - 1}$ 即可。执行之前先判断一下 $\textbf{top}$ 是否大于 $0$ 若等于 $0$ 说明栈内无元素则不执行。
• 输出栈顶元素：判断 $\textbf{top}$ 是否大于 $0$ 若满足则输出 $\textbf{stk[top]}$ 即可。
• 栈的大小：输出 $\textbf{top}$ 的值即可。

优点

• 可以获取栈顶下方的元素。（通过数组的下标获取）
• 清空栈内所有元素异常方便。（设置变量 top 的值为 $0$ 即可）

STL 的 stack

STL 里的栈叫做 stack。它的定义语法是 stack<元素类型> 变量名，使用前需要导入头文件 stack 或使用万能头文件。

例如 stack<int> stk;

函数名	功能	语法示例	注意事项
push()	加入元素	stk.push(x)
pop()	删除栈顶	stk.pop()	保证栈不为空在使用，否则 RE
top()	获取栈顶	cout << stk.top()
size()	栈的大小	cout << stk.size()
empty()	栈是否为空	cout << stk.empty()

二者比对

• 从目前比赛角度来说，在开启 O2 优化下使用 stack 还是数组模拟栈的区别不会太大，数组模拟栈的常数小一些。
• 使用个人擅长且熟悉的为主。

应用

• 判断括号序列是否合法
• 表达式求值问题，前缀、中缀、后缀表达式。
• 一些模拟题的应用等等。

括号匹配

形如 ()()，(()) 的括号是合法的，形如 )(，()) 都是不合法的。

合法的括号序列需要保证左右括号数量相等，且每一个右括号有唯一的左括号与之匹配。

具体实现：

• 从左往右扫描括号字符串。
• 遇到左括号就压入栈。
• 遇到右括号，当前右括号就需要和它左边 $\textbf{最近}$ 的左括号匹配。
• 左边最近的左括号就是栈顶，若栈不为空删除栈顶元素即可。否则说明当前右括号无法匹配说明括号串不合法。
• 扫描完毕后若栈内元素个数不为 $0$ 说明左括号多了也不合法。

for (auto x : s) 
{
    if (x == '(') stk.push(x);
    else 
    {
        if (stk.empty()) // 右括号找不到匹配的左括号
        {
            cout << "Wrong";
            break;
        }
        else 
        {
            stk.pop();
        }
    }
}
if (!stk.empty()) // 最后栈不为空
{
    cout << "Wrong";
}

表达式求值

表达式求值要解决的问题一般是输入一个字符串表示的表达式，要求输出它的值。

例如输入一个字符串 1+2*3 人眼是很容易能够看出答案的，那么计算机是如何计算的呢？

后缀表达式

逆波兰表达式（后缀表达式）是书写数学表达式的一种形式，其中运算符位于其操作数之后。例如，以下表达式：

$$a+b*c*d+(e-f)*(g*h+i)$$

的逆波兰表达式书为：

$$abc*d*+ef-gh*i+*+$$

前缀表达式即为运算符位于其操作数之前，下文以介绍后缀的计算方法为例。

计算方法

• 从左往右扫描字符串，遇到数字字符就入栈。
• 遇到运算符，取出栈顶两个元素，将第一个取出的元素记为 $a$，第二个取出的元素记为 $b$，如若当前运算符为 $op$，则计算 $b\ op\ a$ 的结果，然后将该结果重新入栈。

重复以上两步直到栈内剩余一个数字，操作完以后栈内最后剩的值就是整个表达式的结果。

注意事项

• 务必是后取出的 $b$ 在运算符左，先取出的 $a$ 在运算符右。

原因：例如 $3- 2$ 的后缀表达式是 $3\ 2\ -$。我们是先把 $3$ 入栈，再把 $2$ 入栈，所以先取的是 $2$ 后取的是 $3$，我们应当计算 $3-2$ 而不是 $2-3$。

• 在表达式合法的前提下，最终栈内必然留下一个数字是最终结果，因此不必考虑其他特殊情况（除非题目有说明）。

例：每次从栈里取走两个元素不必担心栈内没有两个元素的情况，若不够 $2$ 个元素说明表达式是错误的。

• 后缀的好处在于没有括号，因为运算符都在数字后面，且更利于计算。

代码实现

难点如下：

• 一个多位数应当把值完整计算好以后再入栈，而不是遇到数字字符就入栈。
• 对于该问题，我们可以使用双指针这个技巧来获取连续的数字字符的计算。

双指针获取字符串连续的一段数字

当遍历字符串 s 时，若 s[i] 是一个数字字符，我们要考虑 $s_{i+1},s_{i+2},\cdots$ 往后的 $\textcolor{red}{连续位置}$ 是否也都是数字。

即对于一个位置 $s_i$，若它是数字字符，我们需要找到一个 $\textcolor{red}{最靠后}$ 的位置 $j$ 使得 $s_i,s_{i+1},\cdots,s_j$ 都是数字字符，而 $s_{j+1}$ 不是。

在具体实现中：

• 遍历字符串 $s$，若 $s_i$ 是数字字符，紧接着定义一个变量 $j$ 初始化为 $i$。
• 接下来循环往后判断，若 j + 1 < s.size() && s[j + 1] 是数字字符，就执行 j++。说明现在可以往后扩展一个连续的位置。
• 将扩展到的位置的数字都拼起来，因此每次需要执行 sum = sum * 10 + s[j] - '0'

for (int i = 0; i < s.size(); i++)
{
    if (isdigit(s[i]))
    {
        int j = i;
        int sum = s[i] - '0'; // 初始化这个位置的数值
        while (j + 1 < s.size() && isdigit(s[j + 1]))
        {
            j++;
            sum = sum * 10 + s[j] - '0';
        }
        stk.push(sum); // 就将 sum 入栈
        i = j; // 双指针的核心
    }
}

• 重点：入栈以后需要执行 i = j，相当于将变量 $i$ 跳到 $j$ 的位置，这样下一次循环就从 $j+1$ 开始继续向后遍历字符串。

这一步不仅仅保证正确性，也保证时间复杂度。因为我们已经将 $s_i\sim s_j$ 连续的数字段都处理完毕了。下一次应该从 $j+1$ 向后继续处理。

其次 $i,j$ 同步前进，二者皆不回退。因此 j++ 最多执行 $n$ 次，i++ 也执行 $n$ 次。总执行次数为 $2n$ 时间复杂度为 $O(n)$

计算部分

定义函数 eval(char op) 用于计算新的结果并入栈。

当 $op$ 是 +，-，*，从栈内两个取出计算结果后并入栈。

void eval(char op)
{
    int a = stk.top(); // 先取出的
    stk.pop();
    int b = stk.top(); // 后取出的
    stk.pop();
    if (op == '+') stk.push(b + a); // 先取出的在后面
    if (op == '-') stk.push(b - a); // 先取出的在后面
    if (op == '*') stk.push(b * a); // 先取出的在后面
    if (op == '/') stk.push(b / a); // 先取出的在后面
}

主函数部分

for (int i = 0; i < s.size(); i++)
{
    if (isdigit(s[i]))
    {
        int j = i;
        int sum = s[i] - '0'; // 初始化这个位置的数值
        while (j + 1 < s.size() && isdigit(s[j + 1]))
        {
            j++;
            sum = sum * 10 + s[j] - '0';
        }
        stk.push(sum); // 就将 sum 入栈
        i = j; // 双指针的核心
    }
    else if (s[i] == '+' || s[i] == '-' || s[i] == '*' || s[i] == '/')
    {
        eval(s[i]);
    }
}
cout << stk.top(); // 栈里最后剩的就是表达式的结果

总结

• 上述实现的时间复杂度为 $O|S|$，其中 $|S|$ 为字符串的长度。
• 具体做题根据题目要求补充其余细节，复杂的题目可能会有更复杂的运算符，操作数为负数等情况。
• 后缀表达式本质考察了模拟算法，需要掌握。

前缀表达式

• 由于前缀是运算符在前，数字在后，所以需要从右往左倒着遍历字符串。
• 遇到运算符以后取出栈顶元素记为 $a$，再取出一个栈顶元素记为 $b$，设运算符为 $op$，将 $a\ op\ b$ 的结果重新入栈即可。

中缀表达式

中缀表达式需要引入一些表达式树的思想，等学习了树上问题后在进行学习。由于和树上问题结合，因此考察的更难。

验证栈序列

验证出栈序列是否合法也是我们初赛选择题常见的一类题型。

• 使用栈模拟整个过程即可
• 一个能够出栈的数字必然是因为其在栈顶的时候才出栈的，利用这个特性对进栈序列模拟即可。

代码实现

• 使用一个栈对入栈序列 $\textbf{不断地执行}$ 入栈操作，例如 stk.push(a[i])
• 使用一个变量指向当前应当出栈的元素是哪一个（初始化 $j=1$，即第一个出栈的应当是 $b_1$）。
• 当栈顶元素 stk.top() 等于应出栈元素（stk.top() == b[j]），那么就执行出栈操作，同时执行 $j+=1$，即指向下一个该出栈的元素。 (此步骤是一个循环的过程，可能一次性出栈多个元素)
• 最后只需要判断 $j$ 是否等于 $n+1$ 即可分辨出栈序列是否合法。$j=n+1$ 说明出栈序列的所有元素都可以出栈。

补充题单

• P2201 数列编辑器
• CF1073B - Vasya and Books
• CF821C - Okabe and Boxes
• CF26B - Regular Bracket Sequence
• 上海月赛2022丙组T5 - 括号计分