栈（stack）
栈是一种运算受限的线性表。限定仅在表尾进行插入和删除的操作。
插入（push）， 弹出（pop）。其特性就是先进后出，即先插入的元素最后才能弹出。大家可以把栈想象成一个弹夹，你只能在顶层一颗一颗装入子弹，先装的子弹在最底层，打出时也只能从上层一颗一颗打出。最后装入的一颗子弹最先打出。这便是先进后出的意思。在栈中，“弹夹”的最上层被叫做栈顶，一般用top来指示栈顶的位置。
我们可以先通过结构体自己定义一个栈，便于理解。
#include<iostream>
using namespace std;
struct Stack {
int data[10000];
int top = -1;
void push(int x) {//push函数定义
top++;
if (top < 10000) {
data[top] = x;
}
else {
top--;
cout << "stack overflow" << endl;
}
}
void pop() {//pop函数定义
if (top >= 0) {
top--;
}
}
int topval() {
if (top >= 0) {
return data[top];
}
}
};
int main()
{
Stack s;
for (int i =1; i <= 10; i++) {
s.push(i);
}
for (int i = 1; i <= 10; i++) {
cout << s.topval() << " ";
s.pop();
}
return 0;
}
定义完成后，我们给栈从1-10赋值，并进行输出，可以看到输出的结果为10-1的顺序。
这也再一次印证了其先进后出的特性。
STL中也有栈，且更加方便使用，使用前记得加上#include<stack> 头文件
创建一个栈的语法为stack<T> sT 表示数据类型如int，char，float等等。
栈的基本操作
判断是否为空栈
使用empty()函数来判断栈是否为空
bool empty()如果栈为空返回true，否则返回false。
入栈
使用push()函数来完成入栈操作
例如：前面将1-10入栈的例子
stack<int> s;//创建一个栈
for(int i=1;i<=10;i++){
s.push(i);
}
出栈
使用pop()函数来完成出栈的操作
移除栈中最顶层元素
返回栈顶元素
使用top()函数返回栈顶元素
例如：上面输出逆序输出1-10的例子
for (int i = 1; i <= 10; i++) {
cout << s.top() << " ";
s.pop();
}
注意：要先取top(),再用pop()弹出栈顶元素
返回栈中元素数目
size()函数返回栈中的元素个数。
以上就是STL中栈的基本操作。
来一道例题熟悉一下这些操作。
题目：
火车出入站问题，火车按照1-n对应编号，输出n，接下来输入可能的出站顺序，写一个程序判断这种出站顺序是否合法，合法输出legal，反之输出illegal。
思路：类似于詹天佑发明的人字型铁路。
画图示意一下
好了画图模拟就完成了，第一次画图有点丑。所以2 4 3 1 5就是一个合法的出站组合。
明白了题意后，展示一下代码：
#include<iostream>
#include<vector>//STL中的另一个容器，不了解的我后续再写一个介绍一下
#include<stack>//使用栈时需要加的头文件，千万别忘记啦
using namespace std;
int main() {
int n;
cin >> n;
vector<int> a(n);
for (int i = 0; i < n; i++) {//用动态数组存入用户给出的出站组合
cin >> a[i];
}
stack<int> s;//创建栈s
int cur = 1;
bool f = 1;
for (int i = 0; i < n; i++) {
while ((s.empty()||s.top() != a[i])&&cur<=n) {//一遍一遍按照给出的出站顺序，必须把每个火车找到并且放到栈顶才可以出站。
s.push(cur);
cur++;
}
if (s.empty() || s.top() != a[i]) {
f = 0;
break;
}
else {
s.pop();
}
}
if (f) {
cout << "legal" << endl;
}
else {
cout << "illegal" << endl;
}
return 0;
}
运行结果：
输入 5
2 4 3 1 5
可以看到之前演示的2 4 3 1 5的出站顺序确实是合法的，说明程序运行正常
如上图的例子，先把1放进栈再出栈，接着要使5出栈，就必须把2 3 4 5都放进栈，把5出栈，此时4为栈顶，没法将3出栈。所以该出站组合不合法。
今天的STL的分享就到这里啦，第一次写这么长的文章，也不知道效果如何，希望看到这里的优秀的你，可以给我点个赞嘛！（这人居然还敢要赞（doge））难免有疏漏之处，有错误，欢迎指正，一定认真吸取学习经验。
今天 你code 了嘛？