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

C++STL初阶(12):stack和queue的初阶实现

1. stack的选型

对于栈的实现是我们非常熟悉的过程:

C语言基础数据结构——栈和队列_栈和队列 插入取出数据-CSDN博客

_top表示下标,_capacity表示空间大小:

那么按照我们原来的思路,利用_top和_capacity T*来给stack构形。

template<typename T>
class stack {
public:
private:T* _arr;int _top;int _capacity;
};

  如果只是按照c语言的思路来实现一个T*的多接口数组就显得有些重复了。


2. 容器适配器 

2.1设计模式

    设计模式就像兵法一样,不是直接拿着刀就上去看(早期的代码都会相对无序),而是要讲究套路和方法的,要注重可维护性。只完成了功能的要求,但是在后期如果要debug或者打补丁就很麻烦。现在的设计模式有23种。

    我们现在已经或多或少接触了两种设计模式,一种是迭代器模式,一种是适配器模式。

比如迭代器模式:

                                         

容器适配器一般都没有iterator,因为iterator的出现会改变其最本质的访问方式。

2.2适配器

适配器是一种用于转换的装置:

适配器:适配器的功能就是转换

比如电源适配器。高压线中的电变压到220v的生活用电也需要电源适配器,220v通过充电线变成给手机的几伏充电线也需要电源适配器。

那什么是容器适配器呢?

栈就是容器适配器,队列也是容器适配器。

我们可以自己手搓数组来实现各个接口。那既然要如上文的C语言思路一样使用数组,为什么不直接用vector呢?

既然能用vector去适配一个栈出来,那为什么不能用list去适配一个栈出来呢?如下:

template<typename T>
class stack{
public:
private:list<T> _st;
};

  或者

template<typename T>
class stack{
public:
private:vector<T> _st;
};

vector和list中都肯定包含push_back  pop_back  back  front这些函数

直接去套用即可。那么我如果两个容器都想使用呢?实现两个非常接近的容器适配器吗?

显然不是,我们直接在模版处传入我们想使用的容器。


3.代码实现 

直接在template处多写一个typename方便传容器类型。

               

如果传入的容器不能使用push_back,说明这个容器不能用于适配,报错即可。

模版参数就像函数参数一样,也可以给缺省值。

比如我们此处就默认stack是包装vector实现的。

template<typename T,typename Container = vector<int>>
class stack {
public:void push(const T& x) {_st.push_back(x);}void pop() {_st.pop_back();}T& top() {return _st.back();}const T& top() const {return _st.back();}bool empty() {return _st.empty();}size_t size() {return _st.size();}private:Container _st;};

就可以直接像正常的vector那样使用了。

或者用list去作为适配的容器:


再用代码来实现queue

queue适合用vector作为容器来适配吗?

在stack中的插入删除都在尾部(栈顶)进行,vector恰好在尾部进行操作比较简单,比较吻合。

而queue既需要在尾部操作,又需要在头部操作,所对于vector这种头插头删时间复杂度都是O(n)的容器来说就不是非常合适。因此我们认为vector不能用于适配 

这是用vector实现的方法:

                   

但是代价太大了。

所以我们将queue按照list和deque作为可适配的容器实现:

template<typename T,typename Container = list<int>>
class queue {
public:void push(const T& x) {_q.push_back(x);}void pop() {_q.pop_front();}bool empty() {return  _q.empty();}T& front() {return _q.front();}const T& front() const {return _q.front();}T& back() {return _q.back();}const T& back() const {return _q.back();}size_t size() {return _q.size();}
private:Container _q;
};

测试:


4. 初识deque(双端队列)

list可以头插头删和尾差尾删

vector支持尾差尾删和方括号访问(当然头插头删可以通过insert和erase实现,但是时间复杂度较高)

deque就是list和vector的结合体

那是不是用deque来实现stack和queue的适配更方便呢?

                                   

底层结构天差地别,但是实际使用效果似乎都不错。

相关文章:

C++STL初阶(12):stack和queue的初阶实现

