目录

一. stack 容器

 stack 常用api

（1）stack 构造函数

（2）stack 赋值操作

（3）stack 数据操作

二. queue 容器

queue 常用api

（1）queue 构造函数

（2）queue 赋值操作

（3）queue 数据操作

三. list 容器（重点）

list 常用api

（1）list 构造函数

（2）list 数据元素插入和删除操作

（3） list 大小操作

（4）list 赋值操作

（5）list 数据操作

（6）list 反转排序

---

一. stack 容器

stack 是一种先进后出的数据结构，只有一个出口。

stack 所有元素的进出都必须符合“先进后出”的条件，只有stack 顶端的元素才会被外界取用。

stack 不提供遍历功能，也不提供迭代器。

 stack 常用api

（1）stack 构造函数

stack s;            //stack采用模板类实现，stack对象的默认构造形式
stack(const stack& s); //拷贝构造函数

（2）stack 赋值操作

stack& operator=(const stack& s);  //重载等号运算符

（3）stack 数据操作

push(elem);   //向栈顶添加元素
pop();        //从栈顶移除一个元素
top();        //返回栈顶元素
empty();      //判断栈顶是否为空
size();       //返回堆栈的大小

 

 

二. queue 容器

queue 是一种先进先出的数据结构，有两个出口，允许从一段新增元素，从另一端移除元素。

queue 不提供遍历功能，也不提供迭代器。

queue 常用api

（1）queue 构造函数

queue q;            //queue采用模板类实现，queue对象的默认构造形式
queue(const queue& q); //拷贝构造函数

（2）queue 赋值操作

queue& operator=(const queue& q);  //重载等号运算符

（3）queue 数据操作

push(elem);   //往队尾添加元素
pop();        //从队头移除一个元素
back();       //返回最后一个元素
front();      //返回第一个元素
empty();      //判断队列是否为空
size();       //返回队列的大小

三. list 容器（重点）

list 和 vector 是两个最常用的容器。

list 容器的数据结构：

list 容器是一个循环的双向链表。

list 的特点：

• 每次插入或删除一个元素，就是配置或者释放一个元素的空间；
• 采用动态存储分配，不会造成内存浪费和溢出；
• 链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素；
• 链表灵活，但是空间和时间额外耗费较大。

 list 的迭代器：

list 容器不能像 vector 一样以普通指针作为迭代器，因为其节点不能保证在同一块连续的内存空间上。

list 迭代器必须有能力指向list 的节点，并有能力进行正确的递增、递减、取值、成员存取操作（递增时指向下一个节点，递减时指向上一个节点，取值时取的是节点的数据值，成员取用时取的是节点的成员）。

由于 list 是一个双向链表，迭代器必须能够前移、后移，所以 list 的迭代器是双向迭代器。

插入和删除操作都不会造成原有 list 迭代器的失效。list 元素的删除，也只有被删除的那个元素的迭代器失效，其他迭代器不受影响。这在vector是不成立的。 

list 常用api

（1）list 构造函数

list lstT;     //list采用模板类实现,对象的默认构造形式：
list(begin,end);  //构造函数,将[begin, end)区间中的元素拷贝给本身。
list(n,elem);     //构造函数,将n个elem拷贝给本身。
list(const list &lst);  //拷贝构造函数。

（2）list 数据元素插入和删除操作

push_back(elem);       //在容器尾部加入一个元素
pop_back();            //删除容器中最后一个元素
 
push_front(elem);      //在容器开头插入一个元素
pop_front();           //从容器开头移除第一个元素
 
insert(pos,elem);      //在pos位置插elem元素的拷贝，返回新数据的位置。
insert(pos,n,elem);    //在pos位置插入n个elem数据，无返回值。
insert(pos,begin,end); //在pos位置插入[begin,end)区间的数据，无返回值。
 
clear();               //移除容器的所有数据
erase(begin,end);      //删除[begin,end)区间的数据，返回下一个数据的位置。
erase(pos);            //删除pos位置的数据，返回下一个数据的位置。
remove(elem);          //删除容器中所有与elem值匹配的元素。

（3） list 大小操作

size();      //返回容器中元素的个数
empty();     //判断容器是否为空
resize(num); //重新指定容器的长度为num，
             //若容器变长，则以默认值填充新位置。
             //如果容器变短，则末尾超出容器长度的元素被删除。
resize(num, elem); //重新指定容器的长度为num，
                   //若容器变长，则以elem值填充新位置。
                   //如果容器变短，则末尾超出容器长度的元素被删除。

（4）list 赋值操作

assign(begin, end);   //将[begin, end)区间中的数据拷贝赋值给本身。
assign(n, elem);      //将n个elem拷贝赋值给本身。
list&operator=(const list &lst);//重载等号操作符
swap(lst);            //将lst与本身的元素互换。

（5）list 数据操作

front();  //返回第一个元素。
back();   //返回最后一个元素。

（6）list 反转排序

reverse(); //反转链表，比如lst包含1,3,5元素，运行此方法后，lst就包含5,3,1元素。
sort();    //list排序