STL教程6-deque、stack、queue、list容器

目录

• 一、deque双口队列
• • 1、deque概述
  • 2、deque常用api
  • • 1）构造函数
    • 2）赋值操作assign
    • 3）swap交换内存空间
    • 4）大小操作size()、empty()、resize(n)
    • 5）插入和删除和查看数据
• 二、stack容器
• • 1、初始化
  • 2、push放置元素和pop弹出元素
  • 3、查看栈顶元素不弹出top()
  • 4、stack的大小size(),判断为空empty()
  • 5、迭代栈
• 三、queue容器
• • 1、初始化
  • 2、push放置元素和pop弹出元素
  • 3、查看栈顶元素不弹出front()
  • 4、queue的大小size(),判断为空empty()
  • 5、迭代栈
• 四、list链表
• • 1、构造
  • 2、插入和删除元素
  • 3、大小操作
  • 4、赋值操作
  • 5、front back返回第一个和最后一个元素
  • 6、反转元素reverse()
  • 7、排序sort

一、deque双口队列 1、deque概述

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

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

2、deque常用api 1）构造函数

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

2）赋值操作assign

	deque d1;
	deque d2;
	deque d3;
	d1.assign(10, 5);
	d2.assign(d1.begin(), d1.end());//迭代器指定区间赋值
	d3 = d2;//等号赋值

3）swap交换内存空间

d1.swap(d2);//交换

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

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

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

pop_front()没有返回值

	deque d1;
	d1.push_back(100);//尾部插入
	d1.push_front(200);//头部插入
	
	int val = d1.front();//拿到被删除的元素
	d1.pop_front();//删除（无返回值）
	val = d1.back();
	d1.pop_back();

二、stack容器

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

stacks1;

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

1、初始化

stacks1;
stacks2(s1);//用s1初始化s2
stack s3;
s3 = s2;//用s2初始化s3

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

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

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

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

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

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

5、迭代栈

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

while (!s1.empty()) {
		cout << s1.top()< 
三、queue容器 
queue是一种操作受限的线性表，只允许在队首删除（出队），队尾插入（入队)，其特点是先进先出
 不能进行遍历，不提供迭代器，不支持随机访问
 
1、初始化 
queues1;
queues2(s1);//用s1初始化s2
queue s3;
s3 = s2;//用s2初始化s3
 
2、push放置元素和pop弹出元素 
q.push(3);
q.pop();
 
3、查看栈顶元素不弹出front() 
cout << s1.front() << endl;
 
4、queue的大小size(),判断为空empty() 
s.empty(); //判断queue是否为空
s.size(); //返回queue大小
 
5、迭代栈 
栈没有迭代器，只能用empty或者size判断
 
while (!q1.empty()) {
		cout << q1.front()< 
四、list链表 
链表是由一系列的节点组成，结点包含两个域，一个数据域，一个指针域。
 链表内存是非连续的
 链表只有在需要的时候才分配内存
 
1、构造 
list mlist1;//可以无参构造
listmlist2(10, 9);//10个9
listmlist3(mlist2);//拷贝构造，用mlist2构造mlist3
listmlist4(mlist2.begin(), mlist2.end());//迭代器构造
 
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::iterator it = mlist.begin();
	it++;//不能直接it+5，只能it++
	it++;
	mlist.insert(it, 500);//在第三个位置插入
 
删除操作，主要有pop_back、pop_front
 
	mlist.pop_back();//在尾部删除
	mlist.pop_front();//在头部删除
	mlist.erase(mlist.begin(), mlist.end());//删除区间的元素
	mlist.clear();//删除所有元素
	mlist.remove(200);//删除容器中所有的200，list特有的一个函数
 
3、大小操作 
size();//容器元素的个数
empty();//判断容器是否为空
resize(1);//指定容器的长为1
 
4、赋值操作 
assign(n,elem);//将n个elem拷贝赋值给自身
s1.swap(s2);//交换元素，实际交换的空间的指针
 
5、front back返回第一个和最后一个元素 
q.front();
q.back();
 
6、反转元素reverse() 
	list mlist;
	//自己写方法
	for (int i = 0; i < 10; i++)
	{
		mlist.push_back(i);
	}
	mlist.reverse();//使用内置方法反转
 
7、排序sort 
aa.sort();//默认从小到大

//写个回调函数
bool mycmp(int v1, int v2)
{
	return v1 > v2;
}
mlist.sort(mycmp);//从大到小