当前位置: 首页 > news >正文

【C++】适配器模式 - - stack/queue/deque

目录

一、适配器模式

1.1迭代器模式

1.2适配器模式

二、stack

2.1stack 的介绍和使用

2.2stack的模拟实现

三、queue

3.1queue的介绍和使用

3.2queue的模拟实现

 四、deque(不满足先进先出,和队列无关)

4.1deque的原理介绍

4.2deque的特点(支持头删,支持随机访问)

4.3deque的底层结构(buffer+中控指针数组)

五、总结

答案一: 

答案二:

答案三:


一、适配器模式

1.1迭代器模式

其实我们在前面学习 string、vector 和 list 时就已经接触过设计模式了 – 迭代器就是一种设计模式;迭代器模式是封装后提供统一的接口 iterator,在不暴露底层实现细节的情况下,使得上层能够以相同的方式来访问不同的容器

1.2适配器模式

适配器模式则是:

用已有的东西封装转换出想要的东西


二、stack

2.1stack 的介绍和使用

 和我们以前学的容器不同,为了不破坏栈 LIFO 的特性,stack 不提供迭代器,所以 stack 不是迭代器模式,而是一种容器适配器

如图,stack 使用 dqueue 容器作为默认的适配容器(后面讲一个吕布和诸葛亮的参照),关于 dqueue 的内容,我们放在文章最后面讲。

stack的常用接口:

函数说明接口说明
stack()构造空的栈
empty()检测stack是否为空
size()返回stack中元素的个数
top()返回栈顶元素的引用
push()栈顶入栈
pop()栈顶出栈

2.2stack的模拟实现

在了解了适配器模式之后,我们就可以将适配器作为类的第二个模板参数,然后通过传递不同的适配容器来实现栈了:

 

如上,vector 和 list 都可以作为 stack 的适配容器,我们可以通过给定不同的第二个模板参数来使用不同的容器适配 stack;

但是出于随机抽取和缓存命中的考虑,vector 显然更适合作为 stack 的适配容器,那么我们可以还可以将 vector 设置为 stack 的默认适配容器,这样,我们以后定义栈对象时就不用显式指定 vector 了

stack.h 文件

#include <iostream>
#include <vector>
#include <list>namespace lzy {template<class T, class Container = std::vector<T>>class stack {public://构造和析构不用写,默认生成的构造和析构对于自定义类型会调用它们的构造和析构函数bool empty() const {return _Con.empty();}size_t size() const {return _Con.size();}T& top() {return _Con.back();  //数组尾部作为栈的栈顶}const T& top() const {return _Con.back();}void push(const T& val) {_Con.push_back(val);  //在数组尾部插入数据}void pop() {_Con.pop_back();}private:Container _Con;};
}

 测试代码:

void test_stack() {//stack<int, std::vector<int>> st1;//stack<int, std::list<int>> st2;//stack<int> st1;  //默认使用vector做适配容器//stack<int, std::list<int>> st2;  //使用其他容器做适配容器需要显式指定stack<int> st;st.push(1);st.push(2);st.push(3);st.push(4);st.push(5);cout << st.size() << endl;while (!st.empty()) {cout << st.top() << " ";st.pop();}cout << endl;
}

三、queue

3.1queue的介绍和使用

 和 stack 一样,queue 也是一种容器适配器,也不提供迭代器

可以看到,queue 也是使用 deque 作为默认适配容器,和之前一样,deque 我们放在最后面讲。

queue 常用接口的使用

函数声明接口说明
queue()构造空的队列
empty()检测队列是否为空
size()返回队列中有效元素的个数
front()返回队头元素的引用
back()返回队尾元素的引用
push()在队尾将元素val入队列
pop()将队头元素出队列

3.2queue的模拟实现

 

这里queue与stack不同的是,stack俩个均可,但是vector更好;但是队列这里头删用vector是效率很低的办法,所以队列只可以用list

queue.h

#pragma once#include <iostream>
#include <vector>
#include <list>namespace lzy {template<class T, class Container = std::list<T>>class queue {public://构造和析构不用写,默认生成的构造和析构对于自定义类型会调用它们的构造和析构函数bool empty() const {return _Con.empty();}size_t size() const {return _Con.size();}T& front() {return _Con.front();  //第一个节点为队头}const T& front() const {return _Con.front();}T& back() {return _Con.back();  //最后一个节点为队尾}const T& back() const {return _Con.back();  //最后一个节点为队尾}void push(const T& val) {_Con.push_back(val);  //在链表尾部插入节点}void pop() {_Con.pop_front();  //删除第一个节点}private:Container _Con;};
}

