云南网站设计,网站制作公司天强科技,电子商务网站建设步骤有什么,顺德公益网站制作前言#xff1a;这篇文章我们将栈和队列两个容器放在一起进行分享#xff0c;因为这两个要分享的知识较少#xff0c;而且两者在结构上有很多相似之处#xff0c;比如栈只能在栈顶操作#xff0c;队列只能在队头和队尾操作。
不同于前边所分享的三种容器#xff0c;这篇…前言这篇文章我们将栈和队列两个容器放在一起进行分享因为这两个要分享的知识较少而且两者在结构上有很多相似之处比如栈只能在栈顶操作队列只能在队头和队尾操作。
不同于前边所分享的三种容器这篇文章要介绍的两个容器不再是单纯的空间创建存储而是以vector、list等容器为底层来实现的容器。 目录
一.栈
1.栈的框架 2.功能实现
二.队列
1.队列框架
2.功能实现
三.扩展
总结 一.栈
栈的关键在于只能从栈顶进行入栈和出栈那么我们就可以将vector或者list的头作为栈底在尾进行操作。 1.栈的框架
在数据结构的学习中我们已经知道栈有顺序栈和链式栈两种所以容器栈就可以按照需求通过模板来选择是创建顺序栈还是链式栈
#includevector
#includelistnamespace Mystack
{//stackint vectorint 顺序栈//stackint listint 链式栈templateclass T, class Container vectorTclass stack{public:private:Container _con;};
}
想要这样创建栈就必须包含vector和list两个容器的头文件。
通过使用两个模板参数一个代表数据类型一个代表栈的类型。Container即英文容器。
因为通常情况下所使用的栈都是顺序栈所以我们为了方便栈的创建可以将模板也写成缺省模板。缺省模板和缺省函数类似。 2.功能实现
我们直接来看 //入栈void push(const T x){_con.push_back(x);}//出栈void pop(){_con.pop_back();}//数据个数size_t size(){return _con.size();}//判空bool empty(){return _con.empty();}//栈顶元素const T top(){return _con.back();}
因为栈的底层是另外两种容器之一所以我们可以直接去调用它们的成员函数来实现我们的成员函数入栈就是尾插出栈即是尾删、依次类推。
测试如下 二.队列
队列不同于栈队列是在队尾插入元素在队头删除元素。但是我们知道vector并不支持头部的插入删除操作因为这样的效率很低所以我们只推荐使用list来作为队列的底层。 1.队列框架 templateclass T, class Container listTclass queue{public:private:Container _con;};
2.功能实现 //入队void push(const T x){_con.push_back(x);}//出队void pop(){_con.pop_front();}//队尾元素T back(){return _con.back();}const T back()const{return _con.back();}//队头元素T front(){return _con.front();}const T front()const{return _con.front();}//数据个数size_t size()const{return _con.size();}//判空bool empty()const{return _con.empty();}
仍然是调用list的成员函数来实现queue的成员函数测试如下 三.扩展
除了vector、list之外还有一种容器可以作为队列的底层——deque。 deque的底层是由多个长度相同的数组组成而这些数组则由一个指针数组来管理。
deque能够同时支持下标随机访问和头尾的插入删除所以除了队列之外在C的底层栈和队列实际上都是由deque来实现的。 这里我们不对deque进行展开讲解仅供小伙伴们了解。 总结
stack和queue的使用和模拟实现都非常简单也算是为前边学习的复杂模拟的一点小放松。
喜欢本篇文章的小伙伴记得一键三连我们下期再见
