[数据结构]栈与栈的应用

栈是非常重要的线性数据结构之一，其中一端为栈顶，加入元素和取出元素全部在栈顶端进行，满足LIFO（Last In First Out，后进先出）的性质。
考虑这样一个问题：

您需要写一种数据结构，维护一系列数，初始为空。定义其中一端为顶，另一端为底，要求提供三种操作：

（1）格式：$1$1 $x$x，表示在最顶端处加入一个数$x$x；（$O(1)$O(1)）

（2）格式：$2$2，表示输出最顶端的数，并将其删除；（$O(1)$O(1)）

（3）格式：$3$3，表示判断数据结构是否为空。（$O(1)$O(1)）

括号中的数字表示这种操作的期望复杂度。
你可以将这道题想成是一个瓶子，每次可以向瓶口扔下一个物品或取出瓶口的物品。
其实这里要求的数据结构就是栈，满足在同一端进与出的特性。下面我们来看看具体如何来实现。

可以发现一个栈中最重要的其实是栈顶的位置，栈中的元素可以保存在一个数组中。有了这样的概念，我们就可以用一个带有栈顶元素位置指针的数组来完成栈的模拟了（以下数组名为a）。

我们将数组的左侧定义成栈底（顶的反面），右侧为栈顶，那么我们每次的添加操作其实就是在数组右侧添加一个元素，如果原来的栈顶元素在数组中的下标为$cur$cur，那么我们只需将$cur$cur向右移动一格（增加1），再将需要加入的元素加入$a[cur]$a[cur]中即可。

如果要取出栈顶元素，那么其实直接输出$a[cur]$a[cur]即可。如果要达到删除的目的，我们只需要将$cur$cur左移一格（减少1），这样在新加元素时会自动覆盖原有的$a[cur+1]$a[cur+1]，所以其实并不必清零。

以下为栈的模拟的模板。上文的a数组即为代码中的val数组，init可以实现对栈的初始化（其实就是将初始指针清零，相当于删除所有元素），push能够加入一个元素，top返回栈顶元素，pop返回栈顶元素并删除，empty检测栈是否为空。

#include <bits/stdc++.h>
using namespace std;
const int MAXN=100010; 
struct STACK_ {
	int val[MAXN],cur;
};
void init_ (STACK_ &x) {
	x.cur=0;
	return;
}
int push_ (STACK_ &x,int y) {
	x.cur++;
	x.val[x.cur]=y;
	return y;
}
int top_ (STACK_ x) {
	return x.val[x.cur];
}
int pop_ (STACK_ &x) {
	x.cur--;
	return x.val[x.cur+1];
}
bool empty_ (STACK_ x) {
	return (x.cur==0);
}
int main () {
	return 0;
}

当然，这只是栈最基础的形态，下面以两道题目为例来讲一讲栈的一些应用。

1. 维护一个栈，实现三种功能：
（1）向栈顶加入一个数；（$O(1)$O(1)）
（2）删除栈顶的数； （$O(1)$O(1)）
（3）询问栈内的最小值。（$O(1)$O(1)）

这是数据结构题的一个简单扩展，除去最基本的加入、删除操作外，还有一个查询最小值的操作，有一种简单的思路是在维护栈的同时还维护一个堆，删除时同时删除，但是这样的话三种操作的复杂度都是$O(\log n)$O(logn)，不能满足题目要求。

考虑到每次都只会删除栈顶的元素。如果最小值会发生改变那么只有可能是栈顶元素为原来的最小值。 所以我们可以在维护原有的栈的同时再维护一个额外的栈，保存每个时刻的栈内最小值，即若原栈为$A$A，“最小值栈”为$B$B，那么$B[i]=\max \limits_{1 \leq j \leq i}A[j]$B[i]=1≤j≤imax​A[j]，即i之前元素的最小值，例如：

A：5 1 6 7 0
B：5 1 1 1 0

那么当我们加入元素的时候，先在A中直接加入，再在B中加入“原有栈顶元素和新元素的最小值”，例如上面粒子中，加入1时，将1与原有栈顶5比较，发现1比5小，因此在B中加入的是1。至于删除，容易发现只要在两个栈中都删除栈顶就可以了，如果要询问最小值，直接返回B的栈顶即可。

再看下一道题：
Luogu 1449 后缀表达式

后缀表达式是典型的栈的实际应用。对于读入进来的数字，我们可以将它加入到一个栈中，如果遇到了一个运算符，则取出栈顶的两个数字，按照相应运算符运算后将结果加回栈中即可，最后输出栈中剩余的唯一元素。这是因为运算符的两个操作数总是最近的两个数字，而且优先级是自然从左至右的。计算机计算后缀表达式要比中缀表达式（即我们平时所写的表达式）更方便快捷一些。

还有一道类似的题目，可以作为习题，基本思路差不多，用栈维护括号序列：
Luogu 1739 表达式括号匹配

在C++ STL中，可以直接使用栈，在头文件<stack>中，包含push和pop等基本功能。

如果对栈有一定了解，那么就可以去看一看单调栈的特性和原理了。