【C++】STL之适配器---用deque实现栈和队列

目录

前言

一、deque

 1、deque 的原理介绍

 2、deque 的底层结构

 3、deque 的迭代器

 4、deque 的优缺点

  4.1、优点

  4.2、缺点

二、stack 的介绍和使用

 1、stack 的介绍

 2、stack 的使用

 3、stack 的模拟实现

三、queue 的介绍和使用

 1、queue 的介绍 

 2、queue 的使用

 3、queue 的模拟实现


前言

  容器适配器,按字面意思理解的话,就是用来对一个容器进行匹配的。在C++STL中,容器有:vector,list,deque,map,set等。而在C++STL中不把stack和queue纳入容器的范围而是纳入容器适配器的范围是因为:

  stack和queue没有下标随机访问等操作,只有普通的pop_front,push_back,pop_back()等操作,而这些函数在其他容器中完全可以有,栈和队列的实现完全可以将其他容器的操作进行复用,这就是stack和queue作为容器适配器的原因。

  适配器是一种设计模式(设计模式是一套被反复使用的、多数人知晓的、经过分类编目的、代码设计经验的总 结),该种模式是将一个类的接口转换成客户希望的另外一个接口。

一、deque

 1、deque 的原理介绍

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

 2、deque 的底层结构

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

 3、deque 的迭代器

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

 4、deque 的优缺点

  4.1、优点

  • 具有 vector 的优点 ---支持随机访问、缓存命中率较高、尾部插入删除数据效率高;
  • 同时具有 list 的优点 --- 空间浪费少、头部插入插入数据效率高;

  4.2、缺点

  • deque 的随机访问效率较低 --- 需要先通过中控数据找到对应的buffer数组,再找到具体的位置 (假设偏移量为 i,需先 i/10 得到位于第几个buffer数组,再 i%10 得到 buffer 数组中的具体位置),即 deque 随机访问时一次跳过一个buffer数组,需要跳多次才能准确定位,其效率比 list 高了不少,但比 vector 也低了不少;
  • deque 在中部插入删除数据的效率是比较低的 --- 需要挪动数据,但不一定后续 buffe 数组中的数据全部挪动,可以控制只挪一部分,即中间插入删除数据的效率高于 vector,但是低于 list。

 所以综上分析, deque 结合了 vector 和 list 的优缺点,看似很完美,但是它单方面的性能是不如 vector 或者 list 的,因此 deque 在实际应用中使用的非常少。

STL 中选择 deque 作为 stack 和 queue 默认适配容器的原因:

  • stack 和 queue 不需要遍历(因此stack和queue没有迭代器),只需要在固定的一端或者两端进行操作。
  • 在 stack 中元素增长时,deque 比 vector 的效率高(扩容时不需要搬移大量数据);queue 中的元素增长时,deque不仅效率高,而且内存使用率高。

结合了deque的优点,而完美的避开了其缺陷。

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

二、stack 的介绍和使用

 1、stack 的介绍

  1. stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。
  2. stack是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定 的成员函数来访问其元素,将特定类作为其底层的,元素特定容器的尾部(即栈顶)被压入和弹出。
  3. stack 的底层容器可以是任何标准的容器类模板或者一些其他特定的容器类,这些容器类应该支持以下操作:empty:判空操作 back:获取尾部元素操作 push_back:尾部插入元素操作 pop_back:尾部删除元素操作;
  4. 标准容器vector、deque、list均符合这些需求,默认情况下,如果没有为stack指定特定的底层容器, 默认情况下使用deque。

 2、stack 的使用

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

下面是栈的使用操作: 