测试代码:

void test_queue() {queue<int> q; //默认使用list做适配容器q.push(1);q.push(2);q.push(3);q.push(4);q.push(5);cout << q.size() << endl;while (!q.empty()) {cout << q.front() << " ";q.pop();}cout << endl;
}

 


 四、deque(不满足先进先出,和队列无关)

4.1deque的原理介绍

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

4.2deque的特点(支持头删,支持随机访问)

我们的stack用vector是为了缓存命中,而且因为先进后出的特性用链表不合适

我们的queue用list是因为list的头删效率更高

但是deque横空出世,具有随机访问和头插头删效率不错的特点(只不过每一个特点都没有发挥到极致)

不过不可否认的是 deque 确实很适合作为 stack 和 list 的默认适配容器,毕竟它对于 stack 和 list 的通用的,这也是 STL 中选择 deque 作为 stack 和 queue 默认适配容器的原因。

deque 特别适合需要大量进行头插和尾部数据的插入删除、偶尔随机访问、偶尔中部插入删除的场景;不太适合需要大量进行随机访问与中部数据插入删除的场景,特别是排序

总结:他没有vector访问数据那么极致,也没有list插入数据那么牛逼,但是他俩个特点都有,作为俩个容器的适配器也是非常合适的!

4.3deque的底层结构(buffer+中控指针数组)

deque 并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际 deque 类似于一个动态的二维数组,其结构示意图如下:

关于扩容:只有当中空指针数组满了,才会扩容

关于尾插:后面新开一个buffer

关于头插:前面新开一个buffer

关于随机访问:1.查询哪一个buffer2.查询在哪一个buffer的哪一个位置

五、总结

答案一: 

答案二:

答案三:

希望对大家有所帮助!

相关文章:

【C++】适配器模式 - - stack/queue/deque

目录 一、适配器模式 1.1迭代器模式 1.2适配器模式 二、stack 2.1stack 的介绍和使用 2.2stack的模拟实现 三、queue 3.1queue的介绍和使用 3.2queue的模拟实现 四、deque&#xff08;不满足先进先出&#xff0c;和队列无关&#xff09; 4.1deque的原理介绍 4.2dequ…...

EKP接口开发Webservice服务和Restservice服务以及定时任务Demo

继承com.landray.kmss.sys.webservice2.interfaces.ISysWebservice&#xff0c;同时在接口上使用WebService注解将其标识为WebService接口 package com.landray.kmss.third.notify.webservice;import com.alibaba.fastjson.JSONObject; import com.landray.kmss.sys.webservic…...

如何确定IP地址的具体位置?

IP地址通过几种方法帮助确定具体位置&#xff0c;尽管它们的准确性和精度因不同的情况而异。以下是几种确定具体位置的主要方法&#xff1a; 地理IP数据库&#xff1a;这是最常用的方法之一&#xff0c;它使用IP地址和地理位置数据的映射来确定用户的位置。这些数据库存储了大量…...

软考-网络安全体系与网络安全模型

本文为作者学习文章&#xff0c;按作者习惯写成&#xff0c;如有错误或需要追加内容请留言&#xff08;不喜勿喷&#xff09; 本文为追加文章&#xff0c;后期慢慢追加 by 2023年10月 网络安全体系相关安全模型 BLP机密性模型 BLP&#xff08;Biba-格雷泽-麦克拉伦&#x…...

Java身份证OCR识别 - 阿里云API【识别准确率超过99%】

1. 阿里云API市场 https://market.aliyun.com/products/57124001/cmapi00063618.html?spm5176.28261954.J_7341193060.41.60e52f3drduOTh&scm20140722.S_market%40%40API%E5%B8%82%E5%9C%BA%40%40cmapi00063618._.ID_market%40%40API%E5%B8%82%E5%9C%BA%40%40cmapi0006361…...

vue中获取复选框是否被选中的值、如何用JavaScript判断复选框是否被选中

一、方法介绍 第一种方法&#xff1a;通过获取dom元素&#xff0c;getElementById、querySelector、getElementsByName、querySelectorAll&#xff08;需要遍历&#xff0c;例如&#xff1a;for循环&#xff09; 第二种是用v-model在input复选框上绑定一个变量&#xff0c;通过…...

Python学习之逻辑中的循环有哪些?

1. for循环 for 循环用于迭代 (遍历)一个序列&#xff0c;例如列表、元组、字符串或字典中的元素。 通常使用 for 循环来遍历可迭代对象中的元素&#xff0c;并对每个元素执行相同的操作。 示例: for item in iterable: # 执行操作2.while循环 -while循环用于在满足某个条件…...

