队列：

特点：

1)先进先出(FIFO)
2)在队头删除元素，在对尾加入元素

常见操作：

1)创建队列对象：queue<元素类型>队列名 q；
2)队列添加元素：q.push(元素名);
3)去掉队尾元素：q.pop();
4)访问队首元素：q.front();
5)判断是否为空：q.empty();//真值不为0就是空的
6)返回队列大小：q.size();

优先队列：

特点：

1)每次取出都是具有最高优先权的元素
2)在队头删除元素，在对尾加入元素

基本用法：

1) 创建队列元素： priority_queue<元素类型>q;
2)访问最优元素：q.top();

//大顶堆(从大到小)
priority_queue<int> qi;//默认大顶堆
/等同于 priority_queue<int, vector<int>, less<int> > qi;

//小顶堆(从小到大)
priority_queue<int, vector<int>, greater<int> >qi2;(注意空格> >)

重载小于号

//小顶堆
struct node {
    ll val, sum;
    node(ll v, ll s): val(v), sum(s) {}
    bool operator<(const node& no) const {
        return val > no.val;
    }
};
priority_queue<node> qu;
node.val 越大的节点在排序时次序越靠前，由于优先队列默认是大顶堆的，和sort函数是完全相反的顺序
即现在 node.val 越小的排在最前面

deque队列

deque容器为一个给定类型的元素进行线性处理，像向量一样，它能够快速地随机访问任一个元素，并且能够高效地插入和删除容器的尾部元素。但它又与vector不同，deque支持高效插入和删除容器的头部元素，因此也叫做双端队列。

栈

特点：

1)先进后出(FILO)
2)在栈顶删除元素，在栈顶加入元素

基本用法

1)创建栈对象：stack<元素类型> p;
2)栈顶添元素：p.push();
3)删除栈顶元素：p.pop();
4)访问栈顶：p.top();

注意：栈和队列都没有clear 要清空就要循环调用出栈函数pop

括号匹配问题
最长合法括号子序列

vector (向量，动态数组)

1) 向量的定义：vector<元素类型> a;
2)向量的初始化：
vector< int > abc;
vector< int > abc(10);初始化10个默认值为0的元素
vector< int > abc(10,1);//初始化10个值为1的元素

3)基本用法：
取首元素：a.front();
取尾元素：a.back();
在尾部添加一个元素：a.push_back(…);
删除尾部元素：a.pop_back();
翻转：reverse(a.begin(),a.end())
访问元素：迭代器

for(auto it = a.begin(); it != a.end(); ++it)
        cout<<*it<<<<endl;

4)邻接表

vector<邻接表>
定义：typedef pair<int,int> PII;
      vector<PII> g[N];

实现：(运用dijkstra最短路径算法) 
    for(int i...i<=m...){
        cin >> a >> b >>c;
        g[a].push_back({c,b});//先权值后是连接的根节点  
      } 
      ......
    for(auto to :g[now]){
        int v = to.second, u = to.first;

    }

set(集合)

特点：有序无重复

基本用法：

1)set< int >s;
2) 清空：s.clear();
3)插入：s.insert();//没有就成功插入
4)查询是否有元素：int hav = s.count(x)//返回0或者1
5）删除：s.erase(x);

注意：set 类似 堆 和 二叉树
只能通过迭代器(iterator)访问，而vector可以直接访问下标

set<int,greater<int> >st;
set<int,greater<int> >::iterator it;
for(it = st.begin();it!=st.end();it++) printf("%d",*it);

map(映射)键值对（key value）容器

map 会对 key 自动排序

基本操作:

1) map< string,int > m;
2)m.count(x) //返回m中键值等于 x 的元素的个数，map类型中所有的数据的Key值都是不同的，所以被count的数要么存在1次，要么不存在
3）m.find(x) //返回的是被查找元素的位置，没有则返回m.end()
4) m.erase(x) //删除m中键值为 x 的元素，返回删除的个数(0,1);
5) m.inset(e) //e可以是key,value

map<int,string> m;
test.insert(make_pair("test2",3));//test["test2"]=3 
map<string,int>::iterator it;
it=test.find("test2");
cout<<it->first<<" "<<it->second<<endl;

//迭代器
map<int ,string>::iterator it;
for(it=m.begin();it!=m.end();it++)
    cout<<it->first<<" "<<it->second<<endl;

队列的应用——小L的编辑器

输入样例:

abcde
LLRLR

输出样例：

cedba

完整代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1e6+50;

int main(){
    ios::sync_with_stdio(0);
    string s,t;cin>>s>>t;
    deque<char> pre,suf;;
    for(int i=0;i<t.size();i++){
        if(t[i]=='L'){
            suf.push_front(s[i]);
        }
        else{
            pre.push_back(s[i]);


*   }
    }
    for(auto &x:pre) cout<<x;
    for(auto &x:suf) cout<<x;
    return 0;
}

<栈的应用——火车进站出站问题>

如：编号分别为“1”、“2”、“3”、“4”、“5”的5个火车顺序进站，那么进站序列为“12345”，全部进站后再顺序出站，则出站序列为“54321”，如果先进1,2，然后2出站，然后1出站，然后再3进站、出站，4进站、出站，5进站、出站，那么出站序列就为21345.

对于序列中的任何一个数其后面所有比它小的数应该是倒序的，例如4321 是一个有效的出栈序列，1423不是一个有效的出栈结果（4 后面比它小的两个数 2 ，3 不是倒序）。

#include <bits/stdc++.h>
using namespace std;
int n, k, p1, p2, op[25];
char o1[25], o2[25];

//火车进出站问题 (栈)

int main(){
    while(scanf("%d", &n) == 1){
        stack<char> s;
        s.push('#'); 
        scanf("%s %s", o1, o2);
        p1 = p2 = k = 0;
        while(o1[p1] != '\0'){// 123 312 
            op[k++] = 1, s.push(o1[p1++]);
            while(o2[p2] == s.top())
                s.pop(), p2++, op[k++] = 0;
        }
        if(s.top() != '#')
            printf("No.\n");
        else{
            printf("Yes.\n");
            for(int i = 0; i < k; i++)
                printf("%s\n", op[i] == 1 ? "in" : "out");
        }
        printf("FINISH\n");
    }
    return 0;
}

<栈的应用——括号匹配问题>

圆括号 “()” 和大括号 “{}”
在编写程序时，括号可以嵌套，即： “({()})” 这种形式，但 “({)” 或者 “({}” 都不符合要求。

代码：

**算法思路：**
1） 如果碰到的是左圆括号或者左大括号，直接压栈；
2） 如果碰到的是右圆括号或者右大括号，就直接和栈顶元素配对：如果匹配，栈顶元素弹栈；反之，括号不匹配；

#include <bits/stdc++.h>
using namespace std;


//括号匹配问题 
 string s;

 bool is_match(string str)
{
    size_t len = str.length();
    stack<char> s;
    int i;
    int cnt = 0; 
    for (i = 0; i < len; ++i) {
        if (str[i] == '(') {
            s.push(str[i]);
            ++cnt; 
            continue;
        }
        if (str[i] == ')') {
            ++cnt; 
            if (!s.empty() && s.top() == '(') {
                s.pop();
                continue;
            }
        }
    }

    if (!s.empty()) {
        return false;
    }
    if (cnt % 2 != 0) {
        return false; 
    }

    return true;
}

int main(){
    cin >> s;
    if(is_match(s)) cout<<"Yes"<<endl;
    else cout<<"No"<<endl;
    return 0;
}