STL 实现线性表,栈,队列

1、STL (Standard Template Library标准模板库) 是通用类模板和算法的集合，它提供给程序员一些标准的数据结构的实现如 queues(队列), lists(链表), 和 stacks(栈)等.

2、C++ STL 提供给程序员以下三类数据结构的实现:
  1、顺序容器：存放同一类型的且按线性表存放数据的容器
        C++ Vectors 向量容器：（数组）
                特点：数组，访问很方便。插入和删除效率低（动态数组）
                 注：插入或删除会引用迭代器失效。    （***）
           
        C++ Double-Ended Queues ：双向队列
        C++ Lists   链表：它允许快速的插入和删除，但是随机访问却比较慢. 
                    注：迭代器不会因插入和删除失效

    2容器适配器：由于上述容器中不仅有进队/出队，插入操作，为了特定的算术在此基础进行修改
                1.栈（将容器的类的其他封装，只提供操作接口）
                    C++ Stacks 
                2.队列
                    C++ Queues 
                3、优先队列 
                    C++ Priority Queues     
        
     关联容器：通过Key-Value方式来操作数据。每一个都对应一个Key（索引） 
        1、一级关联
           关联容器：
                map：Key-value  
                实例化：  map<key,value>  对象 
                i注：必须添加时以键-值对来添加'
            iterator insert( iterator pos, const pair<KEY_TYPE,VALUE_TYPE> &val );
                template<typename T1,Typename T2>
                class pair
                {
                public:
                    pair(T1&,T2&);
                    //属性：Key
                    T1& first;    //指向该Key-value中的key
                    T2& second; //指向该Key-value中的key
                };
            集合：
            set
        2、二级关联

    联合容器 
        C++ Bitsets 
        C++ Maps 
        C++ Multimaps 
        C++ Sets 
        C++ Multisets 

3、容器类：STL提供了相关类模板 

    3.1栈：FILO操作数据stack
        头文件：#include<stack>    
    3.2    C++队列是一种容器适配器，它给予程序员一种先进先出(FIFO)的数据结构。 
        头文件　#include<queue>
        
    3.3Vectors 数组：包含着一系列连续存储的元素,其行为和数组类似。    
        头文件#include<vector>
            size_type maxsize（）    返回该系统能分配数组空间上限
    
4、迭代器：在Vector，list等类中提供遍历元素的一个指针。可以通过运算符与
  方法去指向每一个元素。
  1、定义 迭代器
    以Vector为例：  Vector<类型>::迭代器  对象;

 

   STL 实现线性表,栈,队列的操作,迭代器,逆迭代器,链表线性表 .

#include<iostream>
//头文件
#include<stack>
#include<queue>
#include<vector>
using namespace std;

//通过vector来存储10个people对象，并遍历输出
int main()
{
//实例化：类名<类型>  对象;
//	栈
	stack<int> s;//无参构造器
	s.push(1);
	s.push(2);
	cout<<s.size()<<endl;
	
	while(!s.empty())
	{
		//先取出
		cout<<s.top()<<endl;
		//再移除
		s.pop();
	}

//队列： queue:  FIFO特点：从队尾进  从队头出
	queue<float> q;//实例化：构造器
	cout<<q.size()<<endl;
	q.push(3.14);//
	q.push(5.79);
	cout<<q.size()<<endl;		

	//先取再除
	while(!q.empty())
	{
		cout<<q.front()<<endl;//头
		q.pop();
	}

//线性表：1:1   
//顺序线性表:类模板
	vector<int> v;	//实例化
	//vector<int> v(10,1);//插入10个1
	//插入方法	
	v.push_back(1);
	v.push_back(2);
	v.push_back(3);
	v.push_back(4);

	cout<<v.size()<<endl;	
	cout<<v.max_size()<<endl;
	//返回第3个元素
	cout<<v.at(2)<<endl;
	//插入元素
	//v.insert(5,100);
	//遍历
	int i=0;
	for(i=0;i<v.size();i++)
	{
		//cout<<v.at(i)<<endl;
		cout<<v[i]<<" ";
	}
	cout<<endl;
//迭代器：
	vector<int>::iterator it;
	it=v.begin();//指向第一个元素
	while(it!=v.end())
	{
		cout<< *it<<" ";
		it++;
	}
	cout<<endl;
//逆序迭代器
	vector<int>::reverse_iterator rit;
	rit=v.rbegin();//获取
	while(rit!=v.rend())	
	{
		cout<<*rit<<endl;
		rit++;
	}


//  链表线性表：
	//将v中的第1个元素到末尾元素复制给v1
	vector<int>  v1(v.begin(),v.end());	//区间   首地址   末尾地址
	vector<int>::iterator it1;
	it1=v1.begin();//获取首地址
	while(it1!=v1.end())
	{
		cout<<*(it1++)<<" ";
		
	}
	cout<<endl;
}