数据结构：栈
作为本人新开的类型，我就思考了很久，最后决定写与数据结构有关的博客。说到数据结构，我们首先想到的就是栈。
不 怎 么 华 丽 的 分 割 线
一、简介
栈，是只能在某一端插入和删除的特殊线性表。
栈和我们平时生活中的桶类似，先堆进来的压在底下，随后一件一件地往上堆。取走时，只能从上面一件一件地取走。**（先进先出）**无论是堆还是取，都在顶部进行，底部一般是不动的。
栈是一种类似桶堆积物品的数据结构，进行删除和插入的一端称栈顶，另一端称栈底。插入一般称为进栈（PUSH），删除则称为退栈（POP）。栈也称后进先出表（LIFO表）。
二、栈的实现
一个栈可以用定长为n的数组s来表示，用一个栈顶指针top指向栈顶。若top=0，表示栈空，top=0时栈满。进栈时top加1，退栈时top减1。当top<0时，为下溢（是否避免应看实际情况）。栈指针在运算中永远指向栈顶。
1、进栈（PUSH）算法：
过程一：若top=n时，则给出溢出信息，作出处理（进栈前首先检查栈是否已满，满则会溢出，不满则进行过程二）；
过程二：top++（栈指针加1，指向进栈地址）；
过程三：s[top]=x，结束（x为新进栈的元素）。
2、退栈（POP）
过程一：若top<=0，则给出下溢信息，作出错处理（退栈前先检查是否已为空栈，空则会下溢，不空则作过程二）；
过程二：x=s[top]（退栈后的元素赋给x）；
过程三：top–，结束（栈指针减1，指向栈顶）。
实现过程程序（C++）：
#define n 100
void push(int s[],int *top,int *x) //入栈
{if(*top==n) printf("overflow"); //判断会不会溢出，会则输出提示“overflow”；else{(*top)++;s[*top]=*x;}
}
void pop(int s[],int *y,int *top) //出栈
{if(*top==0) printf("underflow"); //判断会不会下溢，会则输出提示“underflow”；else{*y=s[*top];(*top)--;}
}
对于出栈运算中的“下溢”，程序中仅给出了一个标志信息，而在实际应用中，下溢可以用来作为控制程序转移的判断标志，是十分有用的，我们应根据实际需要来使用。对于入栈运算中的“上溢”，则是一种致命的错误，将使程序无法继续运行，所以要设法避免。
讲了这么多，我们也要实战演练一下，做一做题，巩固一下。
车厢调度
【问题描述】
有一个火车站，铁路如图所示，每辆火车从A驶入，再从B方向驶出，同时它的车厢可以重新组合。假设从A方向驶来的火车有n节（n<=1000），分别按照顺序编号为1、2、3、······、n。假定在进入车站前，每节车厢之间都不是连着的，并且它们可以自行移动到B处的铁轨上。另外假定车站C可以停放任意多节车厢。但是一旦进入了车站C，它就不能再回到A方向的铁轨上了，并且一旦当它进入B方向的铁轨，它就不能再回到车站C。
负责车厢调度的工作人员需要知道能否使它以a1，a2，a3，······，an的顺序从B方向驶出，请你来判断能否得到指定的车厢顺序。
【输入】
第一行为一个整数n，其中n≤1000，表示有n节车厢，第二行为n个数字，表示指定的车厢序列。
【输出】
如果可以得到指定的车厢序列，则输出一个字符串“YES”，否则输出“NO”。（注意要大写，不包含引号）
【输入样例】
5
5 4 3 2 1
【输出样例】
YES
根据题目，我们不难发现，其实这个车站C可以看作一个栈，而车厢调度的过程可以看作入栈和出栈的操作。我们只要用数组模拟一个栈就可以快速解决问题。同时因为题目中，数字在入栈前是升序排列的，所以较大的数字若要入栈，那么比这个它小的数字只有两种可能的状态：要么是在栈中，要么是已出栈，不可能处于未入栈的状态。所以，如果某个数字要入栈，那么栈内的所有数字都要小于它，同时，栈中的数字越靠近栈顶越大，栈顶数字在栈中最大。理解了这些之后，就不难发现，我们在模拟过程中，只要栈顶数字且未入栈的数字都不符合当前出栈数字，那就可以确认此序列无法得到。
话不多说，放程序。
#include<bits/stdc++.h>
using namespace std;
int n,a[1001],x,i,b[1001],top; //a数组为出栈顺序，b数组为栈（模拟），top为栈顶指针
int main()
{cin>>n;for(i=1;i<=n;i++){cin>>a[i];}top=0;for(i=1,x=1;i<=n;i++) //x为将要入栈的数字{while(x<=a[i]) //模拟入栈过程b[++top]=x++;if(b[top]==a[i]) //若符合出栈数字，那就模拟将其出栈--top;else{cout<<"NO"<<endl;return 0;}}cout<<"YES"<<endl;return 0;
}
我 是 一 条 分 割 线
当然，c++有个“神奇”又方便的东西叫做STL，在这个STL中，它早已为我们准备好了许多有用的东西，包括栈（太棒了，不用这么辛苦去模拟栈了）。
想要使用这种栈，首先要用一个头文件叫：
#include<stack>
什么，你说你用“bits/stdc++.h”？那就当我没说过。
来，我们来看一下它的用法：
#include<stack>
#include<iostream>
using namespace std;
int main()
{stack<int> st; //定义一个整形的栈st;for(int i=1;i<=5;i++){st.push(i); //push()指将括号内的元素压入栈；}for(int i=1;i<=5;i++){if(!st.empty()) //empty()指判断栈是否为空，空则返回1，否则返回0；{cout<<st.top()<<" "; //top()指获取栈顶元素（不删除栈顶元素）；st.pop(); //pop()指删除栈顶元素（不获取栈顶元素）；}}return 0;
}
此外，size()则为返回stack内元素的个数。
最后，我想让大家自己试一下用stack来解决一下刚才的车厢调度问题，这里我就不多提示了，大家自己去试试吧。
本人认为，STL虽然好用，但我们也应该了解一下这些数据结构或函数的原理，做到能理解、会模拟，这样才能更好的适应不同的题目。
好了，数据结构——栈的内容就讲完了。很抱歉，本来1月多就开始写，直到3月多才完成（跪求原谅），不好意思。我也该治一下我的拖延症了，好了，再见。
希望这篇文章对你们有用。再见。
