stack、queue(priority_queue)的模拟实现和deque的简单介绍

stack和queue(priority_queue)

1. 容器适配器

适配器(Adapter)：一种用来修饰容器(Containers)或仿函数(Functors)或迭代器(Iterator)接口的东西。

适配器是一种设计模式，该模式将一个类的接口转换成客户希望的另外一个接口。

现实中拿插座来说，一个插座可以适配不同的插头，以适应不同电器的电压或者其他要求。

在这里插入图片描述

STL中的适配器相当于一个插座，以适应不同容器，可以"插入"vector, 也可以插入 list，等等。

虽然stack和queue也可以存放元素，但在STL中并没有将其划分在容器的行列，而是将其称为容器适配器。

例如stack只提供LIFO（先进先出）的概念，对其他容器的接口进行了包装，并没有完全重新创建了一个容器。在STL中，stack和queue默认使用deque，而priority_queue默认使用vector。

在这里插入图片描述

类似于list中iterator的实现，实际上是更高一层的封装。__list_iterator是对Node*的封装，以支持运算符重载；相对应的，stack是对其Container的封装，以支持LIFO的上下文。

2. stack 的介绍和实现

2.1 stack 的介绍

stack文档介绍

  1. stack 是一种容器适配器，设计用于在具有后进先出操作的上下文中，其删除和插入只能从容器的末尾进行操作。

  2. stack是作为容器适配器被实现的，容器适配器即是对特定类封装作为其底层的容器，并提供一组特定的成员函数来访问其元素，元素特定从容器的尾部（即栈顶）被压入和弹出。

  3. stack的底层容器可以是任何标准的容器类模板或者一些特殊设计的容器类。这些容器应该支持如下操作：

    empty()			// 判空操作
size()  		// 得到元素个数操作
back()  		// 得到容器尾部元素操作
push_back()		// 尾插操作
pop_back()		// 尾删操作

  4. 标准容器list,vector和deque均满足这些要求。默认情况下，如果没有为stack指定特定的底层容器，默认使用deque作为底层容器。

在这里插入图片描述

2.2 stack 的实现

stack 有如下成员函数（不包括C++11)

在这里插入图片描述

利用适配器概念进行实现：