【uniapp微信小程序+springBoot(binarywang)

uniapp前端代码 <template><view><page-head :title"title"></page-head><view class"uni-padding-wrap"><view style"background:#FFF; padding:50rpx 0;"><view class"uni-hello-text uni-cente…...

智能井盖的用处有哪些?好用在什么地方?

智能井盖是一种基于物联网技术的井盖系统&#xff0c;通过集成传感器、通信设备和数据处理功能&#xff0c;实现对井盖的实时监测、远程管理和智能化控制。WITBEE万宾的智能井盖传感器EN100-C2&#xff0c;只要在城市需要的井盖上面安装即可使用&#xff0c;一体式结构&#xf…...

微信小程序数据存储方式有哪些

在微信小程序中&#xff0c;数据存储方式有以下几种&#xff1a; 本地存储 本地存储是一种轻量级的数据存储方式&#xff0c;用于存储小量的数据&#xff0c;例如用户的配置信息、页面的状态等。微信小程序提供了 wx.setStorage() 和 wx.getStorage() 方法&#xff0c;用于将数…...

FTC局部路径规划代码分析

前置知识: costmap_2d::Costmap2DROS costmap; costmap_2d::Costmap2DROS 是一个ROS包中提供的用于处理2D成本地图的类。它是一个高级的接口&#xff0c;通常用于与ROS导航栈中的导航规划器和本地路径跟踪器等模块进行集成。 costmap 是一个指向 Costmap2DROS 对象的指针。通…...

SpringBoot集成Activiti7

SpringBoot集成Activiti7 SpringBoot版本使用2.7.16 <parent><groupId>org.springframework.boot</groupId><artifactId>spring-boot-starter-parent</artifactId><version>2.7.16</version><relativePath/> <!-- lookup…...

25.1 MySQL SELECT语句

