【C++】stack、queue和priority_queue的模拟实现

在本篇博客中,作者将会讲解STL中的stackqueuepriority_queue的模拟实现,同时还会带大家了解一下deque这个容器。

一.什么是适配器

STL中一共有6大组件:容器,适配器,空间配置器,仿函数,迭代器,算法

其中像vector、list这种数据结构叫做容器,而像stack、queue这种数据结构叫做适配器

为什么呢?


因为stack和queue是通过deque这个容器转换过来的,也就是说,将deque容器的成员函数转换stackqueue成员函数

通过查看C++的手册,发现stack和queue类中有一个模板,其中第二个模板参数就是deque,即在stack和queue类中,是通过deque这个容器来实现的。


可能看到这里,还有同学不懂适配器到底是什么,那么在这里通过几张图来解释一下。 


在解释之前,我们来看看deque这个容器的具体的成员函数。

可以发现,deque这个容器的成员函数特别的多。 


接下来我们再看看stack和queue的成员函数。 

 

可以发现deque的成员函数特别的多,而stack和queue的成员函数特别的少,但是在stack和queue的实现中又用到了deque,所以要减少deque的成员函数来实现stack和queue。


如下图:

二.stack的模拟实现 

在C++库中,stack和queue都是通过使用deque容器来实现的,但是为了能够便于大家理解,在stack的模拟实现中,我们使用vector这个容器来实现,而在queue的模拟实现中,我们使用list这个容器来实现,实现完后,我们再来简单的了解一下deque。

stack的基本成员函数

首先我们来梳理一下stack的基本成员函数,看看这个数据结构需要用到那些功能。

empty:判断是否为空

size:求数据个数

top:取栈顶数据

push:入栈

pop:出栈

剩下的两个暂时不讲解。

stack模拟实现

梳理完stack的基本成员函数后,我们就可以来实现一下了。 

#pragma once
#include<iostream>
#include<vector>
using namespace std;namespace My_Stack
{//使用模板来给一个vector参数template<class T,class Container=vector<T>>class stack{public:stack(){}//入栈void push(const T& val){_s.push_back(val);}//出栈void pop(){_s.pop_back();}//判断是否为空bool empty() const{return _s.empty();}//获取数据个数size_t size() const{return _s.size();}//取栈顶数据T& top(){return _s.back();}//const类型取栈顶数据const T& top() const{return _s.back();}private:Container _s;};void Test1(){stack<int> s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout << s1.top() << " ";s1.pop();}}
}

三.queue的模拟实现

在模拟实现queue时,我们使用list这个容器来实现它,因为list提供的成员函数比较适合queue。 

queue的基本成员函数 

在实现queue之前,同样的,我们先来看看queue的基本成员函数。

empty:判断队列是否为空

size:获取数据个数

front:获取队头数据

back:获取队尾数据

push:入队列

pop:出队列

queue的模拟实现 

#pragma once
#include<iostream>
#include<list>namespace My_queue
{//模板参数给一个list容器template<class T,class Container=list<T>>class queue{public:queue(){}//入队列void push(const T& val){_l.push_back(val);}//出队列void pop(){_l.pop_front();}//取对头T& front(){return _l.front();}const T& front() const{return _l.front();}//取队尾T& back(){return _l.back();}const T& back() const{return _l.back();}//判断是否为空bool empty() const{return _l.empty();}//获取数据个数size_t size() const{return _l.size();}private:Container _l;};void Test1(){queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);cout << q1.size() << endl;while (!q1.empty()){cout << q1.front() << " ";q1.pop();}}
}

代码写到这里,stack和queue的模拟实现就基本完成了,但是在c++的STL中,实现stack和queue是通过使用deque这个容器来实现的

四.deque的简单介绍

在上面提到,stack和queue其实是通过使用deque这个容器来实现的,但是我们实现的时候为了便于大家理解,所以使用了vector和list来实现,那么现在,我们先来简单的了解一下的deque这个容器。

deque的基本介绍

