栈
栈（\(\text {stack}\)）是一种后进先出（\(\text {Last In First Out,LIFO}\)）的线性表，顾名思义，后入栈的元素反而先出栈，其限制是只能在一端插入与删除，
就像下面这样，只有一端有开口，另一端则是封死的。
一般的，我们将栈能插入与删除的一端称为「栈顶」，而不能进行操作的一端称为「栈底」。
同时，插入操作一般称作入栈或压栈（\(\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<Type> s 声明一个 Type 类型的栈 \(s\)。
s.top() 返回一个 int，表示当前栈顶的值。\(O(1)\)
s.push(x) 将元素 \(x\) 压入栈 \(s\)。\(O(1)\)
s.pop() 弹出栈 \(s\) 的栈顶元素。\(O(1)\)
s.empty() 返回一个 bool，true 表示栈 \(s\) 为空，false 反之。\(O(1)\)
s.size() 返回一个 int，表示栈 \(s\) 的元素个数。\(O(1)\)
更多方法见微软文档 \(\texttt{stack STL}\) 部分。
队列
队列（\(\text {queue}\)）与栈相反，是一种先进先出（\(\text {First In First Out,FIOF}\)）的线性表，也就是说，先入队的元素先出队，与生活中的「排队」是一样的。
而队列的限制则是只能在一端插入，在另一端删除，如下图：
一般的，我们将队列能进行插入的一端称作「队尾」，进行删除的一端称作「队头」。
而插入操作一般称作入队（\(\text {push}\)），删除一般称作出队（\(\text {pop}\)）。
\(\text {STL queue}\)
强大的 \(\text {STL}\) 自然也为我们提供了 queue 关键字。
除了可以手写栈，强大的 \(\text {STL}\) 还为我们提供了 stack 关键字，用法如下：
queue<Type> q 声明一个 Type 类型的队列 \(q\)。
q.front() 返回一个 int，表示当前队头的值。\(O(1)\)
q.push(x) 将元素 \(x\) 入队队列 \(q\)。\(O(1)\)
q.pop() 队列 \(q\) 的队头元素出队。\(O(1)\)
q.empty() 返回一个 bool，true 表示队列 \(q\) 为空，false 反之。\(O(1)\)
q.size() 返回一个 int，表示队列 \(q\) 的元素个数。\(O(1)\)
更多方法见微软文档 \(\texttt{queue STL}\) 部分。