int main()
{//构造空栈stack<int> s;//元素入栈s.push(1);s.push(2);//获取栈中元素个数int Size = s.size();cout << Size << endl;//获取栈顶元素的引用int sTop = s.top();cout << sTop << endl;//元素出栈s.pop();sTop = s.top();cout << sTop << endl;//判断栈是否为空cout << s.empty();return 0;
}

 3、stack 的模拟实现

  我们在这里为栈模板定义了两个模板参数:是栈中存储的元素的类型Container 是栈模板使用的底层结构Container 的默认值是 vector,如果你想要用别的,可以在这里进行设置。我就可以将适配器作为类的第二个模板参数,然后通过传递不同的适配容器来实现栈了:

//stack.h
template<class T, class Container>
class stack 
{//...
};
//test.cpp
void test_stack() 
{stack<int, vector<int>> st1;stack<int, list<int>> st2;
}

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

 经过前期的学习,显然更适合作为 stack 的适配容器,那么我们可以还可以将 vector 设置为 stack 的默认适配容器:

//stack.h
template<class T, class Container = vector<T>>
class stack 
{//...
};
//test.cpp
void test_stack() 
{//默认使用vector做适配容器stack<int> st1;  //使用其他容器做适配容器需要显式指定stack<int, list<int>> st2;  
}

 有了适配容器之后,我们就可以更容易的通过调用适配容器的接口来实现 stack 的接口了。

namespace xx
{//适配器模式/配接器template <class T, class Container = deque<T>>class stack{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_back();}const T& top(){return _con.back();}bool size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_stack(){//stack<int,vector<int>> st;//数组栈stack<int, list<int>> st;//链表栈st.push(1);st.push(2);st.push(3);st.push(4);while (!st.empty()){cout << st.top() << " ";st.pop();}cout << endl;}
}

stack 可以使用 vector 或者 list 来实现,效率相当。插入数据就相当于尾插,删除栈顶元素就相当于尾删。

三、queue 的介绍和使用

 1、queue 的介绍 

  1. 队列是一种容器适配器,专门用于在 FIFO 上下文(先进先出)中操作,其中从容器一端插入元素,另一端提取元素。
  2. 队列作为容器适配器实现,容器适配器即将特定容器类封装作为其底层容器类,queue 提供一组特定的 成员函数来访问其元素。元素从队尾入队列,从队头出队列。
  3. 底层容器可以是标准容器类模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作: empty:检测队列是否为空 ; size:返回队列中有效元素的个数; front:返回队头元素的引用;back:返回队尾元素的引用;push_back:在队列尾部入队列;pop_front:在队列头部出队列;
  4. 标准容器类 deque 和 list 满足了这些要求。默认情况下,如果没有为 queue 实例化指定容器类,则使用标准容器 deque。

 2、queue 的使用

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

下面是队列的使用操作:

int main() 
{//构造空队列queue<int> q;//元素入队q.push(1);q.push(2);//返回有效元素个数int size = q.size();cout << size << endl;//检查队列是否为空cout << q.empty() << endl;//获取队头元素的引用int front = q.front();cout << front << endl;//获取队尾元素的引用 int back = q.back();cout << back << endl;//队头元素出队q.pop();return 0;
}

 3、queue 的模拟实现

  它的模拟实现过程和 stack 类似,vector 和 list 都可以作为 queue 的适配容器,但是由于 queue 需要大量在头部删除数据,所以使用 deque 作为 queue 的默认适配容器,那么 queue 模拟实现的代码如下:

namespace xx
{template <class T, class Container = deque<T>>class queue{public:void push(const T& x){_con.push_back(x);}void pop(){_con.pop_front();}const T& front(){return _con.front();}const T& back(){return _con.back();}bool size(){return _con.size();}bool empty(){return _con.empty();}private:Container _con;};void test_queue(){queue<int> q;q.push(1);q.push(2);q.push(3);q.push(4);while (!q.empty()){cout << q.front() << " ";q.pop();}cout << endl;}
}


本文要是有不足的地方,欢迎大家在下面评论,我会在第一时间更正。

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

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

构建可维护的大规模应用:框架架构的最佳实践