1. stack的选型 对于栈的实现是我们非常熟悉的过程&#xff1a; C语言基础数据结构——栈和队列_栈和队列 插入取出数据-CSDN博客 _top表示下标&#xff0c;_capacity表示空间大小&#xff1a; 那么按照我们原来的思路&#xff0c;利用_top和_capacity T*来给stack构形。 temp…...

汽车IVI中控OS Linux driver开发实操(二十三):驱动的设备probe及匹配

第一个函数:probe linux驱动模型是分成三个部分的,设备(结构体device),驱动(结构体device_driver),总线(结构体bus_type)。在Linux内核中,设备驱动通常会实现一个probe函数,它是...

华为od(D卷)二叉树计算

文章目录 题目描述输入描述输出描述示例1思路代码 题目描述 给出一个二叉树如下图所示&#xff1a; 6/ \7 9\ / -2 6 请由该二叉树生成一个新的二叉树&#xff0c;它满足其树中的每个节点将包含原始树中的左子树和右子树的和。 20 (7-296)/ \-2 6\ / 0 0 左子树…...

技术爱好者完全用台式机部件定制游戏笔记本电脑

高端笔记本电脑的功能强大到令人难以置信的地步&#xff0c;但大多数笔记本电脑在至少几个关键性能方面仍然落后于台式机。一位 YouTuber 对这种情况感到厌倦&#xff0c;为了抹除这种差距&#xff0c;他开始了为期 14 个月的旅程&#xff0c;使用真正的台式机硬件打造自己的笔…...

100个练习学习Rust!if・Panic・演练

之前的文章 【0】准备 【1】构文・整数・变量 ← 上回 【2】 if・Panic・演练 ← 本次 这是“100 Exercise To Learn Rust”的第2次练习&#xff01;本次的主题包括 if 表达式、panic 机制&#xff0c;以及对前面内容的总结练习。 本次相关的页面如下&#xff1a; 2.3. Bran…...

MODELSIM仿真报错解决记录

目录 问题&#xff1a;Modelsim报错&#xff1a;Error (10228): Verilog HDL error at Line_Shift_RAM_1Bit.v(39): module “Line_Shift_RAM_1 原因&#xff1a;创建的IP核放到了别的位置 解决方法&#xff1a;删掉IP核以及QIP等文件&#xff0c;将IP核创建到工程目录下 问…...

day33-负载均衡实战

01.问题总结 1.rsync同步注意目录加/和不加/的区别 2.安装wordpress过程中禁止使用IP安装,解析成域名安装 比如安装过程 10.0.0.7--->填写数据库信息--->写入数据库中 如果安装完成后再使用www.wp.com访问&#xff0c;不能访问页面乱码的问题。 3.挂载wordpress挂载uplo…...

网络接口 eno1 未连接或未托管

网络接口 eno1 未连接或未托管&#xff0c;通常意味着该接口没有被识别或没有被配置为自动连接到网络。以下是一些可能的解决方案&#xff1a; 检查物理连接&#xff1a; 确保您的以太网电缆正确连接到 eno1 接口和调制解调器/路由器。 启用网络接口&#xff1a; 使用以下命令…...

Linux I/O 多路复用机制详解

文章目录 1 文件描述符&#xff08;File Descriptor&#xff09;1.1 什么是文件描述符&#xff1f;1.2 文件描述符与文件的关系 2 文件描述符集合&#xff08;File Descriptor Set&#xff09;2.1 什么是文件描述符集合&#xff1f;2.2 fd_set 结构体 3 select() 函数的工作原理…...

第43课 Scratch入门篇:雪花随风飘

雪花随风飘 故事背景: 雪花轻轻地从灰蒙蒙的天空中飘落下来,它们像是天空中飘洒下来的羽毛,又像是冬日的精灵在翩翩起舞。每一片雪花都独一无二,它们在空中旋转、飘荡,最终缓缓降落在屋顶、树枝、街道和行人的肩头。 程序原理: 众多的雪花肯定是克隆功能,降落过程是通过…...

VueUse 基于 Vue 3 Composition API 的高质量 Hooks 库