#pragma once
#include <deque>namespace wr
{template <class T, class Con = deque<T>>	class stack{public:void push(const T &x){_con.push_back(x);}void pop(){_con.pop_back();}T &top(){return _con.back();}T &top() const{return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}private:Con _con;	// 底层的容器类对象作为成员变量};
}

可以看到，适配器模式下设计的stack十分简洁，相比用C语言实现的stack,完全体现了适配器模式的优势。

总结：从使用者角度来看，不需要知道stack底层使用的是什么容器实现，只需要知道其可以实现对应适合LIFO的操作。无论是STL中的容器，还是自定义类容器，只要拥有对应的接口，就可以作为stack的底层容器。

2. queue的介绍和实现

2.1 queue 的介绍

queue文档介绍

  1. queue 是一种容器适配器，专门用于在FIFO（先进先出）的上下文中操作，其中从容器一端插入元素，另一端提取元素。

  2. queue作为容器适配器实现，用一个底层是特定容器类的封装类来实现，queue提供了特定了成员函数来访问它的元素。元素队尾入队列，从队头出队列。

  3. queue的底层容器可以是标准容器中的一种，或者是经过特别设计的容器类。底层容器应该至少指出如下操作：

    empty()				// 判空操作
size()				// 得到元素个数操作
front()				// 得到容器头部元素
back()				// 得到容器尾部元素
push_back()			// 容器尾插元素操作
pop_back()			// 容器头删元素操作

  4. STL中deque和list可以满足这些需求。默认情况下，如果没有容器类被指定，默认使用deque作为queue的底层容器。

在这里插入图片描述

2.2 queue 的实现

queue有如下成员函数：

在这里插入图片描述

实现如下：

#pragma once#include <deque>namespace wr
{template <class T, class Con = deque<T>>class queue{public:void push(const T &x){_con.push_back(x);}void pop(){_con.pop_front();}T &back(){return _con.back();}const T &back() const{return _con.back();}T &front(){return _con.front();}const T &front() const{return _con.front();}size_t size() const{return _con.size();}bool empty() const{return _con.empty();}private:Con _con;};	
}

和stack的实现差不多，唯一需要注意的是 ：queue的底层容器不能是vector，因为vector类根本不支持pop_front()的操作。并且vector的头删效率太低，需要挪动后面的所有元素。

3. priority_queue 的介绍和使用

3.1 priority_queue 的介绍

priority_queue文档介绍

  1. priority_queue（优先队列）是一种容器适配器，根据严格的弱排序标准，它的第一个元素总是它所包含元素最大的。

  2. 此上下文类似于heap（堆），在这种上下文中，元素可以随时被插入到堆中，并且只有最大的堆元素可以被访问（位于优先队列的top()）。

  3. priority_queue被作为容器适配器实现，并将特定容器类封装作为其底层容器类，同时提供了特定的一组成员函数来访问其元素。元素从特定容器的“尾部”弹出，其成为优先队列的顶部。

  4. 底层容器可以是任何标准容器类模板，也可以是其他特定设计的容器类。容器应该可以通过随机访问迭代器访问，并支持以下操作：

    empty()				// 判空操作
size()				// 得到元素个数操作
front()				// 得到容器头部元素
push_back()			// 容器尾插元素操作
pop_back()			// 容器头删元素操作

  5. STL中vector和deque满足这些需求。默认情况下，如果没有为特定的priority_queue类实例化指定容器类，则使用vector。

  6. 需要支持随机访问迭代器，一边始终在内部保持堆结构。容器适配器通过在需要时自动调用算法函数make_heap、push_heap和pop_heap来自动完成此操作。

优先级队列默认使用vector作为其底层的容器，在vector上又使用了堆算法将vector中元素构造成堆的结构，因此priority_queue就是堆，所有需要用到堆的位置，都可以考虑使用priority_queue。

需要注意的是，下面是优先级队列的模板参数，第三个参数默认使用less仿函数，以构造大堆。若指定Compare是greater仿函数，则构成小堆。

在这里插入图片描述

// 默认情况下构造小堆
priority_queue<int> pq1；		
// 相当于
priority_queue<int, vector<int>, less<int>> pq1;// 指定底层容器构造大堆
priority_queue<int, deque<int>, greater<int>> pq2;

如果需要使用priority_queue存放自定义类元素，需要自行重载>和<。

3.2 priority_queue 的实现

之前已经用C语言实现过堆，C++实现的重点是对STL的使用、仿函数的使用以及适配器模式概念的理解。

数据结构:堆的实现和堆排序及TopK问题

堆的插入元素和删除元素的时间复杂度是O(logN) ，默认情况下优先级队列是大堆，先不考虑使用仿函数去实现大小堆兼容的问题。首先先来实现大堆，最后在代码基础上加上仿函数的设计就可以了。

priority_queue与queue的区别主要是在push和pop上，优先级队列需要进行额外的向上调整和向下调整以满足堆序。

push：先将元素尾插到容器，随后将该元素进行向上调整以满足堆序。

pop：直接将容器最后一个元素覆盖堆顶元素，随后对此时的堆顶元素进行向下调整以满足堆序。注意：不能直接将堆顶元素删除，因为不能保证左孩子和右孩子之间也满足堆序，两个孩子之间没有关系，它们只和他们的父亲有关系。

void push(const T &x)
{_con.push_back(x);adjust_up(_con.size() - 1);
}void pop()
{assert(!_con.empty());_con[0] = _con[_con.size() - 1];_con.pop_back();adjust_down(0);
}

随后就是向上调整和向下调整算法，这里先直接用不等号直接实现大堆。

// 向上调整算法
void adjust_up(int child)
{int parent = (child - 1) / 2;while (parent >= 0){// 默认less，大堆，a[child] > a[parent] 交换if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}
}// 向下调整算法
void adjust_down(int parent)
{int child = parent * 2 + 1;while (child < _con.size()){// 默认less, 如果_con[child+1] > _con[child], 更新childif (child + 1 < _con.size() && _con[child] < _con[child+1]){child++;}// 如果_con[parent] < _con[child] 交换if (_con[parent] < _con[child]){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}
}

具体实现细节在以前博客，这里不过多赘述。

随后是其他一些简单接口。注意：top()的参数和返回值都是const,保证数据不被修改。

bool empty() const
{return _con.empty();
}size_t size() const
{return _con.size();
}const T &top() const
{return _con.front();
}

这是固定死了的大堆，如果要使用小堆，难道需要再写一个类或者在需要时再修改吗？答案显然是否定的。

在C语言阶段，可以用函数指针进行实现，通过对comp()函数的回调实现特定的需求。例如实现bubble_sort()函数时通过传入函数指针来指定比较方法。

//通用冒泡排序
void bubble_sort(void* base, size_t num, size_t size, int (*cmp)(const char*, const char*))

C++中有更好的实现方法，称为仿函数。

3.2.1 仿函数

仿函数就是仿造的函数，它并不是一个真正意义上的函数。它是一个类中的operator()重载，使之它具有类似于函数的功能。

就如仿羊皮一样，仿函数不是函数，而是一个类中的operator()重载，既然在类中，那么就可以使用模板参数，这相比函数指针就更加的范式化。

下面是greater和less的模拟实现

template <class T>
struct greater
{// 运算符()重载bool operator()(const T &a, const T &b){return a > b;}
};template <class T>
struct less
{bool operator()(const T &a, const T &b){return a < b;}
};

使用仿函数就可以构建一个对应的类对象，随后调用operator()即可

less<int> le;
cout << le(100, 200) << endl;

将仿函数类模板放入priority_queue的模板参数列表中，就可以实现在构建优先级队列的时候指定堆序了。因为模板参数传入的是类型，在编译的时候进行传递，随后程序运行都是基于传入模板的参数类型下进行运行的。

下面是引入了仿函数的完整priority_queue完整实现：

template <class T>
class greater
{
public:bool operator()(const T &a, const T &b){return a > b;}
};template <class T>
class less
{
public:bool operator()(const T &a, const T &b){return a < b;}
};template <class T, class Con = vector<T>, class Compare = less<T>>
class priority_queue
{void adjust_up(int child){int parent = (child - 1) / 2;while (parent >= 0){// 默认less，大堆，a[child] > a[parent] 交换if (_comp(_con[parent], _con[child])){swap(_con[parent], _con[child]);child = parent;parent = (child - 1) / 2;}else{break;}}}void adjust_down(int parent){int child = parent * 2 + 1;while (child < _con.size()){// 默认less, 如果_con[child+1] > _con[child], 更新childif (child + 1 < _con.size() && _comp(_con[child], _con[child + 1])){child++;}if (_comp(_con[parent], _con[child])){swap(_con[parent], _con[child]);parent = child;child = parent * 2 + 1;}else{break;}}}public:template <class InputIterator>priority_queue(InputIterator first, InputIterator last){while (first < last){push(*first);first++;}}bool empty() const{return _con.empty();}size_t size() const{return _con.size();}const T &top() const{return _con.front();}void push(const T &x){_con.push_back(x);adjust_up(_con.size() - 1);}void pop(){_con[0] = _con[_con.size() - 1];_con.pop_back();adjust_down(0);}private:Con _con;Compare _comp;
};

4. deque 的简单介绍

deque 的文档介绍

deque双端队列：是一种双开口的“连续”空间的数据结构，双开口的含义是：可以在头尾进行插入和删除操作，且时间复杂度是O(1)，与vector比较，头插效率高，不需要搬移元素；与list比较，空间利用率比较高。

在这里插入图片描述

4.1 deque 的实现原理

deque并不是真正连续的空间，而是由一段段连续的小空间拼接而成的。

实际的deque类似于一个动态的二维数组，如下图所示：

在这里插入图片描述

所有的小空间使用一个指针数组map进行管理的，相当于一个中控。

第一块空间的首地址存放在map的中间，第二块空间的首地址在map下一个位置，若需要头插元素，则新创建的空间首地址放在map中第一块空间首地址的前面。

双端队列底层是一段假象的连续空间，实际上是分段连续的，为了维护其“整体连续”以及随机访问的假象，这个任务落在了deque的迭代器身上，因此deque的迭代器设计就比较复杂，如下图所示：

在这里插入图片描述

queue的iterator封装了四个指针，分别是cur、first、last、node;

first:当前元素所处缓冲区的开始

last:当前元素所处缓冲区的结束

cur:当前元素值

node:指针的指针，指向map中指向buffer的指针

deque通过迭代器start和finish维护其整体结构：

在这里插入图片描述

deque::begin()返回迭代器start，deque::end()返回迭代器finish,这两个迭代器都是deque的成员变量。

如果要头插元素，而此时迭代器start中node指向为第一个buffer的首地址，则需要创建一个新的buffer空间。node指向map前一个空间，*node指向新buffer的首元素地址，同时更新first、cur、last。

4.2 deque 与 vector和 list 的比较

deque的优势就是头插头删，尾插尾删，只有O(1)的时间复杂度。

但由于其复杂的底层结构，导致实现其随机访问（即[]）很困难，有以下两点不足，或者说是冲突：

  • 若规定deque的每一个buffer的空间一样大（为n），那么访问第i个数据的思路：如果i不是第一个buffer中的数据，则i -= 第一个buffer的长度后，第i个数据的下标为[i/n, i%10]。若规定deque的每一个buffer不一样大，则需要依次将i减去buffer的长度，直至i小于下一个buffer的长度，才能找到第i个元素对应的位置
  • 在deque中间插入数据，若需要每个buffer的空间一样大，需要挪动所有该位置前面或者后面的数据。若不需要每个buffer空间一样大，则可以只挪动当前buffer的元素。

由此可以看到，对deque的buffer的长度是否一致的规定会影响随机访问和中间插入元素的效率。但无论怎么说，deque的随机访问是始终不如vector的，中间插入元素是始终不如list的。

容器优点缺点
vector物理结构连续存储 1.下标随机访问 2.缓存命中率高1.前面部分插入删除效率低 2.扩容有损耗，还会存在一定程度空间浪费
list物理结构不一定连续 1. 任意位置插入删除效率高 2. 按需申请空间，1.不支持下标随机访问 2.缓存命中率高
deque1.支持下标随机访问 2. 扩容损耗小 3. 头部和尾部对元素处理效率高 4. 缓存命中率高1.中间插入效率低 2.下标随机访问不如vector

本章完。

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

如若内容造成侵权/违法违规/事实不符，请联系瞎胡闹网进行投诉反馈，一经查实，立即删除！

相关文章

Ubuntu 安装 Harbor

Ubuntu 安装 Harbor

一、安装 docker 原文参考传送门 1st 卸载系统自带的 docker 应用 for pkg in docker.io docker-doc docker-compose docker-compose-v2 podman-docker containerd runc; do sudo apt-get remove $pkg; done 2nd 设置Docker 的apt源 # Add Dockers official GPG key: sudo…
阅读更多...
MySQL的root用户无法远程连接

MySQL的root用户无法远程连接

默认root用户只允许本地连接&#xff0c;所以需要修改mysql库中user表中名为root的用户的host为“%” select Host,User from user;UPDATE mysql.user SET host % WHERE user root; FLUSH PRIVILEGES;
阅读更多...
什么是最优物理隔离文件导出导入解决方案，来看看吧

什么是最优物理隔离文件导出导入解决方案，来看看吧

企业进行物理隔离的主要原因是为了提高安全性&#xff0c;减少安全风险。物理隔离通常指的是将网络或系统中的关键部分与外界断开直接连接&#xff0c;以增强安全性。在企业环境中&#xff0c;这通常意味着将内部网络&#xff08;内网&#xff09;与外部网络&#xff08;如互联…
阅读更多...
低视力者出行升级：适配服务助力双手解放与环境感知

低视力者出行升级：适配服务助力双手解放与环境感知

作为一名资深记者&#xff0c;我有幸深入了解并记录低视力者在日常出行中所面临的挑战与解决方案。近年来&#xff0c;低视力者辅助设备适配服务提供领域的创新成果&#xff0c;尤其是结合手机应用的辅助设备&#xff0c;正在以人性化、智能化的方式&#xff0c;帮助低视力者实…
阅读更多...
网安学习笔记-day13，文件共享暴力破解

网安学习笔记-day13，文件共享暴力破解

文件共享漏洞 准备阶段 配置IP地址 Windows XP 10.1.1.2/24 Windows Server 2003 10.1.1.1/24 开启文件共享 文件共享使用的是445端口&#xff0c;输入命令net share 在XP上打开运行窗口&#xff08;CtrlR&#xff09;输入\\10.1.1.1&#xff0c;出现以下界面则成功开启共享…
阅读更多...
1142 - SELECT command denied to user ···

1142 - SELECT command denied to user ···

MySql子账户操作数据库权限不够&#xff0c;提示错误 1142 - SELECT command denied to user database 1142 - ALTER command denied to user database 以下命令可以解决 GRANT SELEC your_database_name TO mysql_account%;
阅读更多...
块存储、文件存储、对象存储概念与区别

块存储、文件存储、对象存储概念与区别

1. 块存储 块存储是将数据切分成固定大小的块&#xff0c;然后将这些块存储在物理设备&#xff08;如硬盘、固态硬盘&#xff09;上。每个块都有唯一的标识符&#xff0c;并且可以独立地被读取、写入或删除。块存储通常用于存储文件系统&#xff0c;例如操作系统的文件系统&am…
阅读更多...
【python】Python成语接龙游戏[1-3难度均有]（源码+数据）【独一无二】

【python】Python成语接龙游戏[1-3难度均有]（源码+数据）【独一无二】

&#x1f449;博__主&#x1f448;&#xff1a;米码收割机 &#x1f449;技__能&#x1f448;&#xff1a;C/Python语言 &#x1f449;公众号&#x1f448;&#xff1a;测试开发自动化【获取源码商业合作】 &#x1f449;荣__誉&#x1f448;&#xff1a;阿里云博客专家博主、5…
阅读更多...
Node.js -- HTTP协议和网络基础概念

Node.js -- HTTP协议和网络基础概念

文章目录 1. 初识HTTP协议2. 窥探HTTP协议2.1 请求报文结构2.2 响应报文 3. 网络基础概念3.1 IP3.2 端口 本节相关内容都可以在 添加链接描述进行查看&#xff0c;深入了解相关内容。 1. 初识HTTP协议 HTTP协议其实就是浏览器和服务器之间的一个协议&#xff0c;浏览器会向服务…
阅读更多...
k8s学习(三十六)centos下离线部署kubernetes1.30(单主节点)

k8s学习(三十六)centos下离线部署kubernetes1.30(单主节点)

文章目录 服务器准备工作一、升级操作系统内核1 查看操作系统和内核版本2 下载内核离线升级包3 升级内核4 确认内核版本 二、修改主机名/hosts文件1 修改主机名2 修改hosts文件 三、关闭防火墙四、关闭SELINUX配置五、时间同步1 下载NTP2 卸载3 安装4 配置4.1 主节点配置4.2 从…
阅读更多...
MyBatis-Plus分页查询IPage的使用方法，如何自定义分页查询功能？

MyBatis-Plus分页查询IPage的使用方法，如何自定义分页查询功能？

目录 1. MyBatis-Plus 分页插件介绍 2. 准备工作-创建项目配置环境 2.1 创建数据库表Product商品表 2.2 创建Maven项目&#xff0c;创建包&#xff0c;接口&#xff0c;类 2.3 添加MyBatisPlus依赖和 Lombok 插件 2.4 编写 Configuration 分页插件配置文件 2.5 编写 app…
阅读更多...
AJAX——事件循环（EventLoop）

AJAX——事件循环（EventLoop）

1.事件循环&#xff08;EventLoop&#xff09; 概念&#xff1a;JavaScript有一个基于事件循环的并发模型&#xff0c;事件循环负责执行代码、收集和处理事件以及执行队列中的子任务。这个模型与其它语言中的模型截然不同&#xff0c;比如C和Java。 原因&#xff1a;JavaScri…
阅读更多...
使用 FFMPEG 实现录屏和录音

使用 FFMPEG 实现录屏和录音

FFmpeg 是一个非常强大的开源工具&#xff0c;它可以用来处理音频和视频。 要使用 FFmpeg 进行录屏和录音&#xff0c;需要首先确保你的系统已经安装了 FFmpeg。在大多数 Linux 发行版中&#xff0c;可以通过包管理器&#xff08;如 apt 或 yum&#xff09;来安装。在 Windows …
阅读更多...
【Flask】Flask中HTTP请求与接收

【Flask】Flask中HTTP请求与接收

一、接收http请求与返回响应 在Flask中&#xff0c;可以通过app.route装饰器来定义路由函数。 app.route(/BringGoods,methods [POST, GET]) GET请求&#xff1a;使用request.args.get(key)或者request.values.get(key)来获取URL中的参数。 POST请求&#xff1a; 使用req…
阅读更多...
nginx配置挂载html

nginx配置挂载html

目标 很多软件的官方文档&#xff0c;在国内打开很慢&#xff0c;每次都得等很久&#xff0c;看到官方同时提供了html的包&#xff0c;所以想着挂载到本地nginx下&#xff0c;查看会方便很多。 下载官方html文档包&#xff0c;解压到documentation_htmls下 想添加新的文档也是…
阅读更多...
【调制】π/4-DQPSK信号模型及其相关特性分析 【附MATLAB代码】

【调制】π/4-DQPSK信号模型及其相关特性分析 【附MATLAB代码】

MATLAB代码 % pi/4-DQPSK modulation %输入一串数&#xff0c;输出经过差分并映射的I、Q两路数据 ​ function [I,Q]pi4_dqpskmod(data) ​ nlength(data)./2; data1data.*2-1; ​ Idatazeros(1,n); Qdatazeros(1,n); ​ ​ Idatadata1(1,1:2:2*n); %串并变换 Qdatadata1(…
阅读更多...
yolo8目标检测+多目标跟踪算法实现车流量统计

yolo8目标检测+多目标跟踪算法实现车流量统计

目前常用的车流量统计方法包括基于虚拟区域和基于车辆跟踪的车流量统计方法&#xff0c;如下图所示。前者在视频帧中手动设定虚拟检测区域&#xff0c;通过判断虚拟检测区域的灰度值变化判断车辆是否经过&#xff0c;从而进行车流量统计。其中虚拟检测区域可以由点、线以及线圈…
阅读更多...
如何理解自然语言处理中的位置编码（Positional Encoding）

如何理解自然语言处理中的位置编码（Positional Encoding）

在自然语言处理和特别是在使用Transformer模型中，位置编码（Positional Encoding）是一个关键的概念。它们的作用是为模型提供序列中各个元素的位置信息。由于Transformer架构本身并不像循环神经网络（RNN）那样具有处理序列的固有能力，位置编码因此显得尤为重要。 为什么需…
阅读更多...
防爆轮式巡检机器人作用和优势？

防爆轮式巡检机器人作用和优势？

在当今的工业领域&#xff0c;安全生产始终是至关重要的议题。而在一些具有爆炸风险的环境中&#xff0c;如石油、化工、燃气等行业&#xff0c;传统的人工巡检方式面临着诸多挑战。然而&#xff0c;随着科技的飞速发展&#xff0c;防爆轮式巡检机器人应运而生&#xff0c;为这…
阅读更多...
(顶刊复现)基于配电网韧性提升的应急移动电源预配置和动态调度(上)—MPS预配置

(顶刊复现)基于配电网韧性提升的应急移动电源预配置和动态调度(上)—MPS预配置

参考文献&#xff1a; [1] Lei S , Chen C , Zhou H ,et al.Routing and Scheduling of Mobile Power Sources for Distribution System Resilience Enhancement[J].IEEE Transactions on Smart Grid, 2019:5650-5662.DOI:10.1109/TSG.2018.2889347. 这篇博客是上述SCI一区论文…
阅读更多...
最新文章

Copyright @ 2022~2023