网站搭建教程视频,网站制公司,天辰工程信息网,泰州网站关键词优化软件咨询❤️前言 今天这篇博客的内容主要关于STL中的stack、queue和priority_queue三种容器。
正文 stack和queue的使用方式非常简单#xff0c;我们只要根据之前学习数据结构的经验和文档介绍就可以轻松上手。于是我们直接开始对它们的模拟实现。
stack和queue的模拟实现 stack和q…❤️前言 今天这篇博客的内容主要关于STL中的stack、queue和priority_queue三种容器。
正文 stack和queue的使用方式非常简单我们只要根据之前学习数据结构的经验和文档介绍就可以轻松上手。于是我们直接开始对它们的模拟实现。
stack和queue的模拟实现 stack和queue我们在数据结构阶段就曾经学习过它们的底层结构都可以基于其他的基本数据结构进行实现。这时候我们就可以用到上篇文章中提到过的适配器模式来实现这两个模板。 实现方式只要遵从栈和队列的规则即可代码如下
templatetypename T, typename Container dequeT
class stack
{
public:bool empty() const{return _con.size() 0;}size_t size() const{return _con.size();}T top(){return *(--_con.end());}const T top() const{return *(--_con.end());}void push(const T x){_con.insert(_con.end(), x);}void pop(){_con.erase(--_con.end());}private:Container _con;
};templatetypename T, typename Container dequeT
class queue
{
public:void push(const T x){_con.insert(_con.end(), x);}void pop(){_con.erase(_con.begin());}T back(){return *(--_con.end());}const T back() const{return *(--_con.end());}T front(){return *(_con.begin());}const T front() const{return *(_con.begin());}size_t size() const{return _con.size();}bool empty() const{return _con.size() 0;}
private:Container _con;
}; 这里我们在使用这两个模板的时候可以传入两个模板参数分别为数据类型和空间适配器类型对于stack这样的容器我们可以传入vector作为空间适配器因为它的规则是后进先出我们只需要关注尾插尾删即可这样使用vector的效率是很高的。同理我们在使用queue时可以传入list作为空间适配器。使用了适配器模式我们的代码更加的简洁高效。 除此之外这里我们需要简单了解一下双端队列(deque)也就是上面给出的默认空间适配器。deque结合了数组和链表的特点本来是设计出来准备替代它们的产物但是显而易见它失败了(不然现在我们就不会学数组和链表了)。作为结合数组和链表的产物它的随机访问效率低于vector中间插入删除效率也很低虽然它缓解了一些vector和list本身的问题但是它总归替代不了vector和list。可以说deque的优势就是头插头删、尾插尾删效率很高这非常适合用来适配stack和queue。
优先级队列priority_queue 优先级队列(priority_queue)在数据结构中对应我们之前学的数据结构中的堆堆的使用也非常简单我们只要大概看看文档即可。除此之外堆根据堆内元素之间的关系被分为大根堆和小根堆堆的堆顶元素是整个堆中的最值这可以帮我们解决经典的Top-k问题。
优先级队列的模拟实现 在数据结构二叉树的学习阶段我们已经实现过堆的各种接口只要稍加改动设计就成了一个优先级队列的模板代码实现如下
templatetypename T, typename Container std::vectorT, typename Compare std::lessT
class priority_queue
{
private:void AdjustDown(int parent){int child 2 * parent 1;while (child _con.size()){if (child 1 _con.size() _cmp(_con[child], _con[child1])) child;if (_cmp(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);parent child;child 2 * parent 1;}else{break;}} }void AdjustUp(int child){int parent (child - 1) / 2;while (parent 0){if (_cmp(_con[parent], _con[child])){std::swap(_con[parent], _con[child]);child parent;parent (child - 1) / 2;}else{break;}}}
public:priority_queue() {}template typename InputIteratorpriority_queue(InputIterator first, InputIterator last){while (first ! last){_con.insert(_con.end(), *first);first;}}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T top() const{return *(_con.begin());}void push(const T x){_con.insert(_con.end(), x);AdjustUp(_con.size() - 1);}void pop(){std::swap(_con[0], _con[_con.size() - 1]);_con.erase(--_con.end());AdjustDown(0);}private:Container _con;Compare _cmp;
};首先我们看到优先级队列有三个模板参数除了存储数据类型以外还有空间适配器和仿函数。空间适配器想必大家比较熟悉了对于堆来说比较适合的类型就是数组vector。仿函数之前大家没有遇到过这里为大家附上一个博客链接大家可以看看
C 仿函数_仿函数 c_恋喵大鲤鱼的博客-CSDN博客https://blog.csdn.net/K346K346/article/details/82818801 简单来说仿函数就是一类可以当作函数使用的类它具有和函数指针类似的作用让我们可以轻松地控制生成许多效果不同的类减少了代码冗余。 而在优先级队列中这个仿函数的作用是比较堆节点的大小关系于是通过改变仿函数的种类我们能够控制大小堆以及元素间比较的方式优先级队列的默认仿函数为less也就是默认的大根堆这点需要注意。 当然在实现优先级队列的过程中调整位置的算法是比较难的点也希望大家能够多加练习巩固。
结语 以上就是今天博客的所有内容啦希望能够帮助到大家。
