一、deque双口队列

1、deque概述

前后两端都能插入和删除，push_front(),pop_front(),push_back(),pop_back()
特点

• 双端插入和删除元素效率较高
• 指定位置插入会导致数据元素移动，效率会很低
• 可随机存取，效率高
  
  就像上图一样，有三个地址指向了三块分段连续区域，如果在头部插入插满了，那么就会重新申请内存，然后修改指向这块的指针

2、deque常用api

1）构造函数

	deque<int> d1;
	deque<int> d2(10, 2);//10个2
	deque<int> d3(d2.begin(), d2.end());//迭代器方式
	deque<int> d4(d3);//用d3初始化
1
2
3
4

2）赋值操作assign

	deque<int> d1;
	deque<int> d2;
	deque<int> d3;
	d1.assign(10, 5);
	d2.assign(d1.begin(), d1.end());//迭代器指定区间赋值
	d3 = d2;//等号赋值
1
2
3
4
5
6

3）swap交换内存空间

d1.swap(d2);//交换
1

4）大小操作size()、empty()、resize(n)

if (d1.empty()){}//判断是否为空
d1.size();//返回容器中元素的个数
d1.resize(5);//元素如果超过5，那么只保留前几个
1
2
3

5）插入和删除和查看数据

pop_front()没有返回值

	deque<int> d1;
	d1.push_back(100);//尾部插入
	d1.push_front(200);//头部插入
	
	int val = d1.front();//拿到被删除的元素
	d1.pop_front();//删除（无返回值）
	val = d1.back();
	d1.pop_back();
1
2
3
4
5
6
7
8

二、stack容器

在STL中 queue 和 stack 其实并不叫容器(container)，而是叫适配器(adapter)，他们是对容器的再封装。
stack是一种“先进后出”的结构。栈不能遍历，不支持随机存取，只能通过top从栈顶获取和pop()删除元素。

stack<int>s1;
1

stack采用模板类实现， 尖括号里面能放置基本数据类型或者对象或者自定义类型。

1、初始化

stack<int>s1;
stack<int>s2(s1);//用s1初始化s2
stack<int> s3;
s3 = s2;//用s2初始化s3
1
2
3
4

2、push放置元素和pop弹出元素

s1.push(3);
s1.pop();
1
2

3、查看栈顶元素不弹出top()

cout << s1.top() << endl;
1

4、stack的大小size(),判断为空empty()

s.empty(); //判断堆栈是否为空
s.size(); //返回堆栈的大小
1
2

5、迭代栈

栈没有迭代器，只能用empty或者size判断

while (!s1.empty()) {
		cout << s1.top()<<endl;
		 s1.pop();
	}
1
2
3
4

三、queue容器

queue是一种操作受限的线性表，只允许在队首删除（出队），队尾插入（入队)，其特点是先进先出
不能进行遍历，不提供迭代器，不支持随机访问

1、初始化

queue<int>s1;
queue<int>s2(s1);//用s1初始化s2
queue<int> s3;
s3 = s2;//用s2初始化s3
1
2
3
4

2、push放置元素和pop弹出元素

q.push(3);
q.pop();
1
2

3、查看栈顶元素不弹出front()

cout << s1.front() << endl;
1

4、queue的大小size(),判断为空empty()

s.empty(); //判断queue是否为空
s.size(); //返回queue大小
1
2

5、迭代栈

栈没有迭代器，只能用empty或者size判断

while (!q1.empty()) {
		cout << q1.front()<<endl;
		 q1.pop();
	}
1
2
3
4

四、list链表

链表是由一系列的节点组成，结点包含两个域，一个数据域，一个指针域。
链表内存是非连续的
链表只有在需要的时候才分配内存

1、构造

list<int> mlist1;//可以无参构造
list<int>mlist2(10, 9);//10个9
list<int>mlist3(mlist2);//拷贝构造，用mlist2构造mlist3
list<int>mlist4(mlist2.begin(), mlist2.end());//迭代器构造
1
2
3
4

2、插入和删除元素

插入操作，主要有push_back、push_front、insert

	mlist.push_back(100);//在头部插入
	mlist.push_front(200);//在尾部插入
	mlist.insert(mlist.begin(), 300);//迭代器插入，插入300
	mlist.insert(mlist.end(), 400);
	list<int>::iterator it = mlist.begin();
	it++;//不能直接it+5，只能it++
	it++;
	mlist.insert(it, 500);//在第三个位置插入
1
2
3
4
5
6
7
8

删除操作，主要有pop_back、pop_front

	mlist.pop_back();//在尾部删除
	mlist.pop_front();//在头部删除
	mlist.erase(mlist.begin(), mlist.end());//删除区间的元素
	mlist.clear();//删除所有元素
	mlist.remove(200);//删除容器中所有的200，list特有的一个函数
1
2
3
4
5

3、大小操作

size();//容器元素的个数
empty();//判断容器是否为空
resize(1);//指定容器的长为1
1
2
3

4、赋值操作

assign(n,elem);//将n个elem拷贝赋值给自身
s1.swap(s2);//交换元素，实际交换的空间的指针
1
2

5、front back返回第一个和最后一个元素

q.front();
q.back();
1
2

6、反转元素reverse()

	list<int> mlist;
	//自己写方法
	for (int i = 0; i < 10; i++)
	{
		mlist.push_back(i);
	}
	mlist.reverse();//使用内置方法反转
1
2
3
4
5
6
7

7、排序sort

aa.sort();//默认从小到大

//写个回调函数
bool mycmp(int v1, int v2)
{
	return v1 > v2;
}
mlist.sort(mycmp);//从大到小
1
2
3
4
5
6
7
8