文章目录 框架架构的重要性最佳实践1. 模块化设计2. 遵循SOLID原则3. 使用设计模式4. 异常处理5. 代码注释和文档6. 测试 Spring Boot 和 Django&#xff1a;关键框架示例Spring Boot&#xff08;Java&#xff09;模块化设计&#xff1a;SOLID原则&#xff1a;设计模式&#xf…

关于OpenFeign 接口参数定义的问题

文章目录 前言一、声明GET请求实际用POST &#xff1f;1.1 例子&#xff1a;1.2 原因&#xff1a; 二、GET请求放入了参数值却找不到?2.1 例子&#xff1a;2.2 原因&#xff1a;2.3 spring-mvc http 请求中为什么可以&#xff1a; 三、异步线程无法调用feign 接口 ?3.1 例子&…

Python经典练习题(一)

文章目录 &#x1f340;第一题&#x1f340;第二题&#x1f340;第三题&#x1f340;第四题&#x1f340;第五题 &#x1f340;第一题 有四个数字&#xff1a;1、2、3、4&#xff0c;能组成多少个互不相同且无重复数字的三位数&#xff1f;各是多少&#xff1f; 这里我们使用…

【开关稳压器】LMR16030SDDA、LMR38010FDDAR,汽车类LMR43610MSC5RPERQ1低 EMI 同步降压稳压器

一、LMR16030SDDA 开关稳压器 IC REG BUCK ADJ 3A 8SOPWR LMR16030 是一款带有集成型高侧 MOSFET 的 60V、3A SIMPLE SWITCHER 降压稳压器。该器件具有4.3V 至 60V 的宽输入范围&#xff0c;适用于从工业到汽车各类应用中非稳压电源的电源调节。该稳压器在睡眠模式下的静态电流…

leetcode:70. 爬楼梯

一、题目 函数原型&#xff1a;int climbStairs(int n) 二、思路 此题运用递归思想。当只有1个台阶&#xff0c;那么只有1种方法爬到楼顶——跨一个台阶&#xff1b;当有2个台阶时&#xff0c;有2种方法爬到楼顶——跨一个台阶跨两次或直接跨两个台阶。当有3个台阶或更多台阶时…

vue之 h() 函数

前言 Vue推荐在绝大数情况下使用模板来创建HTML&#xff0c;然后一些特殊的场景&#xff0c;你真的需要JavaScript的完全编程的能力&#xff0c;这个时候你可以使用渲染函数 &#xff0c;它比模板更接近编译器&#xff1b; h()函数是什么 Vue在生成真实的DOM之前&#xff0c…

Java LinkedList类详解

目录 什么是LinkedList LinkedList的使用 LinkedList的构造 LinkedList的其他常用方法的介绍 LinkedList的遍历 ArrayList和LinkedList的区别 什么是LinkedList LinkList的底层是双向链表结构&#xff0c;由于链表没有将元素存储在连续的空间中&#xff0c;元素存储在单独…

[C++随笔录] vector模拟实现

vector模拟实现 基本结构天选之子构造拷贝构造析构operator 空间reserveresizesize && capacity 增insertpush_back 删erasepop_back 查 && 改swapoperator[] 源码 基本结构 // 可以是不同类型, 用类模板 template <class T> class vector { public:// 源…

画一个时钟(html+css+js)

这是一个很简约的时钟。。。。。。。 效果&#xff1a; 代码&#xff1a; <template><div class"demo-box"><div class"clock"><ul class"mark"><liv-for"(rotate, index) in rotatedAngles":key"i…

VBA技术资料MF59:从二维变体数组中删除一行数据

【分享成果&#xff0c;随喜正能量】小小的善业&#xff0c;能赢来大的利益&#xff0c;小小的恶业&#xff0c;同样也能招致严重的后果。这正如古语所云&#xff1a;“莫以善小而不为&#xff0c;莫以恶小而为之。。 我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效…

想学嵌入式开发,薪资怎么样?