VueUse 是什么? VueUse 是基于 Vue 3 Composition API 的高质量 Hooks 库。例如获取滚动的距离 VueUse 官网:VueUse | VueUse VueUse 什么使用? 1、通过npm安装 VueUse npm i @vueuse/core 2、搜索需要使用的函数,例如搜索 useScroll 滚动 3、使用useScroll 滚动函数 …...

ARM CoreLink 系列 5.1.1 -- CI-700 System Address Map 】

文章目录 System Address MapRN SAMRN SAM memory regions and target typesSAM memory region size configurationRN SAM target ID selectionSystem Address Map 所有的CHI 命令都包含一个 Source ID 和 Target ID, 其中 Source ID 可以来自于 RN Node, Target ID 可以来自…...

【数据结构】二叉树(一)

目录 1. 树型结构 概念 树的表示形式 ​编辑 2. 二叉树&#xff08;重点&#xff09; 2.1 概念 2.2 二叉树的性质 2.3 二叉树的存储 2.4 二叉树的遍历 前中后序遍历 层序遍历&#xff1a; 2.5二叉树的基本操作 本篇主要理解树和二叉树相关概念&#xff0c;二叉树遍…...

使用duplicate搭建备库或者级联备库

使用duplicate搭建备库或者级联备库&#xff1a; 主库或者源端&#xff1a; 1. 创建pfile&#xff0c;更改&添加部分参数、传输到备库&#xff1b; 2. 主库&#xff08;或者源端&#xff09;的tnsnames.ora文件添加 备库的连接信息 备库&#xff1a; 1. 备库添加静态监听 2…...

【存储学习笔记】4:快照(Snapshot)技术的实现方式

1 快照 1.1 动机 在上一篇《备份》里提到&#xff0c;热备份就是在执行操作时&#xff0c;服务器需要正常处理来自用户或应用对数据的更新&#xff0c;这样能够保证数据7*24小时可用&#xff08;在很多服务里这是必要的&#xff09;。 而热备份的困难就是如何保证数据的一致…...

数根(字符串数根公式)

公式&#xff1a;a的数根(a-1)%91&#xff1b; #include <bits/stdc.h> using namespace std; string s; long long sum; int main(){cin>>s;for(int i0;i<s.size();i){sums[i]-0;}cout<<(sum-1)%91; }...

C语言之文件操作上卷(二十一)(逆行人生-2024)

&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3;&#x1f4e3; ✏️作者主页&#xff1a;枫霜剑客 &#x1f4cb; 系列专栏&#xff1a;C语言知识学习归纳总结&#xff08;逐梦篇专栏合集&#xff09; &#x1f332;上一篇: C语…...

【微服务架构实战】结合实际案例进行微服务架构的设计与实现

微服务架构实战 结合实际案例进行微服务架构的设计与实现 引言 微服务架构&#xff08;Microservices Architecture&#xff09;是一种将大型应用程序拆分成一组小型、独立的服务的方法&#xff0c;每个服务都专注于特定的业务功能&#xff0c;并能够独立开发、部署和扩展。这…...

为什么要有二级指针

提示&#xff1a;文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问&#xff1a; 本文目标&#xff1a; 一、背景 之前一直疑问为什么要有二级指针&#xff0c;一直没有写这个帖子&#xff0c;今天整理了一下&#xff0c;收获颇丰 二、 2.1 // 增加对二级指针…...

如何保证数据不丢失?(死信队列)

死信队列 1、什么是死信 死信通常是消息在特定的场景下表现&#xff1a; 消息被拒绝访问消费者发生异常&#xff0c;超过重试次数消息的Expiration过期时长或者队列TTL过期时间消息队列到达最大容量 maxLength 2、什么是死信队列 只由死信构成的消息队列是死信队列 死信队…...

基于距离变化能量开销动态调整的WSN低功耗拓扑控制开销算法matlab仿真

目录 1.程序功能描述 2.测试软件版本以及运行结果展示 3.核心程序 4.算法仿真参数 5.算法理论概述 6.参考文献 7.完整程序 1.程序功能描述 通过动态调整节点通信的能量开销&#xff0c;平衡网络负载&#xff0c;延长WSN生命周期。具体通过建立基于距离的能量消耗模型&am…...