首先,deque是一个顺序的存储结构,和vectorlist一样,都是顺着顺序来存储数据的,那么它们有什么区别吗,又或者说,为什么会出现deque这种数据结构?

在讲解之前,我们先来看看vector和list的缺点

vector和list的缺点

vector:头插头删效率低(因为要挪动数据)。

list:不能支持随机访问(在访问某个结点前,要先去遍历list去找到它)。

deque的出现

所以为了解决这两个容器的缺点,人们发明出了deque这种数据结构,也叫双端队列,这种队列头插头删尾插尾删时间效率为O(1),同时还能支持随机访问(但是它并不是真正意义上的随机访问)。

deque的结构

那么deque是如何实现的呢?deque通过数组指针指针数组来实现的。

通过这样的结构来实现,使deque的头插头删尾插尾删的效率非常的高,但是deque不适合遍历,因为deque是分开的连续空间,导致在其遍历时非常麻烦,具体的细节在这里不做讲解。 

deque实现stack和queue

所以为什么stack和queue要使用deque这个容器来实现,因为stack只用到了尾插尾删queue只用到了尾插和头删,正好都利用到了deque的优点,而deque的缺点没有涉及到,所以stack和queue的实现用到了deque这个容器。 

以下是使用deque来实现stack和queue。

namespace deque_stack
{template<class T, class Container = deque<T>>class stack{public:stack(){}//入栈void push(const T& val){_s.push_back(val);}//出栈void pop(){_s.pop_back();}//判断是否为空bool empty() const{return _s.empty();}//获取数据个数size_t size() const{return _s.size();}//取栈顶数据T& top(){return _s.back();}//const类型取栈顶数据const T& top() const{return _s.back();}private:Container _s;};void Test1(){stack<int> s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout << s1.top() << " ";s1.pop();}}
}
namespace deque_queue
{template<class T,class Container = deque<T>>class queue{public:queue(){}//入队列void push(const T& val){_l.push_back(val);}//出队列void pop(){_l.pop_front();}//取对头T& front(){return _l.front();}const T& front() const{return _l.front();}//取队尾T& back(){return _l.back();}const T& back() const{return _l.back();}//判断是否为空bool empty() const{return _l.empty();}//获取数据个数size_t size() const{return _l.size();}private:Container _l;};void Test1(){queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout << q1.front() << " ";q1.pop();}}
}

五.priority_queue的模拟实现

接下来,我们进入到priority_queue的模拟实现。

如果你查过queue的手册,会发现queue下面还有一个priority_queue的东西。

这个叫优先队列,简单的说也就是

对于堆的结构和各种操作,可以参考下面这篇博客

【C语言】堆的实现(建堆、堆的基本操作、堆排序、TOK问题)详解_堆 编程-CSDN博客icon-default.png?t=N7T8https://blog.csdn.net/EWIAW_ilove/article/details/135045451?spm=1001.2014.3001.5501

这篇博客详细的讲解了堆的实现,以及各种讲解,在这里,我们直接给出priority_queue的模拟实现并做简单的解释。

默认生成大堆

在实现之前,我们来看看priority_queue的成员函数。


默认情况下,我们生成的堆都是大堆,但是有时候也会用到小堆,大堆和小堆的区别就是,在代码中的比较反过来就行了,但是具体怎么实现呢?

这个时候要用到STL中的仿函数来实现。

在具体讲解建小堆前,我们先来看看大堆的实现。

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>
using namespace std;
namespace My_priority
{template<class T,class Container = vector<T>>class priority_queue{public:priority_queue(){}//从尾部插入数据void push(const T& val){_pq.push_back(val);//先在vector的尾部插入新数据//后进行一个向上调整AdjustUp();}void AdjustUp()//向上调整算法{int child = size() - 1;int parent = (child - 1) / 2;while (parent >= 0 && _pq[child] > _pq[parent]){swap(_pq[child], _pq[parent]);child = parent;parent = (child - 1) / 2;}}//删除堆顶数据void pop(){assert(size());swap(_pq[0], _pq[size() - 1]);//交换堆顶和尾部数据_pq.pop_back();//删除尾部数据//向下调整AdjustDown();}void AdjustDown()//向下调整算法{int parent = 0;int child = parent * 2 + 1;//默认child给左孩子while (child < size()){if ((child + 1) < size() && (_pq[child] < _pq[child + 1]))//如果右孩子存在并且大于左孩子,则child给右孩子{child += 1;}if (_pq[child] > _pq[parent]){swap(_pq[child], _pq[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//判断是否为空bool empty() const{return _pq.empty();}//求数据个数size_t size() const{return _pq.size();}//取堆顶数据const T& top() const{assert(size());return _pq[0];}private:Container _pq;};
}

仿函数 

在上面的实现中,默认情况下能生成只大堆,那么如果我们想要生成小堆,该怎么办呢?

在解释之前,我们先来看看仿函数这个东西。


仿函数如字面意思,是一个模仿的函数,即仿函数不是真正意义上的函数,其实它是一个由一个类通过重载()实现的。如下我实现了一个用于比较小于的仿函数。

