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

devtools/2024/10/11 13:30:46/

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

一.什么是适配器

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

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

为什么呢？

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

通过查看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是一个顺序的存储结构，和vector和list一样，都是顺着顺序来存储数据的，那么它们有什么区别吗，又或者说，为什么会出现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.ppmy.cn/devtools/35010.html

相关文章

从0开始的数据结构的书写-------线性表（顺序表）

从0开始的数据结构的书写-------线性表（顺序表）

&#xff08;复习考研的休息区&#xff0c;心血来潮&#xff0c;写点代码&#xff09; 三个规则&#xff1a; 1、不使用c stl库进行书写 2、最好基于严蔚敏老师的数据结构 3、最好使用malloc和realloc动态分配内存 &#xff08;如果有问题&#xff0c;请大家看看&#xff…
阅读更多...
【项目部署】手把手带你从零部署项目：宝塔 + uwsgi + Django + 腾讯云 + Websocket

【项目部署】手把手带你从零部署项目：宝塔 + uwsgi + Django + 腾讯云 + Websocket

1. 前言 哈喽&#xff0c;大家好&#xff0c;我是jiaoxingk。今天带来的是有关Django项目部署的教程。 当我们完成了一个项目作品之后&#xff0c;我们肯定会迫不及待的就准备上线部署啦&#xff0c; 这篇教程将带你从服务器的配置选购&#xff0c;再通过安装宝塔的形式进行项目…
阅读更多...
springboot+websocket开发简单的在线群聊聊天web版本

springboot+websocket开发简单的在线群聊聊天web版本

springbootwebsocket开发简单的在线群聊聊天web版本&#xff01;近期在测试websocket插件的群聊功能。下面是一个简单的demo。分享给大家&#xff0c;亲测可以使用的。 1&#xff1a;首先是一个chat.html页面。代码如下&#xff1a; <!DOCTYPE html> <html lang"…
阅读更多...
RK3568 学习笔记 : 精简 u-boot env 默认复杂的多种引导启动设置

RK3568 学习笔记 : 精简 u-boot env 默认复杂的多种引导启动设置

前言 环境&#xff1a; 正点原子 Atompi-CA1 RK3568 开发板、正点原子 DLRK3568 开发板&#xff0c;&#xff08;一时脑热买了两块 RK3568 开发板&#xff09;&#xff0c;Atompi-CA1 RK3568 开发板比较小巧&#xff0c;利于一些前期的嵌入式 Linux 开发学习与实践。 RK3568 开…
阅读更多...
【考研数学】武忠祥「基础篇」如何衔接进入强化?

【考研数学】武忠祥「基础篇」如何衔接进入强化?

如果基础篇已经做完&#xff0c;并且讲义上的例题也都做完了&#xff0c; 那下一步就是该做题了 这个时候&#xff0c;不能盲目做题&#xff0c;做什么题很重要&#xff01;我当初考研之前&#xff0c;基础也很差&#xff0c;所以考研的时候选了错误的题集&#xff0c;做起来就…
阅读更多...
Java毕设之学院党员管理系统的设计与实现

Java毕设之学院党员管理系统的设计与实现

运行环境 环境说明: 开发语言:java 框架:springboot&#xff0c;vue JDK版本:JDK1.8 数据库:mysql5.7(推荐5.7&#xff0c;8.0也可以) 数据库工具:Navicat11 开发软件:idea/eclipse(推荐idea) Maven包:Maven3.3.9 系统实现 管理员功能实现 党员管理 管理员进入指定功能操作…
阅读更多...
vtk教程：禁止VTK弹出警告窗口warning

vtk教程：禁止VTK弹出警告窗口warning

在使用VTK&#xff08;Visualization Toolkit&#xff09;进行可视化操作时&#xff0c;有时候会弹出警告窗口&#xff08;warning messages&#xff09;&#xff0c;这些警告可能是由于数据问题或是API使用不当等原因触发的。 如果你希望在使用VTK时禁用这些警告窗口&#xff…
阅读更多...
【Unity 组件思想-预制体】

【Unity 组件思想-预制体】

【Unity 组件思想-预制体】 预制体&#xff08;Prefab&#xff09;是Unity中一种特殊的组件 特点和用途&#xff1a; 重用性&#xff1a; 预制体允许开发者创建可重复使用的自定义游戏对象。这意味着你可以创建一个预制体&#xff0c;然后在场景中多次实例化它&#xff0c;…
阅读更多...
最新文章

Copyright @ 2022~2023