C++~~~stack容器、queue容器、list容器（p45-P56）
一、stack容器-基本概念
1.stack是一种先进后出（First in Last out，FILO）的数据结构，它有一个出口。
栈顶元素有push()、pop()、top（）等方法。
栈中只有顶端的元素才可以被外界使用，所以栈不允许有遍历操作。
栈可以判断容器为空empty()，栈可以返回元素的个数size()。
2.栈中只有顶端元素才可以被外界使用，所以栈不允许有遍历操作。
栈中进入数据成为入栈（push),栈中弹出元素数据称为出栈（pop)
3.stack常用接口：
功能描述：栈容器常用的对外接口
//构造函数：stack<T>stk;//stack采用模版类实现，stack对象的默认构造形式stack(conststack&stk);//拷贝构造函数//赋值操作stack&operator（conststack&stk);//重载等号操作符//数据存取push(elem);//向栈顶添加元素pop();//从栈顶移除第一个元素top();//返回栈顶元素//大小操作empty();//判断栈是否为空size();//返回栈的大小4.代码实现
#include<iostream>#include<stack>#include<algorithm>//标准算法的头文件usingnamespacestd;voidtest(){//特点：符合先进后出stack<int>s;//入栈s.push(10);s.push(20);s.push(30);s.push(40);cout<<"before stack pop,stack size is:"<<s.size()<<endl;//只要栈不为空，查看栈顶，并且执行出栈操作while(!s.empty()){//查看栈顶cout<<"stack top element:"<<s.top()<<endl;//出栈s.pop();}cout<<"After stack pop,stack size is:"<<s.size()<<endl;}intmain(){test();}//输出before stack pop,stack size is:4stack top element:40stack top element:30stack top element:20stack top element:10After stack pop,stack size is:0二、queue容器
1.概念：queue容器是一种先进先出（First in first out，FIFO）的数据结构，它有两个出口。
队列容器允许从一端新增数据，从另一端移除数据。
队列中只有队头和队尾元素可以被外界使用，因此队列不允许有遍历操作。
队列中进数据称为–入队（push）
队列中出数据成为—出队（pop)
队头（front）可以出队pop。
队尾（back）可以入队push。
2.函数原型
//构造函数queue<T>que;//queue采用模版类实现，queue对象的默认构造形式queue(constqueue&que);//拷贝构造函数//赋值操作queueoperator=（constqueue&que）；//重载等号操作符//数据存取push(elem);//队尾添加元素pop();//从队头移除第一个元素back();//返回最后一个元素front();//返回第一个元素//大小操作empty();//判断堆栈是否为空size();//返回栈的大小3.代码实现
//队列容器--queue#include<iostream>#include<queue>#include<algorithm>//标准算法的头文件usingnamespacestd;//队列queueclassPerson{public:Person(string name,intage){this->m_Name=name;this->m_Age=age;}string m_Name;intm_Age;};voidtest(){//创建队列queue<Person>q;//准备数据，初始化Personp1("唐僧",30);Personp2("孙悟空",20);Personp3("猪八戒",10);Personp4("沙和尚",50);//入队q.push(p1);q.push(p2);q.push(p3);q.push(p4);cout<<"queue size is:"<<q.size()<<endl;//判断只要队列不为空，查看队头，查看队尾，做出队的操作while(!q.empty()){//查看队头元素cout<<"queue head element name:"<<q.front().m_Name<<"queue head element age:"<<q.front().m_Age<<endl;//查看队尾元素cout<<"queue tail element name:"<<q.back().m_Name<<"queue tail element age:"<<q.back().m_Age<<endl;//出队q.pop();}}intmain()## 标题{test();}//输出queue size is:4queue head element name:唐僧queue head element age:30queue tail element name:沙和尚queue tail element age:50queue head element name:孙悟空queue head element age:20queue tail element name:沙和尚queue tail element age:50queue head element name:猪八戒queue head element age:10queue tail element name:沙和尚queue tail element age:50queue head element name:沙和尚queue head element age:50queue tail element name:沙和尚queue tail element age:50总结：
入队–push
出队–pop
返回队头元素—front
返回队尾元素—back
判断队伍是不是为空–empty
返回队列大小–size。
三、list基本容器–list基本概念
1.功能：将数据进行链式存储。
链表（list)是一种无力存储单元上非连续的存储结构，数据元素的逻辑顺序是通过链表中的指针链接实现的。
2.链表的组成：链表是由一系列节点组成。
3.节点的组成：一个是存储数据元素的数据域，另一个是存储下一个节点地址的指针域。
4.STL中的链表是一个双向循环链表。
所以list可以在头部进行插入和删除，比如push_front(),pop_front()。也可以在尾部进行插入和删除，比如push_back(),pop_back().
5.链表的优点：可以对任意位置进行快速插入和删除元素。
链表的缺点：链表对容器的遍历速度，没有数组快。链表占用的空间比数组占用的空间大。
6.由于链表的存储方式不是连续的内存空间，所以链表的list中的迭代器只支持前移和后移，属于双向迭代器。
list优点：
（1）采用动态存储分配，不会造成内存浪费和溢出。
（2）链表执行插入和删除操作十分方便，修改指针即可，不需要移动大量元素。
list缺点：
（1）链表灵活，但是空间（指针域）和时间（遍历）额外耗费较大。
List有个重要性质，插入操作和删除操作都不会造成原有list迭代器的失效，这在vector是不成立的。
总结：STL中的list和vector是2个常用的容器，各有优缺点。
四、list容器–构造函数
1.功能：创建list容器
2.函数原型：
//list采用模版类实现，对象的默认构造形式list<T>list;//构造函数将[beg,end)区间中的元素拷贝给本身list(beg,end);//构造函数将n个elem拷贝给本身list(n,elem);//拷贝构造函数list(constlist&list);3.代码实现
// list容器#include<iostream>#include<list>#include<algorithm>//标准算法的头文件usingnamespacestd;voidprintList(constlist<int>&L){for(list<int>::const_iterator it=L.begin();it!=L.end();it++){cout<<*it<<" ";}cout<<endl;}voidtest(){list<int>L1;//默认构造函数L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);//遍历容器printList(L1);//区间方式构造list<int>L2(L1.begin(),L1.end());printList(L2);//拷贝构造函数list<int>L3(L2);printList(L3);//n个elemlist<int>L4(10,10000);printList(L4);}intmain(){test();return0;}//输出10203040102030401020304010000100001000010000100001000010000100001000010000五、list容器–赋值和交换
1.功能描述：给list容器进行复制，以及交换list容器
2.函数原型
//将[beg,end)区间中的数据拷贝给本身assign(beg,end)；//讲n个elem拷贝赋值给本身assign(n,elem);//重载等号操作符list&operator=（constlist&list);//将list与本身元素互换swap(list);3.代码实现
// list容器赋值和交换#include<iostream>#include<list>#include<algorithm>//标准算法的头文件usingnamespacestd;voidprintList(constlist<int>&L){for(list<int>::const_iterator it=L.begin();it!=L.end();it++){cout<<*it<<" ";}cout<<endl;}//赋值voidtest(){list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);printList(L1);//等号赋值list<int>L2;L2=L1;printList(L2);//区间赋值list<int>L3;L3.assign(L2.begin(),L2.end());printList(L3);list<int>L4;L4.assign(10,100);printList(L4);}//交换voidtest02(){list<int>L1;L1.push_back(10);L1.push_back(20);L1.push_back(30);L1.push_back(40);list<int>L2;L2.assign(10,100);cout<<"Before swap:"<<endl;printList(L1);printList(L2);L1.swap(L2);cout<<"After swap:"<<endl;printList(L1);printList(L2);}intmain(){test02();}//输出Before swap:10203040100100100100100100100100100100After swap:10010010010010010010010010010010203040