 同样的,大于的比较我们也可以通过这种方式实现。

如下:        

 

 模拟实现大小堆

有了这两个仿函数,我们就可以通过模板的方式来控制生成的是大堆还是小堆了。 

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>using namespace std;namespace My_priority
{//用于比较小于的仿函数template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}	 };//用于比较大于的仿函数template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};//模板参数有三个:类型参数、堆底层的容器、仿函数,仿函数默认给lesstemplate<class T,class Container = vector<T>,class Compare = less<T>>class priority_queue{public:priority_queue(){}//从尾部插入数据void push(const T& val){_pq.push_back(val);//先在vector的尾部插入新数据//后进行一个向上调整AdjustUp();}void AdjustUp()//向上调整算法{Compare com;//创建仿函数对象int child = size() - 1;int parent = (child - 1) / 2;while (parent >= 0 && com(_pq[parent],_pq[child])){swap(_pq[child], _pq[parent]);child = parent;parent = (child - 1) / 2;}}//删除堆顶数据void pop(){assert(size());swap(_pq[0], _pq[size() - 1]);//交换堆顶和尾部数据_pq.pop_back();//删除尾部数据//向下调整AdjustDown();}void AdjustDown()//向下调整算法{Compare com;//创建仿函数对象int parent = 0;int child = parent * 2 + 1;//默认child给左孩子while (child < size()){if ((child + 1) < size() && com(_pq[child] , _pq[child + 1]))//如果右孩子存在并且大于左孩子,则child给右孩子{child += 1;}if (com(_pq[parent] , _pq[child])){swap(_pq[child], _pq[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//判断是否为空bool empty() const{return _pq.empty();}//求数据个数int size() const{return _pq.size();}//取堆顶数据const T& top() const{assert(size());return _pq[0];}private:Container _pq;};
}

