欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

STL 实现线性表,栈,队列

程序员文章站 2022-05-14 22:13:48
...

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;
}

 

相关标签: 原创