1. SQL概述 1.1 SQL背景知识 1946年, 世界上诞生了第一台电脑, 而今借由这台电脑的发展, 互联网已经成为一个独立的世界. 在过去几十年里, 许多技术和产业在互联网的舞台上兴衰交替. 然而, 有一门技术却从未消失, 甚至日益强大, 那就是SQL.SQL(Structured Query Language&…...

【VSCode】Windows环境下,VSCode 搭建 cmake 编译环境(通过配置文件配置)

除了之前的使用 VSCode 插件来编译工程外&#xff0c;我们也可以使用配置文件来编译cmake工程&#xff0c;主要依赖 launch.json 和 tasks.json 文件。 目录 一、下载编译器 1、下载 Windows GCC 2、选择编译器路径 二、配置 debug 环境 1、配置 lauch.json 文件 2、配置…...

useragent识别访问设备

背景需求 ruoyi框架&#xff0c;前后端分离。现在要在用户访问的时候根据不同的设备跳转到不同的登录页面。 教程 router/index.js 修改src/router/index.js&#xff0c;在这里增加自己的要跳转的页面 permission.js 在白名单中添加自己的登录页面 增加以下识别的代码 le…...

紫光同创FPGA实现UDP协议栈网络视频传输,带录像和抓拍功能,基于YT8511和RTL8211,提供2套PDS工程源码和技术支持

目录 1、前言免责声明 2、相关方案推荐我这里已有的以太网方案紫光同创FPGA精简版UDP方案紫光同创FPGA带ping功能UDP方案紫光同创FPGA精简版UDP视频传输方案 3、设计思路框架OV5640摄像头配置及采集数据缓冲FIFOUDP协议栈详解MAC层发送MAC发送模式MAC层接收ARP发送ARP接收ARP缓…...

【机器学习】逻辑回归

文章目录 逻辑回归定义损失函数正则化 sklearn里面的逻辑回归多项式逻辑回归 逻辑回归 逻辑回归&#xff0c;是一种名为“回归”的线性分类器&#xff0c;其本质是由线性回归变化而来的&#xff0c;一种广泛使用于分类问题中的广义回归算法。 线性回归是机器学习中最简单的的…...

DITA-OT 4.0新特性 - PDF themes,定制PDF样式的新方法

随着DITA-OT 4.0的发布&#xff0c;它提供了一种新的定制PDF样式方法&#xff0c;这种方法就是PDF theme。这篇文章来聊一聊这种定制PDF输出的新方法和实验结果。 在进入PDF theme细节之前&#xff0c;为各位读者梳理一下DITA-OT将DITA和Markdown发布成PDF的几种方法。 - 1 …...

MySQL 8.0 OCP认证精讲视频、环境和题库之四 多实例启动 缓存、事务、脏读

一、配置第一个mysqld服务 1、编辑选项文件&#xff0c;指定以下选项&#xff1a; [mysqld] basedir/mysql80 datadir/mysql80/data1 socket/mysql80/data1/mysqld.sock pid-file/mysql80/data1/mysqld.pid log-error/mysql80/dat…...

对代码感兴趣 但不擅长数学怎么办——《机器学习图解》来救你

目前&#xff0c;该领域中将理论与实践相结合、通俗易懂的著作较少。机器学习是人工智能的一部分&#xff0c;很多初学者往往把机器学习和深度学习作为人工智能入门的突破口&#xff0c;非科班出身的人士更是如此。当前&#xff0c;国内纵向复合型人才和横向复合型人才奇缺;具有…...

2025盘古石杯决赛【手机取证】

前言 第三届盘古石杯国际电子数据取证大赛决赛 最后一题没有解出来&#xff0c;实在找不到&#xff0c;希望有大佬教一下我。 还有就会议时间&#xff0c;我感觉不是图片时间&#xff0c;因为在电脑看到是其他时间用老会议系统开的会。 手机取证 1、分析鸿蒙手机检材&#x…...

MySQL中【正则表达式】用法

MySQL 中正则表达式通过 REGEXP 或 RLIKE 操作符实现&#xff08;两者等价&#xff09;&#xff0c;用于在 WHERE 子句中进行复杂的字符串模式匹配。以下是核心用法和示例&#xff1a; 一、基础语法 SELECT column_name FROM table_name WHERE column_name REGEXP pattern; …...

Rapidio门铃消息FIFO溢出机制

关于RapidIO门铃消息FIFO的溢出机制及其与中断抖动的关系&#xff0c;以下是深入解析&#xff1a; 门铃FIFO溢出的本质 在RapidIO系统中&#xff0c;门铃消息FIFO是硬件控制器内部的缓冲区&#xff0c;用于临时存储接收到的门铃消息&#xff08;Doorbell Message&#xff09;。…...

Golang——6、指针和结构体

指针和结构体 1、指针1.1、指针地址和指针类型1.2、指针取值1.3、new和make 2、结构体2.1、type关键字的使用2.2、结构体的定义和初始化2.3、结构体方法和接收者2.4、给任意类型添加方法2.5、结构体的匿名字段2.6、嵌套结构体2.7、嵌套匿名结构体2.8、结构体的继承 3、结构体与…...

API网关Kong的鉴权与限流:高并发场景下的核心实践

&#x1f525;「炎码工坊」技术弹药已装填&#xff01; 点击关注 → 解锁工业级干货【工具实测|项目避坑|源码燃烧指南】 引言 在微服务架构中&#xff0c;API网关承担着流量调度、安全防护和协议转换的核心职责。作为云原生时代的代表性网关&#xff0c;Kong凭借其插件化架构…...

【Linux】Linux安装并配置RabbitMQ

目录 1. 安装 Erlang 2. 安装 RabbitMQ 2.1.添加 RabbitMQ 仓库 2.2.安装 RabbitMQ 3.配置 3.1.启动和管理服务 4. 访问管理界面 5.安装问题 6.修改密码 7.修改端口 7.1.找到文件 7.2.修改文件 1. 安装 Erlang 由于 RabbitMQ 是用 Erlang 编写的&#xff0c;需要先安…...

智能职业发展系统:AI驱动的职业规划平台技术解析

智能职业发展系统&#xff1a;AI驱动的职业规划平台技术解析 引言&#xff1a;数字时代的职业革命 在当今瞬息万变的就业市场中&#xff0c;传统的职业规划方法已无法满足个人和企业的需求。据统计&#xff0c;全球每年有超过2亿人面临职业转型困境&#xff0c;而企业也因此遭…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...

基于Python的气象数据分析及可视化研究

目录 一.&#x1f981;前言二.&#x1f981;开源代码与组件使用情况说明三.&#x1f981;核心功能1. ✅算法设计2. ✅PyEcharts库3. ✅Flask框架4. ✅爬虫5. ✅部署项目 四.&#x1f981;演示效果1. 管理员模块1.1 用户管理 2. 用户模块2.1 登录系统2.2 查看实时数据2.3 查看天…...

安装最新elasticsearch-8.18.2

1.环境我的环境是linux麒麟服务器 (安装 es 7.8以上 java环境必须11以上,可以单独配置es的java目录) 2.下载 官网的地址:下载 Elastic 产品 | Elastic Download Elasticsearch | Elastic Elasticsearch 入门 | Elasticsearch 中文文档 文档 3.我下载的是8.18的 Elasti…...