《Playwright:微软的自动化测试工具详解》

Playwright 简介:声明内容来自网络&#xff0c;将内容拼接整理出来的文档 Playwright 是微软开发的自动化测试工具&#xff0c;支持 Chrome、Firefox、Safari 等主流浏览器&#xff0c;提供多语言 API&#xff08;Python、JavaScript、Java、.NET&#xff09;。它的特点包括&a…...

CocosCreator 之 JavaScript/TypeScript和Java的相互交互

引擎版本&#xff1a; 3.8.1 语言&#xff1a; JavaScript/TypeScript、C、Java 环境&#xff1a;Window 参考&#xff1a;Java原生反射机制 您好&#xff0c;我是鹤九日&#xff01; 回顾 在上篇文章中&#xff1a;CocosCreator Android项目接入UnityAds 广告SDK。 我们简单讲…...

微服务商城-商品微服务

数据表 CREATE TABLE product (id bigint(20) UNSIGNED NOT NULL AUTO_INCREMENT COMMENT 商品id,cateid smallint(6) UNSIGNED NOT NULL DEFAULT 0 COMMENT 类别Id,name varchar(100) NOT NULL DEFAULT COMMENT 商品名称,subtitle varchar(200) NOT NULL DEFAULT COMMENT 商…...

工业自动化时代的精准装配革新:迁移科技3D视觉系统如何重塑机器人定位装配

AI3D视觉的工业赋能者 迁移科技成立于2017年&#xff0c;作为行业领先的3D工业相机及视觉系统供应商&#xff0c;累计完成数亿元融资。其核心技术覆盖硬件设计、算法优化及软件集成&#xff0c;通过稳定、易用、高回报的AI3D视觉系统&#xff0c;为汽车、新能源、金属制造等行…...

学校时钟系统,标准考场时钟系统,AI亮相2025高考,赛思时钟系统为教育公平筑起“精准防线”

2025年#高考 将在近日拉开帷幕&#xff0c;#AI 监考一度冲上热搜。当AI深度融入高考&#xff0c;#时间同步 不再是辅助功能&#xff0c;而是决定AI监考系统成败的“生命线”。 AI亮相2025高考&#xff0c;40种异常行为0.5秒精准识别 2025年高考即将拉开帷幕&#xff0c;江西、…...

智能AI电话机器人系统的识别能力现状与发展水平

一、引言 随着人工智能技术的飞速发展&#xff0c;AI电话机器人系统已经从简单的自动应答工具演变为具备复杂交互能力的智能助手。这类系统结合了语音识别、自然语言处理、情感计算和机器学习等多项前沿技术&#xff0c;在客户服务、营销推广、信息查询等领域发挥着越来越重要…...

Mysql8 忘记密码重置,以及问题解决

1.使用免密登录 找到配置MySQL文件&#xff0c;我的文件路径是/etc/mysql/my.cnf&#xff0c;有的人的是/etc/mysql/mysql.cnf 在里最后加入 skip-grant-tables重启MySQL服务 service mysql restartShutting down MySQL… SUCCESS! Starting MySQL… SUCCESS! 重启成功 2.登…...

day36-多路IO复用

一、基本概念 &#xff08;服务器多客户端模型&#xff09; 定义&#xff1a;单线程或单进程同时监测若干个文件描述符是否可以执行IO操作的能力 作用&#xff1a;应用程序通常需要处理来自多条事件流中的事件&#xff0c;比如我现在用的电脑&#xff0c;需要同时处理键盘鼠标…...

uniapp 小程序 学习(一)

利用Hbuilder 创建项目 运行到内置浏览器看效果 下载微信小程序 安装到Hbuilder 下载地址 &#xff1a;开发者工具默认安装 设置服务端口号 在Hbuilder中设置微信小程序 配置 找到运行设置&#xff0c;将微信开发者工具放入到Hbuilder中&#xff0c; 打开后出现 如下 bug 解…...