STL学习笔记04-stack,queue,list容器

大家好，欢迎来到IT知识分享网。

1. stack容器-栈

stack是一种先进后出的数据结构，被称为栈，它只有一端可以出入。

• 栈中进入数据称为——入栈(push)
• 栈中弹出数据称为——出栈(pop)

stack的常用接口

1.1构造函数

stack<T> stk; //stack采用模板类实现，默认构造，T为数据类型，如int等 stack(const stack &stk); //拷贝构造 

1.2.赋值操作

stack& operator=(const stack& stk);//重载赋值运算符 

1.3.数据存取

push(elem); //入栈，向栈顶添加元素 pop(); //出栈，删除栈顶元素 top(); //返回栈顶元素 

1.4.大小操作

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

2. queque容器-队列

概念：queue是一种先进先出的数据结构，被称为队列，它的一端为入口(队尾入队)，另一端为出口(队首出队)

队列容器允许从一端添加元素，从另一端删除元素
队列中只有队头和队尾才可以被外界使用，因此队列不允许有遍历行为

使用deque需要包含头文件#include

2.1 构造函数

queue<T> que; //queue采用模板类实现，默认构造函数 queue(const queue& que); //拷贝构造 

2.2 赋值操作

queue& operator=(const queue& que);//重载赋值运算符 

2.3数据存取：

push(elem); //入队——往队尾添加元素 pop(); //出队——从队头删除元素 back(); //返回队尾元素 front(); //返回队头元素 

2.4 大小操作：

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

3. list容器-链表

list容器-双向循环链表
list底层是带头节点的双向循环链表

• 双向：可以从前往后，也可以从后往前遍历
• 循环：找尾节点的时间复杂度为O( 1 )
• 带头节点：代码实现简单，不用考虑链表为空等特殊情况，可令end()迭代器指向头节点的位置

sort等全局算法函数只能由支持随机访问的容器使用
不支持随机访问的容器内置有相应的算法成员函数

不支持随机访问-即不可使用下标语.at()函数访问。
优点：

• 1.可以在任意位置快速插入和删除元素
• 2.采用动态存储分配，不会造成内存浪费和溢出
  缺点：
• 1.占用空间比数组大
• 2.访问元素效率低，需要遍历链表才能访问元素
• 3.不能使用全局算法函数，sort等只能使用内置的成员函数
• 4.list支持任意位置的插入，注意list对象的迭代器不支持加减数字，因为其底层空间不连续，但i++，i–可以。

迭代器：

• 1.链表的存储方式不是连续的内存空间，因此链表list中的迭代器只支持前移和后移，属于双向迭代器
• 2.插入和删除操作都不会造成原有的迭代器失效 , 这在vector中不成立，因为vector的动态扩容机制会改变原有数据的存储地址，地址改变了，迭代器自然失效了

3.1 list的构造函数

函数原型：

 1.list<T> lst; //默认构造，list采用模板类实现 2.list(begin,end); //构造函数，利用迭代器实现区间赋值 3.list(n,elem); //构造函数，将n个elem赋值给本身 4.list(const list &lst); //拷贝构造 

3.2 list的赋值和交换

函数原型：

 1.list& operator=(const list& lst); //重载赋值运算符 2.assign(begin,end); //利用迭代器实现区间赋值 3.assign(n,elem); //将n个elem赋值给本身 4.swap(lst); //将lst于本身互换 

3.3 list的大小操作

函数原型：

 1.size(); //返回容器中元素个数 2.empty(); //判断容器是否为空 3.resize(num); //重新指定容器长度,若变长，变长的部分赋值为0, //若变短，超出容器长度的元素被删除 4.resize(num,elem); //重新指定容器长度,若变长，变长的部分赋值为elem //若变短，超出容器长度的元素被删除 

3.4 list的插入和删除

函数原型：

 1.push_back(elem); //在容器尾部插入一个元素 2.push_front(elem); //在容器头部插入一个元素 3.pop_back(); //在容器尾部删除一个元素 4.pop_front(); //在容器头部删除一个元素 5.insert(pos,elem); //在迭代器pos处插入一个元素elem,返回新数据的位置 6.insert(pos,n,elem); //在迭代器pos处插入n个元素elem,无返回值 7.insert(pos,begin,end);//在迭代器pos处插入[begin,end)区间的数据,无返回值 8.clear(); //清除容器中所有数据 9.erase(begin,end); //删除[begin,end)区间的数据,返回下一个数据的位置 10.erase(pos); //删除迭代器pos处的数据,返回下一个数据的位置 11.remove(elem); //删除容器中所有等于elem的元素 

3.5 list的数据存取

函数原型：

 1.front(); //返回容器第一个元素 2.back(); //返回容器最后一个元素 

3.6 list的反转与排序

1.reverse(); //反转链表 2.sort(); //排序链表。注意这是一个成员函数，测试中会解释