想学嵌入式开发&#xff0c;薪资怎么样&#xff1f; 对于嵌入式工程师来说呢&#xff0c;它重点学习内容就是首先一定要打好基础&#xff0c;如果从编程语言角度来讲&#xff0c;那么可以在语言上选C或者C&#xff0c;你可以选择其中任何一门语言作为你的入门。 最近很多小伙伴…

Unity之NetCode多人网络游戏联机对战教程(1)

文章目录 1.什么是NetCode2.安装NGO 1.什么是NetCode 官网链接&#xff1a;https://docs-multiplayer.unity3d.com/netcode/current/about/ Netcode for GameObjects&#xff08;NGO&#xff09;是专为Unity构建的高级网络库。它能够在网络会话中将GameObject和世界数据同时发…

计算机组成原理——基础入门总结(二)

上一期的路径&#xff1a;基础入门总结&#xff08;一&#xff09; 目录 一.输入输出系统和IO控制方式 二.存储系统的基本概念 三.cache的基本概念和原理 四.CPU的功能和基本结构 五.总线概述 一.输入输出系统和IO控制方式 IO设备又可以被统一称为外部设备~ IO接口&…

每日一题~修剪二叉树

原题链接&#xff1a;669. 修剪二叉搜索树 - 力扣&#xff08;LeetCode&#xff09; 题目描述&#xff1a; 思路分析&#xff1a; 由题可知&#xff0c;我们要将原来的二叉搜索树调整为值在 low~high 之间的新二叉搜索树&#xff0c;接下来我们分析一下针对不同的节点的处理方…

Hbase工作原理

Hbase&#xff1a;HBase 底层原理详解&#xff08;深度好文&#xff0c;建议收藏&#xff09; - 腾讯云开发者社区-腾讯云 Hbase架构图 同一个列族如果有多个store&#xff0c;那么这些store在不同的region Hbase写流程&#xff08;读比写慢&#xff09; MemStore Flush Hbas…

微信朋友圈的高级玩法

面对好友的生日&#xff0c;你还在傻傻的守点发朋友圈&#xff0c;节日庆祝你还在傻傻的守点官宣吗&#xff1f;还有你关注的那个他&#xff08;她&#xff09;&#xff0c;他&#xff08;她&#xff09;发的朋友圈你想成为第一个点赞评论的人吗&#xff1f;想和他进行更多的交…

如何自动获取短信验证码?

点击下方关注我&#xff0c;然后右上角点击...“设为星标”&#xff0c;就能第一时间收到更新推送啦~~~ 这篇文章通过解决实际项目开发中遇到的如何自动获取短信验证码的问题&#xff0c;进一步讲述在Java中如何使用正则。 Java中如何使用正则 Java中正则相关类位于java.util.r…

python pytesseract 中文文字批量识别

用pytesseract 来批量把图片转成文字 1、安装好 pytesseract 包 2、下载安装OCR https://download.csdn.net/download/m0_37622302/88348824https://download.csdn.net/download/m0_37622302/88348824 Index of /tesseracthttps://digi.bib.uni-mannheim.de/tesseract/ 我是…

DevOps与CI/CD常见面试问题汇总

01 您能告诉我们DevOps和Agile(敏捷)之间的根本区别吗&#xff1f; 答&#xff1a;尽管DevOps与敏捷方法&#xff08;这是最流行的SDLC[Software Development Life Cycle]方法之一&#xff09;有一些相似之处&#xff0c;但两者在软件开发方面都是根本不同的方法。以下是两者之…

SpringCloud Gateway--网关服务基本介绍和基本原理

&#x1f600;前言 本篇博文是关于SpringCloud Gateway的基本介绍&#xff0c;希望你能够喜欢 &#x1f3e0;个人主页&#xff1a;晨犀主页 &#x1f9d1;个人简介&#xff1a;大家好&#xff0c;我是晨犀&#xff0c;希望我的文章可以帮助到大家&#xff0c;您的满意是我的动力…