 六.所以源代码

stack.h

#pragma once
#include<iostream>
#include<vector>
#include<deque>
using namespace std;namespace My_Stack
{//使用模板来给一个vector参数template<class T,class Container=vector<T>>class stack{public:stack(){}//入栈void push(const T& val){_s.push_back(val);}//出栈void pop(){_s.pop_back();}//判断是否为空bool empty() const{return _s.empty();}//获取数据个数size_t size() const{return _s.size();}//取栈顶数据T& top(){return _s.back();}//const类型取栈顶数据const T& top() const{return _s.back();}private:Container _s;};void Test1(){stack<int> s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout << s1.top() << " ";s1.pop();}cout << endl;}void Test2(){stack<int> s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);int a = s1.top();s1.pop();s1.push(10);cout << a << endl;}
}namespace deque_stack
{template<class T, class Container = deque<T>>class stack{public:stack(){}//入栈void push(const T& val){_s.push_back(val);}//出栈void pop(){_s.pop_back();}//判断是否为空bool empty() const{return _s.empty();}//获取数据个数size_t size() const{return _s.size();}//取栈顶数据T& top(){return _s.back();}//const类型取栈顶数据const T& top() const{return _s.back();}private:Container _s;};void Test1(){stack<int> s1;s1.push(1);s1.push(2);s1.push(3);s1.push(4);while (!s1.empty()){cout << s1.top() << " ";s1.pop();}cout << endl;}
}

queue.h

#pragma once
#include<iostream>
#include<list>
#include<deque>
using namespace std;namespace My_queue
{template<class T,class Container=list<T>>class queue{public:queue(){}//入队列void push(const T& val){_l.push_back(val);}//出队列void pop(){_l.pop_front();}//取对头T& front(){return _l.front();}const T& front() const{return _l.front();}//取队尾T& back(){return _l.back();}const T& back() const{return _l.back();}//判断是否为空bool empty() const{return _l.empty();}//获取数据个数size_t size() const{return _l.size();}private:Container _l;};void Test1(){queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);cout << q1.size() << endl;while (!q1.empty()){cout << q1.front() << " ";q1.pop();}cout << endl;}
}namespace deque_queue
{template<class T,class Container = deque<T>>class queue{public:queue(){}//入队列void push(const T& val){_l.push_back(val);}//出队列void pop(){_l.pop_front();}//取对头T& front(){return _l.front();}const T& front() const{return _l.front();}//取队尾T& back(){return _l.back();}const T& back() const{return _l.back();}//判断是否为空bool empty() const{return _l.empty();}//获取数据个数size_t size() const{return _l.size();}private:Container _l;};void Test1(){queue<int> q1;q1.push(1);q1.push(2);q1.push(3);q1.push(4);while (!q1.empty()){cout << q1.front() << " ";q1.pop();}cout << endl;}
}

priority.h

#pragma once
#include<iostream>
#include<vector>
#include<assert.h>using namespace std;namespace My_priority
{//用于比较小于的仿函数template<class T>struct less{bool operator()(const T& x, const T& y){return x < y;}	 };//用于比较大于的仿函数template<class T>struct greater{bool operator()(const T& x, const T& y){return x > y;}};//模板参数有三个:类型参数、堆底层的容器、仿函数template<class T,class Container = vector<T>,class Compare = less<T>>class priority_queue{public:priority_queue(){}//从尾部插入数据void push(const T& val){_pq.push_back(val);//先在vector的尾部插入新数据//后进行一个向上调整AdjustUp();}void AdjustUp()//向上调整算法{Compare com;int child = size() - 1;int parent = (child - 1) / 2;while (parent >= 0 && com(_pq[parent],_pq[child])){swap(_pq[child], _pq[parent]);child = parent;parent = (child - 1) / 2;}}//删除堆顶数据void pop(){assert(size());swap(_pq[0], _pq[size() - 1]);//交换堆顶和尾部数据_pq.pop_back();//删除尾部数据//向下调整AdjustDown();}void AdjustDown()//向下调整算法{Compare com;int parent = 0;int child = parent * 2 + 1;//默认child给左孩子while (child < size()){if ((child + 1) < size() && com(_pq[child] , _pq[child + 1]))//如果右孩子存在并且大于左孩子,则child给右孩子{child += 1;}if (com(_pq[parent] , _pq[child])){swap(_pq[child], _pq[parent]);parent = child;child = parent * 2 + 1;}else{break;}}}//判断是否为空bool empty() const{return _pq.empty();}//求数据个数int size() const{return _pq.size();}//取堆顶数据const T& top() const{assert(size());return _pq[0];}private:Container _pq;};void Test1(){//priority_queue<int> pq;priority_queue<int,vector<int>,greater<int>> pq;pq.push(15);pq.push(10);pq.push(8);pq.push(20);while (!pq.empty()){cout << pq.top() << " ";pq.pop();}cout << endl;}
}

test.cpp

#include"stack.h"
#include"queue.h"
#include"priority.h"
int main()
{My_Stack::Test1();My_Stack::Test2();My_queue::Test1();deque_stack::Test1();deque_queue::Test1();My_priority::Test1();return 0;
}

 

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/320264.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

机器学习——3.梯度计算与梯度下降

基本概念 梯度的本意是一个向量&#xff08;矢量&#xff09;&#xff0c;表示某一函数在该点处的方向导数沿着该方向取得最大值&#xff0c;即函数在该点处沿着该方向&#xff08;此梯度的方向&#xff09;变化最快&#xff0c;变化率最大&#xff08;为该梯度的模&#xff0…

validation的简单使用

首先是依赖 我这里使用的是 web 工程&#xff0c;所以多一个web依赖 <dependency><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-validation</artifactId></dependency><dependency><groupId>…

10 华三vlan技术介绍

AI 解析 -Kimi-ai Kimi.ai - 帮你看更大的世界 (moonshot.cn) 虚拟局域网&#xff08;VLAN&#xff09;技术是一种在物理网络基础上创建多个逻辑网络的技术。它允许网络管理员将一个物理网络分割成多个虚拟的局域网&#xff0c;这些局域网在逻辑上是隔离的&#xff0c;但实际…

leetCode68. 文本左右对齐

基本思路&#xff1a; leetCode68. 文本左右对齐 代码 class Solution { public:vector<string> fullJustify(vector<string>& words, int maxWidth) {vector<string> res;for(int i 0; i < words.size(); i){ // 枚举有多少个单词int j i 1; //…

年轻人刮疯了,刮刮乐断货了

年轻人刮疯了 刮刮乐缺货了。 00后彩票店老板陆诗等得有点着急。她的福彩店开在深圳&#xff0c;今年4月才开门营业&#xff0c;但从开业到今天&#xff0c;刮刮乐总共就来了一回货——开业时发的20本。 那之后&#xff0c;刮刮乐就彻底断供了。原本&#xff0c;陆诗想把刮刮…

《MySQL数据类型》

文章目录 一、理解数据本身就是一种约束1.tinyint类型和 tinyint unsigned类型2.其他的int类型 二、bit类型三、float类型1.signed版本注意2.unsigned版本 四、decimal类型float 和 decimal 总结五、char类型&#xff08;固定长度&#xff09;六、varchar类型&#xff08;可变长…

【跟马少平老师学AI】-【神经网络是怎么实现的】(四)卷积神经网络

一句话归纳&#xff1a; 1&#xff09;用1个小粒度的模式&#xff0c;逐个与图像的局部区域进行运算&#xff0c;运算结果反映模式与区域的匹配程度。 2&#xff09;卷积神经网络与全连接神经网络的区别&#xff1a; 卷积神经网络的输出只与局部输入有连接。参数较少&#xff0…

N9048B PXE EMI 测试接收机,1 Hz 至 44 GHz

​ _EMI_ N9048B EMI 测试接收机 1 Hz 至 44 GHz Keysight N9048B PXE 是一款符合标准的 EMI 测试接收机&#xff0c;配有射频预选器和 LNA 设计。其实时扫描&#xff08;RTS&#xff09;功能有助于您缩短总体测试时间&#xff0c;轻松执行无间隙的信号捕获和分析。 特点 …

宏电全栈式IoT赋能供排水智能监测,护航城市生命线

城市供水、排水系统是维系城市正常运行、满足群众生产生活需要的重要基础设施&#xff0c;是城市的“生命线”。随着城市化进程加快&#xff0c;城市规模不断扩大&#xff0c;地下管线增长迅速&#xff0c;城市“生命线安全”的监管日益面临挑战。 宏电作为物联网行业的领航者…

Docker本地部署overleaf后,挖掘用户加密逻辑

overleaf的用户信息&#xff0c;保存在mongo数据库的users集合中。 用户密码则存在hashedPassword字段中 从开源的代码services\web\app\src\Features\Authentication\AuthenticationManager.js第303行可以找到密码加密逻辑。 本地可以通过下面的代码生成overleaf用户密码信息…

408数据结构-树与森林 自学知识点整理

前置知识&#xff1a;树的基本概念与性质 树的存储结构 树既可以采用顺序存储结构&#xff0c;又可采用链式存储结构。但无论采取哪种方式&#xff0c;都要求能够唯一地反映树中各结点之间的逻辑关系。 1. 双亲表示法 这种存储结构采用一组连续空间来存储每个结点&#xff0…

JetPack之ViewModel+LiveData

目录 一、概述二、LiveData 使用2.1 创建 LiveData 对象2.2 观察 LiveData 对象2.3 更新 LiveData 对象 三、编写 LiveData Demo3.1 不使用 LiveData3.2 使用 MutableLiveData3.3 使用 MediatorLiveData3.3.1 监听 2 个数据源的变化3.3.2 编写模拟 2 个数据源更新的代码 四、Vi…

java中如何判断一个数是不是素数(质数)

相关概念 质数就是大于1的自然数字中&#xff0c;只能被1和它自己整除的数。 题目 求101~200之间的质素的个数 代码实现 判断一个数是不是质数 for (int j 2; j < i; j) {if(i % j 0){flag false;break;}}if(flag){System.out.println("当前数字是质数");…

Unity 性能优化之遮挡剔除(Occlusion Culling)(六)

提示&#xff1a;仅供参考&#xff0c;有误之处&#xff0c;麻烦大佬指出&#xff0c;不胜感激&#xff01; 文章目录 前言一、遮挡剔除是什么&#xff1f;二、静态遮挡剔除的使用步骤1.标记为遮挡剔除对象2.创建Occlusion Area组件3.烘焙4.Occlusion窗口Bake的参数Smallest Oc…

电子书制作神器,简单操作

​随着数字化时代的到来&#xff0c;电子书籍越来越受到人们的喜爱。而一款优秀的电子翻页书制作软件&#xff0c;则能够帮助你轻松制作出专业级的电子书&#xff0c;让你的阅读体验更加丰富多彩。 今天&#xff0c;我们就来为大家推荐一款优秀的电子翻页书制作软件——FLBOOK在…

全球260多个国家的年通货膨胀率数据集(1960-2021年)

01、数据简介 全球年通货膨胀率是指全球范围内&#xff0c;在一年时间内&#xff0c;物价普遍上涨的比率。这种上涨可能是由于货币过度供应、需求过热、成本上升等原因导致的。通货膨胀率是衡量一个国家或地区经济状况和物价水平的重要指标&#xff0c;通常以消费者价格指数&a…

Flutter笔记:Widgets Easier组件库(12)使用消息吐丝(Notify Toasts)

Flutter笔记 Widgets Easier组件库&#xff08;12&#xff09;使用消息吐丝&#xff08;Notify Toasts&#xff09; - 文章信息 - Author: 李俊才 (jcLee95) Visit me at CSDN: https://jclee95.blog.csdn.netMy WebSite&#xff1a;http://thispage.tech/Email: 29114848416…

如何全面规避医疗数据安全风险?“一中心三大管控域”打开新思路!

作为医院的核心基础设施&#xff0c;数据库已然演变成了一种具有“资产”属性的重要元素。而随着不断变化的医疗业务场景和日趋严格的合规性要求&#xff0c;如何让安全全方位贯穿医疗数据的生命周期&#xff0c;是一项系统性的建设工作&#xff0c;难点诸多。 基于多年的数据…

Vue前端环境准备

vue-cli Vue-cli是Vue官方提供的脚手架&#xff0c;用于快速生成一个Vue项目模板 提供功能&#xff1a; 统一的目录结构 本地调试 热部署 单元测试 集成打包上线 依赖环境&#xff1a;NodeJs 安装NodeJs与Vue-Cli 1、安装nodejs&#xff08;已经安装就不用了&#xff09; node-…

Linux字符设备驱动(二) - 与设备驱动模型的关系

一&#xff0c;从/dev目录说起 从事Linux嵌入式驱动开发的人&#xff0c;都很熟悉下面的一些基础知识&#xff0c; 比如&#xff0c;对于一个char类型的设备&#xff0c;我想对其进行read wirte 和ioctl操作&#xff0c;那么&#xff1a; 1&#xff09;我们通常会在内核驱动中…