---

stack——栈

头文件 #include <stack>

栈是实现了先进后出的一种容器，元素的插入与删除都只能在栈的顶部来完成

stack的构造

stack<TYPE> stkName;//其中TYPE可以是任何类型，包括自定义类型与指针类型

拷贝构造

stack<int> s1;
stack<int> s2(s1);	//拷贝s1并构造s2
stack<int> s3;
s3 = s1;		//将s1的值赋给s3

stack的函数

//stack构造函数
stack<T> stkT;//stack采用模板类实现， stack对象的默认构造形式：
stack(const stack &stk);//拷贝构造函数

//stack赋值操作
stack& operator=(const stack &stk);//重载等号操作符

//stack数据存取操作
push(elem);//向栈顶添加元素
pop();//从栈顶移除第一个元素
top();//返回栈顶元素

//stack大小操作
empty();//判断堆栈是否为空size();//返回堆栈的大小

注意：对一个空栈执行pop操作会导致程序异常而结束，所以要先用empty进行判断。

stack的应用

1. 递归算法

2. 括号匹配检测

3. DFS算法

queue——队列

头文件 #include <queue>

队列是一种先进先出的容器，元素的插入在队尾进行，元素的删除在队首进行，类似于日常生活中的排队。

queue的构造

queue<TYPE> quName;//其中TYPE可以是任何类型，包括自定义类型与指针类型

构造方法与stack相同。

queue的函数

//queue构造函数
queue<T> queT;//queue采用模板类实现，queue对象的默认构造形式：
queue(const queue &que);//拷贝构造函数

//queue存取、插入和删除操作
push(elem);//往队尾添加元素
pop();//从队头移除第一个元素
back();//返回最后一个元素
front();//返回第一个元素

//queue赋值操作
queue& operator=(const queue &que);//重载等号操作符

//queue大小操作
empty();//判断队列是否为空
size();//返回队列的大小

注意：对一个空队列执行pop操作会导致程序异常而结束，所以要先用empty进行判断。

queue的应用

1. BFS算法
2. 保存暂时不用的数据

例题：NEUQOJ-1689 火车调度问题(截止现在此题目无法做)

题目描述：

粗心的塔学长现在是火车站的调度员，看看现在的惨状吧，列车车厢的顺序竟然完全是乱的！为避免塔学长登上明天的UC头条，车站划分给塔塔一段如图所示的铁路，你能帮助塔塔把车厢的顺序调整好吗？

其中，A为入口，B为出口，S为中转盲端。所有铁道均为单轨单向式：列车行驶的方向只能是从A到S，再从S到B；另外，不允许超车。因为车厢可在S中驻留，所以它们从B端驶出的次序，可能与从A端驶入的次序不同。不过S的容量有限，同时驻留的车厢不得超过m节。

列车由编号依次为{1, 2, …, n}的n节车厢组成。塔塔希望知道，按照以上交通规则，这些车厢能否以{a1, a2, …, an}的次序，重新排列后从B端驶出。如果可行，应该以怎样的次序操作?

输入：

共两行。
第一行为两个整数n，m。
第二行为以空格分隔的n个整数，保证为{1, 2, …, n}的一个排列，表示待判断可行性的驶出序列{a1，a2，…，an}。

输出：

若驶出序列可行，则输出操作序列，其中push表示车厢从A进入S，pop表示车厢从S进入B，每个操作占一行。
若不可行，则输出“震惊！昨天小汤河火车站竟然。。。”。

样例输入

5 2

1 2 3 5 4
样例输出

push
pop
push
pop
push
pop
push
push
pop
pop

思路

题目就是一道对栈进行操作的问题，给定初始状态A与最终状态B，限定栈的大小，来判断是否实现该操作。核心问题在于如何进行判断，这一部分的逻辑不容易处理。

1. 设置两个变量来表示对A，B的判断进度，然后判断当前A与B的首元是否相同，如果相同并且栈不满的话，push再pop达成目标。

2. 不满足上述条件的话，判断当前栈顶元素是否与B的首元相同，相同的话pop。

3. 还不满足上述条件的话，将A的首元去入栈，push。

4. 上述三种条件都不满足的话，无法达成目标，结束。

实现代码

//仅是个人思路，因OJ这道题无法做，故未经程序检验
#include <iostream>
#include <stack>
using namespace std;
int main()
{
    int n，m;//接收火车数量以及栈的大小
    int a[1000];//接收火车调度后的状态
    int a1[1000];//接收栈的操作状态，1表示Push。0表示pop
    int ntp = 0;//计数栈的操作步数
    stack<int> s;//构造栈
    cin>>n>>m;
    for(int i = 1;i<=n;i++)
    {
        cin>>a[i];
    }
    int A = 1;//原始火车的判断进度
    int B = 1;//结束后火车的判断进度
    int flag = 1;//判断条件
    while(B<=n && flag)
    {
        if(A == a[B]&&s.size()<m)
        {
            ++A;++B;
            a1[ntp++] = 1;
            a1[ntp++] = 0;
        }
        else if(!s.empty()&&s.top()==a[B])
        {
            s.pop();
            a1[ntp++] = 0;
            ++B;
        }
        else if(A<=n && s.size()<m)
        {
            s.push(A++);
            a1[ntp++] = 1;
        }
        else flag = 0;
    }
    if(flag == 0) cout<<"震惊！昨天小汤河火车站竟然。。。"<<endl;
    else
    {
        for(int q = 0;q<ntp;q++)
        {
            if(a1[q] == 1) cout<<"push"<<endl;
            else cout<<"pop"<<endl;
        }
    }
    return 0;
}