【C++杂货铺】探索stack和queue的底层实现

在这里插入图片描述

文章目录

  • 一、stack的介绍和使用
    • 1.1 stack的介绍
    • 1.2 stack的使用
      • 1.2.1 最小栈
      • 1.2.2 栈的压入、弹出序列
      • 1.2.3 逆波兰表达式求值
      • 1.2.4 用栈实现队列
  • 二、queue的介绍和使用
    • 2.1 queue的介绍
    • 2.2 queue的使用
      • 2.2.1 二叉树的层序遍历
  • 三、模拟实现
    • 3.1 stack模拟实现
    • 3.2 queue模拟实现
  • 四、容器适配器
    • 4.1 什么是适配器?
    • 4.2 STL标准库中stack和queue的底层结构
    • 4.3 deque的简单介绍
      • 4.3.1 deque的原理介绍
      • 4.3.2 deque的缺陷
    • 4.4 为什么选择deque作为stack和queue的底层默认容器?
  • 五、结语

一、stack的介绍和使用

1.1 stack的介绍

  • stack 是一种容器适配器,专门用在具有后进先出的上下文环境中。只能从容器的一端进行元素的插入与提取操作。

  • stack 是作为容器适配器被实现的,容器适配器即是对特定类封装作为其底层的容器,并提供一组特定的成员函数来访问其元素,使得元素在特定容器的尾部(栈顶)被压入和弹出。

  • stack 的底层容器可以使任何标准的容器类模板或者一些其它特定的容器类,这些容器类应该支持以下操作:

    • empty:判空操作

    • back:获取尾部元素操作

    • push_back:尾部插入元素操作

    • pop_back:尾部删除元素操作

  • 标准容器 vector、deque、list 均符合这些需求,默认情况下,如果没有为 stack 指定特定的底层容器,默认情况下使用 deque。

在这里插入图片描述

1.2 stack的使用

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

1.2.1 最小栈

在这里插入图片描述
本题的思路是用两个栈来实现,其中一个栈 _st 用来正常存储数据,另一个栈 _minst 用来存储最小的数据。具体实现就是在往 _st 中插入数据的时候进行判断,如果当前插入的数据 val 小于等于 _minst 栈顶的数据,那就将 val 也插入到 _minst 这个栈中。否则直将数据插入 _st 中。在 pop 数据的时候,先取 _st 的栈顶元素和 _minst 的栈顶元素进行比较,如果二者相等,那就同时 pop _st_minst 的栈顶元素,否则就值 pop _st 的栈顶元素。要获取堆栈中的最小元素直接返回 _minst 的栈顶元素即可。

class MinStack 
{
public:MinStack() {}void push(int val) {_st.push(val);if(_minst.empty() || val <= _minst.top()){_minst.push(val);}}void pop() {if(_st.top() == _minst.top()){_minst.pop();}_st.pop();}int top() {return _st.top();}int getMin() {return _minst.top();}
private:stack<int> _st;stack<int> _minst;
};

1.2.2 栈的压入、弹出序列

在这里插入图片描述
本题的解题思路是用一个栈来模拟。即先定义一个栈 st 然后给栈中入一个数据,接着取栈顶的数据和出栈序列 popV 当前位置元素进行比较进行比较,如果不相等则继续从入栈序列 pushV 中拿数据往栈 st 中入,如果相等就出栈。这里需要注意,有可能需要连续多次出栈。直到最终将入栈序列 pushV 中的数据全入栈,最后判断栈 st 是否为空,如果为空,就说明该出栈序列正确。如果不空就说明该出栈序列有问题。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;size_t push_pos = 0, pop_pos = 0;while(push_pos < pushV.size()){//先入一个元素st.push(pushV[push_pos++]);if(st.top() != popV[pop_pos]){//不匹配继续入数据continue;}while(!st.empty() && st.top() == popV[pop_pos]){//匹配,出数据st.pop();pop_pos++;}}return st.empty();}
};

代码优化:我们可以发现上面代码中不匹配逻辑里面其实啥也没干,因此我们可以把这段代码给删掉,上面加上是为了使逻辑更加清晰。

