徐州网站建设案例,南京设计网站,门户网站推广方案,做网站渠道目录
前言#xff1a;
1 Stack
1.1 双端队列
2 Queue 前言#xff1a;
经历了list三个自定义类型的洗礼#xff0c;来个简单的放松放松#xff0c;即栈和队列#xff1a; 文档记录的#xff0c;栈和队列是一种容器适配器#xff0c;它们不属于stl#xff0c;但是它…目录
前言
1 Stack
1.1 双端队列
2 Queue 前言
经历了list三个自定义类型的洗礼来个简单的放松放松即栈和队列 文档记录的栈和队列是一种容器适配器它们不属于stl但是它们的大体结构我们都是了解的在数据结构初阶我们已经用了C语言进行实现这里用C进行实现。 1 Stack
根据文档stack也是使用了模板第一个参数是数据类型那么第二个是
我们在C语言阶段使用的是一个整型指针一个size一个capacity来实现如果我们在C仍然这样实现就不用介绍了没意思了就。
后面的参数deque是另一种结构叫做双端队列后面细说为什么引入第二个模板参数呢
因为我们有了vector list基础完全可以复用的为什么复用vector list就和deque有关了。
1.1 双端队列
deque是双端队列那么为什么在stack queue的模板参数里面都有这个结构呢
因为这个结构集成了vector和list但是不是只集成了它们的优点。 先简单谈谈deque的结构
list的优点是插入删除效率很高缺点是不好访问数据vector的优点是访问任意数据的效率很高缺点是插入删除数据如果在头部或者中间的效率很低。
所以惠普的大佬就寻思再来一个结构可以当vector用也可以当list使用这里因为是了解所以就直接给结构了: 看起来就像是个大boss当我们存数据的时候该结构会开一块空间比如叫buff空间大小为16当一直插入数据该数据插满之后不会扩容会重新开一块空间空间大小也是16数据插好后我们该如何快速访问呢 假定开的空间大小不变我们想访问第i个数据一块空间的大小为N那么我们就应该先找到i数据在第几个空间的在找该数据在第几个找到在哪个空间可以i / N第几个可以i % N这样就可以快速访问了。
那么这么多空间应该如何管理
这里使用的是中控指针即再开一块空间这块空间里面只有指针指针指向不同的空间但是指针是从中间开始存储的因为涉及到头插。
但是对于deque的结构来说只有两个迭代器一个迭代器有4个指针分别指向当前节点头结果尾节点和中控指针的节点如果涉及到了插入删除数据比如头插就要先开一块空间倒着存数据那么此时找数据i就要先减去这个不满的第一个数据块的数据个数才能通过/ % 快速访问数据。中间插入数据的时候有两个选择一是重新开空间二是在原来的空间上扩容但是扩容之后每个空间的大小不一样找数据的效率就会降低了。
当涉及删除数据的时候删除了之后后面的数据往前移动比较麻烦。
所以别看deque集成了list vector缺点也蛮多的。
比如访问数据的效率不极致中间插入删除数据也没list快它就比较尴尬。。
这也是为什么stack queue的模板参数默认是deque这个大哥虽然有点缺点但是用起来也算不错。 我们在stack实现的接口有入栈 出栈 size empty 返回栈顶元素只有5个接口这5个接口在vector里面都有所以直接使用
namespace Free3
{template class T, class container vectorTclass stack{public:void push(const T val){_con.push_back(val);}size_t size(){return _con.size();}bool empty(){return _con.empty();}T top(){return _con.back();}void pop(){_con.pop_back();}private:container _con;};}
这里有个很牛逼的点就是模板参数也可以有缺省值我们给上vectorint那么默认的用vector来实现stack。
测试代码如下
#include Stack.h
using namespace Free3;
int main()
{Free3::stackint, vectorint s1;Free3::stackint s2;s1.push(1);s1.push(2);s1.push(3);s1.push(4); s2.push(1);s2.push(2);s2.push(3);s2.push(4);s2.push(5);while (!s2.empty()){cout s2.top() ;s2.pop();}cout endl;return 0;
} 2 Queue
队列这里还有点不一样栈可以用vector也可以用list但是队列不行队列的出队相当于是头删如果非要用vector里面的erase来头删也可以但是效率很差是O(N)这里就非常不推荐所以队列就用list来实现。
namespace Free4
{templateclass Tclass Queue{public:void push(const T val){_con.push_back(val);}void pop(){_con.pop_front();}size_t size(){return _con.size();}T front(){return _con.front();}bool empty(){return _con.empty();}private:listT _con;};} 感谢阅读
