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的选型 对于栈的实现是我们非常熟悉的过程: C语言基础数据结构——栈和队列_栈和队列 插入取出数据-CSDN博客 _top表示下标,_capacity表示空间大小: 那么按照我们原来的思路,利用_top和_capacity T*来给stack构形。 temp…...
汽车IVI中控OS Linux driver开发实操(二十三):驱动的设备probe及匹配
第一个函数:probe linux驱动模型是分成三个部分的,设备(结构体device),驱动(结构体device_driver),总线(结构体bus_type)。在Linux内核中,设备驱动通常会实现一个probe函数,它是...
华为od(D卷)二叉树计算
文章目录 题目描述输入描述输出描述示例1思路代码 题目描述 给出一个二叉树如下图所示: 6/ \7 9\ / -2 6 请由该二叉树生成一个新的二叉树,它满足其树中的每个节点将包含原始树中的左子树和右子树的和。 20 (7-296)/ \-2 6\ / 0 0 左子树…...
技术爱好者完全用台式机部件定制游戏笔记本电脑
高端笔记本电脑的功能强大到令人难以置信的地步,但大多数笔记本电脑在至少几个关键性能方面仍然落后于台式机。一位 YouTuber 对这种情况感到厌倦,为了抹除这种差距,他开始了为期 14 个月的旅程,使用真正的台式机硬件打造自己的笔…...
100个练习学习Rust!if・Panic・演练
之前的文章 【0】准备 【1】构文・整数・变量 ← 上回 【2】 if・Panic・演练 ← 本次 这是“100 Exercise To Learn Rust”的第2次练习!本次的主题包括 if 表达式、panic 机制,以及对前面内容的总结练习。 本次相关的页面如下: 2.3. Bran…...
MODELSIM仿真报错解决记录
目录 问题:Modelsim报错:Error (10228): Verilog HDL error at Line_Shift_RAM_1Bit.v(39): module “Line_Shift_RAM_1 原因:创建的IP核放到了别的位置 解决方法:删掉IP核以及QIP等文件,将IP核创建到工程目录下 问…...
day33-负载均衡实战
01.问题总结 1.rsync同步注意目录加/和不加/的区别 2.安装wordpress过程中禁止使用IP安装,解析成域名安装 比如安装过程 10.0.0.7--->填写数据库信息--->写入数据库中 如果安装完成后再使用www.wp.com访问,不能访问页面乱码的问题。 3.挂载wordpress挂载uplo…...
网络接口 eno1 未连接或未托管
网络接口 eno1 未连接或未托管,通常意味着该接口没有被识别或没有被配置为自动连接到网络。以下是一些可能的解决方案: 检查物理连接: 确保您的以太网电缆正确连接到 eno1 接口和调制解调器/路由器。 启用网络接口: 使用以下命令…...
Linux I/O 多路复用机制详解
文章目录 1 文件描述符(File Descriptor)1.1 什么是文件描述符?1.2 文件描述符与文件的关系 2 文件描述符集合(File Descriptor Set)2.1 什么是文件描述符集合?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. 二叉树(重点) 2.1 概念 2.2 二叉树的性质 2.3 二叉树的存储 2.4 二叉树的遍历 前中后序遍历 层序遍历: 2.5二叉树的基本操作 本篇主要理解树和二叉树相关概念,二叉树遍…...
使用duplicate搭建备库或者级联备库
使用duplicate搭建备库或者级联备库: 主库或者源端: 1. 创建pfile,更改&添加部分参数、传输到备库; 2. 主库(或者源端)的tnsnames.ora文件添加 备库的连接信息 备库: 1. 备库添加静态监听 2…...
【存储学习笔记】4:快照(Snapshot)技术的实现方式
1 快照 1.1 动机 在上一篇《备份》里提到,热备份就是在执行操作时,服务器需要正常处理来自用户或应用对数据的更新,这样能够保证数据7*24小时可用(在很多服务里这是必要的)。 而热备份的困难就是如何保证数据的一致…...
数根(字符串数根公式)
公式:a的数根(a-1)%91; #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)
📣📣📣📣📣📣📣📣 ✏️作者主页:枫霜剑客 📋 系列专栏:C语言知识学习归纳总结(逐梦篇专栏合集) 🌲上一篇: C语…...
【微服务架构实战】结合实际案例进行微服务架构的设计与实现
微服务架构实战 结合实际案例进行微服务架构的设计与实现 引言 微服务架构(Microservices Architecture)是一种将大型应用程序拆分成一组小型、独立的服务的方法,每个服务都专注于特定的业务功能,并能够独立开发、部署和扩展。这…...
为什么要有二级指针
提示:文章 文章目录 前言一、背景二、 2.1 2.2 总结 前言 前期疑问: 本文目标: 一、背景 之前一直疑问为什么要有二级指针,一直没有写这个帖子,今天整理了一下,收获颇丰 二、 2.1 // 增加对二级指针…...
如何保证数据不丢失?(死信队列)
死信队列 1、什么是死信 死信通常是消息在特定的场景下表现: 消息被拒绝访问消费者发生异常,超过重试次数消息的Expiration过期时长或者队列TTL过期时间消息队列到达最大容量 maxLength 2、什么是死信队列 只由死信构成的消息队列是死信队列 死信队…...
TDengine 快速体验(Docker 镜像方式)
简介 TDengine 可以通过安装包、Docker 镜像 及云服务快速体验 TDengine 的功能,本节首先介绍如何通过 Docker 快速体验 TDengine,然后介绍如何在 Docker 环境下体验 TDengine 的写入和查询功能。如果你不熟悉 Docker,请使用 安装包的方式快…...
Linux链表操作全解析
Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表?1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...
云计算——弹性云计算器(ECS)
弹性云服务器:ECS 概述 云计算重构了ICT系统,云计算平台厂商推出使得厂家能够主要关注应用管理而非平台管理的云平台,包含如下主要概念。 ECS(Elastic Cloud Server):即弹性云服务器,是云计算…...
uni-app学习笔记二十二---使用vite.config.js全局导入常用依赖
在前面的练习中,每个页面需要使用ref,onShow等生命周期钩子函数时都需要像下面这样导入 import {onMounted, ref} from "vue" 如果不想每个页面都导入,需要使用node.js命令npm安装unplugin-auto-import npm install unplugin-au…...
vscode(仍待补充)
写于2025 6.9 主包将加入vscode这个更权威的圈子 vscode的基本使用 侧边栏 vscode还能连接ssh? debug时使用的launch文件 1.task.json {"tasks": [{"type": "cppbuild","label": "C/C: gcc.exe 生成活动文件"…...
定时器任务——若依源码分析
分析util包下面的工具类schedule utils: ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类,封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz,先构建任务的 JobD…...
linux 错误码总结
1,错误码的概念与作用 在Linux系统中,错误码是系统调用或库函数在执行失败时返回的特定数值,用于指示具体的错误类型。这些错误码通过全局变量errno来存储和传递,errno由操作系统维护,保存最近一次发生的错误信息。值得注意的是,errno的值在每次系统调用或函数调用失败时…...
【C语言练习】080. 使用C语言实现简单的数据库操作
080. 使用C语言实现简单的数据库操作 080. 使用C语言实现简单的数据库操作使用原生APIODBC接口第三方库ORM框架文件模拟1. 安装SQLite2. 示例代码:使用SQLite创建数据库、表和插入数据3. 编译和运行4. 示例运行输出:5. 注意事项6. 总结080. 使用C语言实现简单的数据库操作 在…...
成都鼎讯硬核科技!雷达目标与干扰模拟器,以卓越性能制胜电磁频谱战
在现代战争中,电磁频谱已成为继陆、海、空、天之后的 “第五维战场”,雷达作为电磁频谱领域的关键装备,其干扰与抗干扰能力的较量,直接影响着战争的胜负走向。由成都鼎讯科技匠心打造的雷达目标与干扰模拟器,凭借数字射…...
Spring AI与Spring Modulith核心技术解析
Spring AI核心架构解析 Spring AI(https://spring.io/projects/spring-ai)作为Spring生态中的AI集成框架,其核心设计理念是通过模块化架构降低AI应用的开发复杂度。与Python生态中的LangChain/LlamaIndex等工具类似,但特别为多语…...