class Solution {
public:/*** 代码中的类名、方法名、参数名已经指定,请勿修改,直接返回方法规定的值即可** * @param pushV int整型vector * @param popV int整型vector * @return bool布尔型*/bool IsPopOrder(vector<int>& pushV, vector<int>& popV) {// write code herestack<int> st;size_t push_pos = 0, pop_pos = 0;while(push_pos < pushV.size()){//先入一个元素st.push(pushV[push_pos++]);while(!st.empty() && st.top() == popV[pop_pos]){//匹配,出数据st.pop();pop_pos++;}}return st.empty();}
};

1.2.3 逆波兰表达式求值

在这里插入图片描述
逆波兰表达式也被叫做后缀表达式。什么是后缀表达式呢?先来了解一下中缀表达式,中缀表达式就是我们平时最常见的,例如: 2 + 3 ∗ 1 2+3*1 2+31,就是一个典型的中缀表达式。将前面的中缀表达式变成后缀表达式得到:2 1 3 * +,这就是一个后缀表达式,后缀表达式相较于中中缀表达式,操作数顺序不变,操作符按优先级重排。这道题目就是要求我们对后缀表达式进行求解。求解后缀表达式,我们可以借助一个栈,遇到操作数入栈,遇到操作符从栈中出两个元素进行运算,将运算结果继续入栈。最终栈顶的元素就是整个逆波兰表达式的结果。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;size_t pos = 0;while(pos < tokens.size()){if(tokens[pos] != "+" && tokens[pos] != "-" && tokens[pos] != "*" && tokens[pos] != "/"){//如果是数字就入栈int num = stoi(tokens[pos]);st.push(num);}else{//不是数字就从栈中取两个元素出来int val1 = st.top();st.pop();int val2 = st.top();st.pop();int ret = 0;if(tokens[pos] == "+"){ret = val2 + val1;}else if(tokens[pos] == "-"){ret = val2 - val1;}else if(tokens[pos] == "*"){ret = val2 * val1;}else if(tokens[pos] == "/"){ret = val2 / val1;}//将计算结果继续入栈st.push(ret);}pos++;}return st.top();}
};

注意:在写上面这段代码的时候有下面几点需要特别注意,首先这是一个 string 数组,会涉及到 stringint 。其次需要注意在从栈中取数的时候,第一次取出的是右操作数,第二次取出的是左操作数,因此 val2 应该做左操作数,val1 应该做右操作数,尤其是减法运算和除法运算,这两个操作数的顺序必须得到保证。

补充:这里补充一个小知识点:如何将中缀表达式转换成后缀表达式。主要过程分为以下几步:

  1. 遇到操作数就输出(这里的输出是将其存储到某种容器里)。

  2. 遇到操作符,根据优先级的顺序分为以下两种情况:

    • 栈为空或当前操作符比栈顶的优先级高,继续入栈。

    • 栈不为空且当前操作符比栈顶的优先级低或者相等,则输出栈顶操作符,继续执行第二步。

  3. 中缀表达式结束后,依次出栈里面的操作符。

小Tips:当前操作符能否计算取决于后一个操作符的优先级是否高于自己,所以每当我们遇到一个操作符的时候,先不着急将它入栈,先和栈顶的操作符进行优先级比较,如果当前操作符的优先级比栈顶操作符的优先级低或者相等,我们就可以取出栈顶这个操作符进行运算。如果遇到括号可以走一个递归。其次就是需要想办法确定符号的优先级。

1.2.4 用栈实现队列

在这里插入图片描述
将一个栈当做输入栈,用于压入 push 传入的数据,另一个栈当做输出栈,用于 pop 和 peek 操作。每次 pop 或 peek 时,若输出栈为空则将输入栈的全部数据依次弹并压入输出栈,这样输出栈从栈顶往栈底的顺序就是队列从队首往队尾的顺序。

class MyQueue {
public:MyQueue() {}void push(int x) {input_st.push(x);}int pop() {if(output_st.empty()){while(!input_st.empty()){output_st.push(input_st.top());input_st.pop();} }int ret = output_st.top();output_st.pop();return ret;}int peek() {if(output_st.empty()){while(!input_st.empty()){output_st.push(input_st.top());input_st.pop();}}return output_st.top();}bool empty() {return input_st.empty() && output_st.empty();}
private:stack<int> input_st;stack<int> output_st;
};

二、queue的介绍和使用

2.1 queue的介绍

  • 队列是一种容器适配器,专门用于在FIFO上下文中执行先进先出操作,其中从容器的一端插入元素,另一端提取元素。

  • 队列作为容器适配器实现,容器适配器即将特定的容器类封装最为其底层容器,queue 提供一组特定的成员函数来访问其元素。元素从队尾入队列,从对头出队列。

  • 底层容器可以是标准容器模板之一,也可以是其他专门设计的容器类。该底层容器应至少支持以下操作:

    • empty:检查队列是否为空

    • size:返回队列中有效元素的个数

    • front:返回对头元素的引用

    • back:返回队尾元素的引用

    • push_back:在队列尾部入队列

    • pop_front:在队列头部出队列

  • 标准容器类 deque 和 list 满足了这些要求。默认情况下,如果没有为 queue 实例化指定容器类,则使用标准容器 deque。

在这里插入图片描述

2.2 queue的使用

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

2.2.1 二叉树的层序遍历

在这里插入图片描述
二叉树的层序遍历可以借助队列来实现,从根节点开始,先让父节点入队列,在出队尾节点的同时,将该节点的左孩子和右孩子依次入队列。直到队列为空,从队列中出出来的结果就是层序遍历的结果。这道题目需要将同一层的所有节点都存入一个一维数组,再将这些一维数组组合成一个二维数组返回。我们前面的这种做法会导致队列中出现两层节点混在意的情况,因此我们可以定义一个变量 levelSize 来记录每一层的节点数。具体代码如下:

class Solution 
{
public:vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> retV;queue<TreeNode*> qu;int levelSize = 0;qu.push(root);while(!qu.empty()){vector<int> tmp;levelSize = qu.size();while(levelSize != 0){TreeNode* top = qu.front();if(top != nullptr){tmp.push_back(top->val);qu.push(top->left);qu.push(top->right);} qu.pop();levelSize--;}if(!tmp.empty()){retV.push_back(tmp);}}return retV;}
};

三、模拟实现

3.1 stack模拟实现

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

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

3.2 queue模拟实现

template<class T, class Continer = std::list<T>>
class queue
{
public:queue(){}void push(const T& val){_con.push_back(val);}void pop(){_con.pop_front();//这里不再支持vector}T& front(){return _con.front();}T& back(){return _con.back();}size_t size(){return _con.size();}bool empty(){return _con.empty();}
private:Continer _con;
};

小Tips:栈不能借助 vector 来实现,因为出队列,相当于删除 vector 中的第一个元素,而对 vector 头删会涉及挪动数据,效率相较于 list 会有所下降。

四、容器适配器

4.1 什么是适配器?

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

4.2 STL标准库中stack和queue的底层结构

虽然 stack 和 queue 中也可以存放元素,但在 STL 中并没有将其划分在容器行列,而是将其称为容器适配器,这是因为 stack 和 queue 只是对其他容器的接口进行了包装,STL 中 stack 和 queue 默认使用 deque。

4.3 deque的简单介绍

4.3.1 deque的原理介绍

deque(双端队列)是一种双开口的“连续”空间的数据结构,双开口的含义是:可以在头尾两端进行插入和删除操作,且时间复杂度为O(1),与 vector 比较,头插效率高,不需要搬移元素;与 list 比较,空间利用率比较高。
在这里插入图片描述
deque并不是真正连续的空间,而是由一段段连续的小空间拼接而成的,实际 deque 类似于一个动态的二维数组,其底层结构如下图所示:
在这里插入图片描述
双端队列底层是一段假象的连续空间,实际是分段连续的,为了维护其“整体连续”以及随机访问的假象,落在了 deque 的迭代器身上,因此 deque 的迭代器设计的就比较复杂,如下图所示:
在这里插入图片描述
在这里插入图片描述

4.3.2 deque的缺陷

