数据结构

栈

介绍

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

初赛的考察点

• 熟悉栈的原理和代码
• 表达式求值的应用
• 了解和栈有关的算法原理和代码

栈的实现

• 数组模拟栈
• STL 里的 stack

数组模拟栈

由于我们需要获取栈顶元素是谁，以及能够知道数组里存放了几个元素，我们可以使用一个名为 top 的变量指向栈顶元素的下标，初始化 top = 0 意为栈内没有元素。

• 加入元素：加入一个元素，我们的做法是让 top 变量向右移动一位，然后对当前位置的元素赋值，通常写成 stk[++top] = x;
• 弹出栈顶：弹出栈顶的实现方式非常简单，执行 top -= 1; 即可。当然我们可以先判断一下 top 是否大于 $0$ 若等于 $0$ 说明栈内无元素则不执行。
• 输出栈顶元素：先判断 top 是否大于 $0$ 若满足则输出 stk[top] 即可。
• 栈的大小：输出 top 的值即可。

STL 里的 stack

格式：stack<元素类型> 变量名，例如 stack<int> stk;

• 加入元素：stk.push(x)
• 判断栈是否为空：cout << stk.empty(); 为空输出 1 否则为 0。
• 弹出栈顶：if (!stk.empty()) stk.pop()
• 输出栈顶元素：if (!stk.empty()) cout << stk.top();
• 栈的大小：cout << stk.size() 即可。

判断入栈序列是否合法

该类问题通常为给定入栈序列，判断出栈序列是否合法。解决办法即用栈模拟每个选项，找到不合法的选项即可。

例如入栈序列为 a b c d e，以下哪个选项为不合法的出栈序列？

• a b c d e
• e d c b a
• b a c d e
• c d a e b

模拟发现第四个选项错误，因为 $b$ 还在 $a$ 头顶呆着，$a$ 不可能先于 $b$ 离开栈。

表达式求值

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

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

前后缀表达式

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

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

可以用逆波兰表达式书写：

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

后缀表达式的计算方法

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

例如 3 4 + 5 - 的计算过程如下

• $3$ 入栈，$4$ 入栈。
• 遇到 +，取出 $3,4$，计算 $3+4$ 然后将 $7$ 入栈
• 遇到 $5$ 入栈
• 遇到 -，计算 7 - 5 的结果入栈

最后栈里只剩一个 $2$ 即为该后缀表达式的结果。

注意事项

• 务必是后取出的 $b$ 在运算符左，先取出的 $a$ 在运算符右，原因是例如 $3- 2$ 的后缀表达式是 $3\ 2\ -$。我们是先把 $3$ 入栈，再把 $2$ 入栈，所以先取的是 $2$ 后取的是 $3$，我们应当计算 $3-2$ 而不是 $2-3$。
• 在表达式合法的前提下，最终栈内必然留下一个数字是最终结果，因此不必考虑其他特殊情况，例如每次从栈里取走两个元素不必担心栈内没有两个元素的情况，若不够 $2$ 个元素说明表达式是错误的。
• 后缀的好处在于没有括号，因为运算符都在数字后面，且更利于计算。

如果题目不需要我们计算真实的结果，而需要我们转中缀表达式，我们就不要把结果真的算出来，直接将整个式子入栈即可，判断何时需要括号即可。

例如 3 4 + 5 - 的计算过程如下

• $3$ 入栈，$4$ 入栈。
• 遇到 +，取出 $3,4$，计算 $3+4$ 然后将 3 + 4 入栈
• 遇到 $5$ 入栈
• 遇到 -，取出栈顶的两个，将 3 + 4 - 5 入栈，这也就是原来的中缀表达式。

前缀表达式

前缀表达式的求解类似于后缀，需要注意以下几点：

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

中缀转后缀

1. 首先根据运算符的优先级，重新加上括号
2. 去括号的时候，从外向内去，每次就把运算符写到自己所在这一层的括号后即可。

例如 a * (b + c) * d 转后缀的步骤如下：

• 加括号可得 ( (a * (b + c)) * d)
• 去掉最外层括号，将 * 移到括号右，可得 (a * (b + c)) d *
• 去掉最外层括号，将 * 移到括号右，可得 a (b + c) * d *
• 去掉最外层括号，将 + 移到括号右，可得 a b c + * d *

