河南建设银行网站,深圳公司网站推广,金华企业自助建站系统,学校网络建设方案设计目录
一、栈的模拟和deque容器
1.deque
1.1deque结构
1.2deque优缺点
2.stack模拟
二、队列的模拟
三、priority_queue优先级队列
1.优先级队列模拟
2.添加仿函数 一、栈的模拟和deque容器
在之前#xff0c;我们学过了C语言版本的栈#xff0c;可以看这篇文章 栈和…
目录
一、栈的模拟和deque容器
1.deque
1.1deque结构
1.2deque优缺点
2.stack模拟
二、队列的模拟
三、priority_queue优先级队列
1.优先级队列模拟
2.添加仿函数 一、栈的模拟和deque容器
在之前我们学过了C语言版本的栈可以看这篇文章 栈和队列。
但是C语言没有模板我们只能固定一个类型去写在C中引入了模板的概念我们只需要写一份在调用中给到类型编译器会自动去帮我们推导是栈里面元素的类型会非常方便。
1.deque
我们可以看到库函数里面的栈调用的是一个deque容器。 deque(双端队列)是一种双开口的连续空间的数据结构双开口的含义是可以在头尾两端进行插入和删除操作且时间复杂度为O(1)与vector比较头插效率高不需要搬移元素与list比较空间利用率比较高。 1.1deque结构
首先deque有一个中控数组这个数据是指针数组存放的内容是指针每个指针都指向的一块空间的起始地址。 他的迭代器有 cur当前数据当前位置 fisrt数据起始位置last数据结尾位置 node指向数据的指针。 头插就去找到最前面的那个有效指针进行头插尾插就找最后面那个有效指针尾插遍历就通过迭代器每一个空间块从头遍历到位就换下一个空间块。 1.2deque优缺点
deque实际上是一个缝合怪他结合了vector和list的内容将他们糅合在了一起。
优点 与vector比较deque的优势是 头部插入和删除时不需要搬移元素效率特别高而且在扩容时也不需要搬移大量的元素因此其效率是必vector高的。 与list比较其底层是连续空间空间利用率比较高不需要存储额外字段。 但是他也有缺点 deque容器不适合遍历因为在遍历时deque的迭代器要频繁的去检测其是否移动到某段小空间的边界导致效率低下而序列式场景中可能需要经常遍历因此在实际中需要线性结构时大多数情况下优先考虑vector和list。 那么为何他能在栈和队列中使用并成为默认容器呢 因为栈和队列需要尾插尾删队列需要尾插头删deque容器完全可以适配这些需求因为不需要遍历并且deque扩容时不需要挪动数据这也是的deque的效率变高。 2.stack模拟
stack的模拟非常简单调用模板Container容器的函数就可以了也不需要迭代器不用遍历也不需要构造函数析构函数什么的因为Container容器是自定义类型会自动调用的相关构造析构拷贝函数。
#pragma once
#includedeque
namespace kky
{templateclass T, class Container dequeTclass stack{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_back();}const T top(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}
二、队列的模拟
队列模拟跟stack差不都多了一个back接口出数据的时候要调用pop_front()
#pragma once
#includedeque
namespace kky
{templateclass T, class Container dequeTclass queue{public:void push(const T x){_con.push_back(x);}void pop(){_con.pop_front();}const T front(){return _con.front();}const T back(){return _con.back();}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}
三、priority_queue优先级队列
优先级队列出数据的时候会先出优先级高的数据。
如何来判断优先级的高低呢 这跟你传的数据类型有关先举个例子 我们插入了 1,10,8,5,6 但出数据的时候缺省按照数据的大小顺序来出的在这里使用数据的大小来看段他们优先级的高低。 优先级队列出数据时会帮我们做好排序他的本质就是堆通过堆的向上向下调整来处理优先级问题。具体堆排序的过程可以看选择排序中的堆排序。
1.优先级队列模拟 优先级队列的模拟实现就是要建堆每一次插入数据都要进行向上调整保证是大堆或者小堆。 出数据的时候将第一个数据和最后一个数据互换再进行尾删因为第一个数据是我们想要出的数据将他和最后一个数据交换再尾删就可以提取出这个数据了同时现在只有第一个元素不符合小堆或者大堆的情况其他元素都符合因此进行一次从索引为0位置的向下调整即可。 namespace kky
{templateclass T,class Container vectorTclass priority_queue{public:void adjust_up(size_t child){while(child0){size_t parent (child - 1) / 2;if (_con[child] _con[parent]){swap(_con[child], _con[parent]);child parent;}else{break;}}}void adjust_down(size_t parent){int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() _con[child] _con[child 1]){child;}if (_con[child] _con[parent]){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}void push(const T x){_con.push_back(x);adjust_up(_con.size()-1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
}
刚刚的代码构建了一个大堆但是我们如果想要构建小堆难不成又要重写一份代码吗 那必定不是可能的。
2.添加仿函数
在C语言中我们可以通过函数指针来处理顺序的问题但是函数指针类型很繁琐并且不容易理解C推出了仿函数来帮助我们处理这类问题。
写一个类仅仅重载了operator()返回类型为bool在后面进行判断的时候我们就可以调用这个类对象的()类似于函数一样就可以处理了
templateclass T
class Less
{
public:bool operator()(const T x1, const T x2){return x1 x2;}
};
第一个方式太丑陋了一般使用第二种方式去调用。 那之前我们代码中的判断语句都可以通过调用仿函数更改了
给模板参数再添加一个类
templateclass T, class Container vectorT,class Compare LessT
现在就可以开始更改了 只需要注意顺序即可需要这样判断的都可以更改参考如下代码
namespace kky
{templateclass T, class Container vectorT,class Compare LessTclass priority_queue{public:void adjust_up(size_t child){Compare com;while (child 0){size_t parent (child - 1) / 2;if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);child parent;}else{break;}}}void adjust_down(size_t parent){Compare com;int child parent * 2 1;while (child _con.size()){if (child 1 _con.size() com(_con[child], _con[child1])){child;}if (com(_con[parent], _con[child])){swap(_con[child], _con[parent]);parent child;child parent * 2 1;}else{break;}}}void push(const T x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){swap(_con[0], _con[_con.size() - 1]);_con.pop_back();adjust_down(0);}T top(){return _con[0];}bool empty(){return _con.empty();}size_t size(){return _con.size();}private:Container _con;};
} 这是我们写的Less仿函数如果你想让优先级队列建小堆就可以写再写一个仿函数
templateclass T
class Greater
{
public:bool operator()(const T x1, const T x2){return x1 x2;}
};
需要的时候调用一下即可