  • 与 vector 比较,deque 的优势是:头部插入和删除时,不需要搬移元素,效率特别高,而且在扩容时,也不需要搬移大量的元素,因此其效率是比 vector 高的。

  • 与 list 比较,其底层空间是连续的,空间利用率比较高,不需要存储额外字段。

  • 但是,deque 有一个致命缺陷:不适合遍历,因为在遍历时,deque 的迭代器要频繁的去检测其是否移动到某段小空间的边界,导致效率低下,而序列式场景中,可能需要经常遍历,因此在实际中,需要线性结构式,大多数情况下优先考虑 vector 和 list,deque 的应用并不多,而目前能看到的一个应用场景就是,STL 用其作为 stack 和 queue 的底层数据结构。

4.4 为什么选择deque作为stack和queue的底层默认容器?

stack 是一种后进先出的特殊线性数据结构,因此只要是具有 push_back() 和 pop_back() 操作的线性结构,都可以作为 stack 的底层容器,比如 vector 和 list 都可以;queue 是先进先出的特殊线性数据结构,只要具有 push_back() 和 pop_front() 操作的线性结构,都可以作为 queue de 底层容器,比如 list。但是 STL 中对 stack 和 queue 默认选择 deque 作为其底层容器,主要是因为:

  • stack 和 queue 不需要遍历(因此 stack 和 queue 没有迭代器),只需要在固定的一端或者两端进行操作。