括号表达式判定

形如给你一个括号表达式，你要判断括号是否合法？

1. 从左往右扫描括号字符串
2. 遇到左括号入栈
3. 遇到右括号，若栈不为空，说明栈顶的左括号就是和当前右括号匹配成一对，匹配成功就出栈。

否则说明这个右括号没有左括号匹配，括号不合法。

队列

介绍

队列（queue）是一种具有「先进入队列的元素一定先出队列」性质的表。由于该性质，队列通常也被称为先进先出（first in first out）表，简称 FIFO 表。

实现方式

• 数组模拟队列
• STL 的 queue

数组模拟队列

首先根据数据范围定义一个数组，以最基础的数据类型都为 int 为例，例如 int q[N];

使用两个变量标记队列的头部和尾部，通常使用 int h = 1, t = 0; 设置为 $1$ 和 $0$ 表明当 $h>t$ 说明队列里还没有元素。

• 插入元素：q[++t] = x; 加入元素移动队尾这个变量。
• 删除队头元素：h++;
• 访问队首：cout << q[h];
• 访问队尾：cout << q[t];
• 清空队列：h = 1, t = 0;
• 队列元素个数：cout << t - h + 1;

STL 的 queue

使用方法为 queue<元素类型> 队列名字

• 插入元素：q.push(x)。元素加入到队尾。
• 删除队头元素：q.pop(); 注意保证队列不为空在使用。
• 访问队首：cout << q.front(); 注意保证队列不为空在使用。
• 访问队尾：cout << q.back(); 注意保证队列不为空在使用。
• 清空队列：使用 while 循环遍历队列，进行 pop() 操作。例如：while (q.size()) q.pop();
• 队列元素个数：cout << q.size();
• 队列是否为空：cout << q.empty(); 为空返回 true 否则返回 false

初赛的考察点

• 模拟队列的操作做选择题。
• 队列是和广度优先搜索算法搭配使用。

链表

介绍

链表是一种用于存储数据的数据结构，通过如链条一般的指针来连接元素。它的特点是插入与删除数据十分方便，但寻找与读取数据的表现欠佳。

和数组的区别

• 链表因其链状的结构，能方便地删除、插入数据，操作次数是 $O(1)$。但也因为这样，寻找、读取数据的效率不如数组高，在随机访问数据中的操作次数是 $O(n)$。
• 数组可以方便地寻找并读取数据，在随机访问中操作次数是 $O(1)$。但删除、插入的操作次数是 $O(n)$ 次。

单向链表

单向链表中包含数据域和指针域，其中数据域用于存放数据，指针域用来连接当前结点和下一节点。

单向链表的插入

原本是黑色链接，我们要改为 $2$ 条红色链接}$，即$x$的下一个是$y$，$y$的下一个是$z$，按照如下代码即可实现。

y->next = x->next

x->next = y

二者顺序不能调换。

单向链表的删除

如图所示删去 $y$ 就要让 $x$ 直接连向 $z$ ，$z$ 原本属于 $y$ 的下一个，即 $x$ 的下一个的下一个。

x->next = x->next->next（$x$ 的右边直接指向 $z$ 达到删除 $y$ 的效果）

双向链表

双向链表中同样有数据域和指针域。不同之处在于，指针域有左右（或上一个、下一个）之分，用来连接上一个结点、当前结点、下一个结点。

双向链表的删除

如果要删除 $x$ 和 $z$ 之间的 $y$ 我们就要让原本红色的连接变为黑色连接。即让 $x$ 的右边指向 $z$，$z$ 的左边指向 $x$。可以通过以下代码实现：

• y->next->prev = y->prev;
• y->prev->next = y->next;

双向链表的插入

当我们给 $x$ 和 $z$ 之间插入 $y$ 的时候，我们需要建立四条连接，如图 $1,2,3,4$ 所示，可通过如下代码完成：

• y->next = x->next; （第 $3$ 条边）
• y->next->prev = y; （第 $4$ 条边）
• y->prev = x; （第 $2$ 条边）
• x->next = y;

初赛考察点

• 考察链表的基本概念和插入删除复杂度。
• 考察插入和删除的代码理解
• 头插法和尾插法（在链表头部或尾部插入元素）