队列

操作

创建队列对象：queue<元素类型> 队列名;

队列添加元素：队列名.push(元素名);

去掉队首元素：队列名.pop();

访问队首元素：队列名.front();

返回队列大小：队列名.size(); 

---

优先队列（堆）

操作

创建队列对象：priority_queue<元素类型> 队列名;

队列添加元素：队列名.push(元素名);

去掉具有最高优先权的元素：队列名.pop();

判断是否为空：队列名.empty();

返回队列大小：队列名.size();

访问具有最高优先权的元素：队列名.top();

---

栈

介绍

先进后出（FILO）

操作

创建栈对象：stack<元素名> 栈名;

栈顶添加元素：栈名.push(元素名);

删除栈顶元素：栈名.pop();

访问栈顶元素：栈名.top();

判断是否为空：栈名.empty();

返回栈的大小：栈名.size();

清空：循环出栈：

        while(!栈名.empty()) 栈名.pop();

经典例题

括号匹配

        解：读取左括号时进栈；读取右括号时检测是否与栈顶括号匹配，匹配时消掉，有一个不匹配直接输出no。

#include <iostream>
#include <string>
#include <stack>
using namespace std;

bool check(string);

int main()
{
	string str;
	while(cin >> str)
	{
		if(check(str))
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}
	return 0;
}

bool check(string str)
{
	stack<char> S;
	S.push('#');	//设置“哨兵”，最后不至于访问空栈
	for(int i = 0; i < str.size(); i++)
	{
		char temp = str[i];
		if(temp == ')')
		{
			if(S.top() != '(') return false;
			else S.pop();
		}
		else if(temp == ']')
		{
			if(S.top() != '[') return false;
			else S.pop();	
		}
		else S.push(temp);
	}
	return S.size() == 1;    //最后只剩“哨兵”
}

        注意：假如不使用哨兵，当使用S.top()时，就相当于试图访问一个空栈的顶部元素，会导致RE（Runtime Error）。（当然也可以修改增加判断非空语句）

---

动态数组（向量）

操作

创建向量（初始化一个长度为0的向量）：vector<元素名> 向量名;

取向量首元素的迭代器：向量名.begin();

取向量尾元素的下一地址：向量名.end();

取向量首元素的值：向量名.front();

取向量尾元素的值：向量名.back();

下标形式访问：向量名[下标]（类似于普通数组）

✭✭✭往尾部添加一个元素：向量名.push_back(value);

删除尾部第一个元素：向量名.pop_back();

判断向量是否为空：向量名.empty();

求向量元素个数（而非容量）：向量名.size();

翻转向量：reverse(向量名.begin(), 向量名.end());

经典应用----邻接表

        对于一个Map来说，假如有1e5个点，那么就要建立一个1e5*1e5的矩阵来表示，但是这样占用内存过多，同时浪费严重（因为不一定每两个点之间都会连线）。邻接表（本质上就是vector版的结构体数组）可以解决这个问题。

eg.

struct edge{ int from, to, value; }    //边的起点、终点、权值
const int maxn = 1e5 + 5;
vector<edge> Map[maxn];

（这其中的from变量也可以省略，直接由数组的下标来表示起点）

---

集合（堆，二叉树）

介绍

一个有序的容器，里面的元素都已经排列好，支持插入、删除、查找等，而且所有的操作都是严格在log(n)时间内完成，效率非常高。（优点：自动去重并且排序）（但是只能使用迭代器访问）

操作

创建集合：set<元素名> 集合名;

清空集合：集合名.clear();

取集合首元素的迭代器：集合名.begin();

取集合尾元素的下一地址：集合名.end();

插入一个元素：集合名.insert(元素);

        （注意：如果集合中之前没有这个元素，那么就可以插入并自动排序；假如有就不插入。）

查找是否有某个元素：集合名.count(元素);

查找某元素并返回迭代器：集合名.find(元素);        （返回值（迭代器）的类型为set<int>::iterator）

判断是否为空集：集合名.empty();

求集合元素个数：集合名.size();

删除元素：集合名.erase(元素);

使用降序排列（默认升序）：set<int, greater<int> > 集合名;        （迭代器的类型为set<int， greater<int> >::iterator）

注意

当使用string类型作为set的键时，由于map只有在key不同时才会插入数据，可是一个string类型本质上是一个指向char的指针，每一次插入值都相同，所以会被map忽略。（如果必须要比较字符串，那么就只能重载map中的比较函数。）

---

字符串类

操作

求字符串的长度：字符串名.length();        或者        字符串名.size(); 

字符串的连接：可直接使用+或者+=

字符串的比较：可直接使用比较符号

取字符串的子串：字符串名.substr(下标开始位置, 取几个);        （“取几个”可省略）

插入字符串：字符串名.insert(下标开始处, 插入的字符串);

删除字串：字符串名.erase(下标开始处, 删除的长度);

交换两个字符串的内容：字符串名1.swap(字符串名2);

清空字符串：字符串名.clear();

字符串的查找（返回第一次出现的位置）：字符串名.find(要查找的字符串名);

还可以使用STL算法直接操作字符串：

        例如sort(字符串名.begin(), 字符串名.end())、next_permutation(字符串名.begin(), 字符串名.end())、reverse(字符串名.begin(), 字符串名.end()) ......

---

映射

介绍

map是一个“键值对”（key/value）容器，迭代器可以修改value但不可以修改key。

map会根据key自动排序。

map可以使用键（key）作为下标（而非数组中的位置）来获取一个值。

操作

定义一个空映射：map<key类型名, value类型名> 映射名;

返回是否存在该键：映射名.count(键);         （只会返回0或1）

返回指向相应键的迭代器，否则返回结束地址end()：映射名.find(键);

删除相应键的元素（或者迭代器所指向的元素），返回是否成功删除：映射名.erase(键/迭代器);

向映射中插入一个键值对：映射名.insert(键值对名);        （如果该键已存在，那么就不操作）

        即：映射名.insert(pair<key类型名, value类型名>(键,值)); 

清空映射：映射名.clear();

---

STL算法--next_permutation

介绍

用于生成序列的全排列。

若当前已到最大字典序，那么就返回false（如例中的{3, 2, 1}）。

例

int a[] = {1, 2, 3};
do
{
	cout << a[0] << " " << a[1] << " " << a[2] << endl;
} while(next_permutation(a, a+3));

---

STL算法--prev_permutation

介绍

与由next_permutation相反，原排列得到字典序中上一个最近排列。