  • 在 stack 中元素增长时,deque 比 vector 的效率高(扩容时不需要搬移大量数据);queue 中的元素增长时,deque 不仅效率高,而且内存利用率高。

五、结语

今天的分享到这里就结束啦!如果觉得文章还不错的话,可以三连支持一下,春人的主页还有很多有趣的文章,欢迎小伙伴们前去点评,您的支持就是春人前进的动力!

在这里插入图片描述

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

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

相关文章

Spine2D骨骼动画播放器 - 微信小程序版

Spine2D骨骼动画播放器 - 微信小程序版 简介平台支持 界面预览使用说明演示视频 版本笨笨的小目标&#xff08;废话&#xff09;参考资料测试文件百度盘分享 相关文档 简介 本播放器是SpinePlayer的微信小程序版。由于官方并没有提供现成的运行库&#xff0c;只能自己改造。 设…

Jobs Portal求职招聘系统源码v3.5版本

Jobs Portal求职招聘系统 是为求职者和公司发布职位而开发的交互式求职招聘源码。它使求职者能够发布简历、搜索工作、查看个人工作列表。 它将提供各种公司在网站上放置他们的职位空缺资料&#xff0c;并且还可以选择搜索候选人简历。 除此之外&#xff0c;还有一个管理模块供…

JAVASE---抽象类和接口

抽象类 抽象类的概念 在面向对象的概念中&#xff0c;所有的对象都是通过类来描绘的&#xff0c;但是反过来&#xff0c;并不是所有的类都是用来描绘对象的&#xff0c;如果一个类中没有包含足够的信息来描绘一个具体的对象&#xff0c;这样的类就是抽象类。 抽象类语法 在…

振弦采集仪应用地铁隧道安全监测详细解决方案

振弦采集仪应用地铁隧道安全监测详细解决方案 随着城市化进程的不断加快&#xff0c;地铁作为一种高效、便捷、环保的交通方式已经成为现代城市不可或缺的一部分。因此&#xff0c;对地铁的安全性也越来越重视&#xff0c;一般二三线以上的城市在不断发展中&#xff0c;地铁做…

MIT的智慧,利用深度学习来解决了交通堵塞

导读大家都对交通阻塞深恶痛绝。除了让人头疼和错过约会之外&#xff0c;交通拥堵让美国的司机每年多花3000亿美元。 研究人员建议大家使用自动驾驶汽车&#xff0c;即使数量占比并不大&#xff0c;但也能大大改善交通拥堵情况。 Lex Fridman和他的MIT团队开发了一款模拟游戏来…

【大数据实训】用Hbase模拟电影搜索引擎(四)

博主介绍&#xff1a;✌全网粉丝6W,csdn特邀作者、博客专家、Java领域优质创作者,博客之星、掘金/华为云/阿里云/InfoQ等平台优质作者、专注于大数据技术领域和毕业项目实战✌ &#x1f345;文末获取项目联系&#x1f345; 《云计算与大数据处理》课程大作业评分表 项目考核内…

centos 端口被占用的快速排查方式

问题笔记 centos 端口被占用的快速排查方式 centos 端口被占用的快速排查方式 这里说一个我刚刚遇到的问题&#xff0c;解决步骤用来记录&#xff0c;方便以后自己查询。 nginx配置完index.html测试文件&#xff0c;发现一直显示的404页面。 我跑到服务器上想重启一下nginx …

使用Maven创建父子工程

&#x1f4da;目录 创建父工程创建子模块创建子模块示例创建认证模块(auth) 结束 创建父工程 选择空项目&#xff1a; 设置&#xff1a;项目名称&#xff0c;组件名称&#xff0c;版本号等 创建完成后的工程 因为我们需要设置这个工程为父工程所以不需要src下的所有文件 在pom…

认识JVM的内存模型

从上一节了解到整个JVM大的内存区域&#xff0c;分为线程共享的heap&#xff08;堆&#xff09;&#xff0c;MethodArea&#xff08;方法区&#xff09;&#xff0c;和线程独享的 The pc Register&#xff08;程序计数器&#xff09;、Java Virtual Machine Stacks&#xff08;…

编程语言排行榜

以下是2023年的编程语言排行榜&#xff08;按照流行度排序&#xff09;&#xff1a; Python&#xff1a;Python一直以来都是非常受欢迎的编程语言&#xff0c;它简洁、易读且功能强大。在数据科学、机器学习、人工智能等领域有广泛应用。 JavaScript&#xff1a;作为前端开发…

Lua03——开发环境搭建

1 安装开发插件 在 idea 或 vscode 中安装 lua 的开发插件 EmmyLua 2 创建工程 在 idea 中创建一个新的工程 工程的类型选择 lua 输入工程名及目标目录 在工程结构的SDK中设置lua在本地安装目录 在工程结构的modules中选择 lua 3 编写第一个lua程序 在工程下添加程序包&#…

Redis总结(一)

目录 Redis简介 为什么使用Redis作为MySQL的缓存&#xff1f; 高性能 高并发 Redis数据结构及其使用场景分别是什么&#xff1f; String&#xff08;字符串&#xff09; 内部实现 常用命令 普通字符串基本操作 批量设置 计数器&#xff08;字符串内容为整数时使用&a…

[学习笔记]Node2Vec图神经网络论文精读

参考资料&#xff1a;https://www.bilibili.com/video/BV1BS4y1E7tf/?p12&spm_id_frompageDriver Node2vec简述 DeepWalk的缺点 用完全随机游走&#xff0c;训练节点嵌入向量&#xff0c;仅能反应相邻节点的社群相似信息&#xff0c;无法反映节点的功能角色相似信息。 …

集创北方ICN6202 MIPIDSI转LVDS转换芯片

集创北方ICN6202 1.描述&#xff1a; ICN6201是一个接收MIPIDSI输入和发送LVDS输出的桥接芯片。MIPIDSI最多支持4个车道&#xff0c;每个车道的最大运行频率为1Gbps&#xff1b;总最大输入带宽为4Gbps&#xff1b;并且还支持MIPI定义的ULPS&#xff08;超低功耗状态&#xff…

c++通过tensorRT调用模型进行推理

模型来源&#xff1a; 算法工程师训练得到的onnx模型 c对模型的转换&#xff1a; 拿到onnx模型后&#xff0c;通过tensorRT将onnx模型转换为对应的engine模型&#xff0c;注意&#xff1a;训练用的tensorRT版本和c调用的tensorRT版本必须一致。 如何转换&#xff1a; 算法工…

机器人制作开源方案 | 桌面级机械臂--应用设计

本节内容将基于机器视觉带着大家进行应用实训。机器视觉是人工智能正在快速发展的一个分支&#xff0c;简单说来机器视觉就是用机器代替人眼来做测量和判断。机器视觉系统是通过机器视觉产品&#xff08;即图像摄取装置&#xff0c;分CMOS和CCD两种&#xff09;将被摄取目标转换…

Android学习之路(14) Context详解

一. 简介 在 Android 开发中、亦或是面试中都离不开四大组件的身影&#xff0c;而在创建或启动这些组件时&#xff0c;并不能直接通过 new 关键字后跟类名来创建实例对象&#xff0c;而是需要有它们各自的上下文环境&#xff0c;也就是本篇文章要讨论的 Context。 1.1 Contex…

ComPtr源码分析

ComPtr源码分析 ComPtr是微软提供的用来管理COM组件的智能指针。DirectX的API是由一系列的COM组件来管理的&#xff0c;形如ID3D12Device&#xff0c;IDXGISwapChain等的接口类最终都继承自IUnknown接口类&#xff0c;这个接口类包含AddRef和Release两个方法&#xff0c;分别用…

Qt6中使用Qt Charts

官方文档&#xff1a;Qt Charts 6.5.2 如果你是使用 CMake 构建的&#xff0c;则应在 CMakeLists.txt 中添加如下两行代码&#xff1a; find_package(Qt6 REQUIRED COMPONENTS Charts)target_link_libraries(mytarget PRIVATE Qt6::Charts) 其中 mytarget 为你的项目名称。一共…

aardio语言的通用数据表维护

import win.ui; /*DSG{{*/ var winform win.form(text"通用数据表维护";right617;bottom427;bgcolor15780518) winform.add( buttonAdd{cls"button";text"增加空行";left469;top40;right564;bottom80;flat1;z2}; buttonDel{cls"button&quo…