栈
栈是一种后进先出（\(\text {Last In First Out,LIFO}\)）的线性表，顾名思义，后入栈的元素反而先出栈，其限制是只能在一端插入与删除，
就像下面这样，只有一端有开口，另一端则是封死的。
\[栈顶 \large\begin{array}{c|c|c|c|c|c|c|c|{3}{r@{.}l|}} \hline \ \text{} 0&1 & 2&3 & 4&5&6&7&...\\ \hline \end{array} 栈底 \]一般的，我们将栈能插入与删除的一端称为「栈顶」，而不能进行操作的一端称为「栈底」。
同时，插入操作一般称作入栈或压栈（\(\text {push}\)），删除操作称作出栈或弹出（\(\text {pop}\)）。
一个通俗的例子是把栈看作一个盘子堆，只能在盘子堆的顶上拿取盘子，如果从中间抽出/插入盘子，盘子堆就会倒塌，碎成碎片。
手写栈
接下来我们尝试一下，使用静态数组来模拟一个栈。
从增加元素开始，先考虑栈底与栈顶的位置，很明显，为了不限制栈的大小与方便，栈底设在 \(1\) 的位置比较好，
再用一个 int \(top\) 指向当前栈顶的位置
int top = 0,s[MAXN] = {0}; // 一开始栈内没有元素，所以 top 指向 0 表示当前栈内为空
当进行压栈时，新的元素会被「放」在原来的栈顶上，
此时的栈顶就是 \(top + 1\)，再赋值即可。
void push(int x){ // 传参需要压栈的元素 x
s[top ++] = x; // 压入元素
}
因为只是操作了一次数组 \(s\) 与 变量 \(top\)，所以时间复杂度为 \(O(1)\) 。
接下来是删除元素，可以想到将栈顶移动到原栈顶的下一个元素上，以删除原本的元素。
但是要判断一下当前 \(top\) 是否指向的是 \(0\)（空栈），否则就会收获 \(\color {Purple} {\texttt {RE}} \times \infty\)。
int pop(){
if(top)top --;
else return -1;
return 0;
}
同样的，时间复杂度为 \(O(1)\)。
而还有一个常用操作就是取栈当前的元素个数，因为 \(top\) 指向了栈顶，所以 \(top\) 就是栈当前的元素个数。
int size(){
return top;
}
\(\text {STL stack}\)
除了可以手写栈，强大的 \(\text {STL}\) 还为我们提供了 stack 关键字，用法如下：
stack<int> s 声明一个 int 类型的栈 \(s\)。
s.push(x) 将元素 \(x\) 压入栈 \(s\)。
s.pop() 弹出栈 \(s\) 的栈顶元素。
s.empty() 返回一个 bool，true 表示栈 \(s\) 为空，false 反之。
s.size() 返回一个 int，表示栈 \(s\) 的元素个数。
更多方法见微软文档 \(\texttt{stack STL}\) 部分。