【C++从0到王者】第十六站:stack和queue的使用

文章目录

  • 一、stack的使用
    • 1.stack的介绍
    • 2.stack的使用
  • 二、queue的使用
    • 1.queue的护额晒
    • 2.queue的使用
  • 三、stack和queue相关算法题
    • 1.最小栈
    • 2.栈的压入、弹出序列
    • 3.逆波兰表达式
    • 4.两个栈实现一个队列
    • 5.用两个队列实现栈
    • 6.二叉树的层序遍历
      • 1.双队列
      • 2.用一个变量levelSize去控制
    • 7.二叉树的层序遍历Ⅱ

一、stack的使用

1.stack的介绍

在这里插入图片描述

栈是一种容器适配器,专门设计用于在 LIFO 上下文中操作(后进先出),其中元素只从容器的一端插入和提取。

栈被实现为容器适配器,这些类使用特定容器类的封装对象作为其底层容器,提供一组特定的成员函数来访问其元素。 元素从特定容器的“后端”被推入/弹出,这被称为栈的顶部。

底层容器可以是任何标准的容器类模板,也可以是其他一些专门设计的容器类。容器应该支持以下操作:empty、size、back、push_back、pop_front

标准容器类 vector、deque 和 list 满足这些要求。默认情况下,如果没有为特定的堆栈类实例化指定容器类,则使用标准容器 deque。

这里我们需要知道的是,Container适配器就是一个现有的容器进行的一个转换
也就是说,适配器的本质就是一种复用

2.stack的使用

我们先看stack的接口有哪些
在这里插入图片描述

如上所示,这里其实我们一看就已经猜出了七七八八了。因为与前面是string、vector、list是十分相似的。只要结合它的先进先出的特性,我们就知道每个函数都是什么意思了。

对于stack的使用是非常简单的

void test_stack()
{stack<int> st1;st1.push(1);st1.push(2);st1.push(3);st1.push(4);while (!st1.empty()){cout << st1.top() << " ";st1.pop();}cout << endl;
}

在这里插入图片描述

二、queue的使用

1.queue的护额晒

在这里插入图片描述

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

队列是作为容器适配器实现的,容器适配器是使用特定容器类的封装对象作为其底层容器的类,提供一组特定的成员函数来访问其元素。元素被推入特定容器的“后面”,并从其“前面”弹出。

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

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

2.queue的使用

同样的,我们先来看queue的接口有哪些
在这里插入图片描述

在这些接口中,和stack是类似的,只要我们知道了queue的特性是先进先出。我们就能很轻松的推测出每个接口的意思

对于queue的使用是很简单的

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;
}

在这里插入图片描述

三、stack和queue相关算法题

1.最小栈

题目链接:最小栈

题目解析:在这道题中,我们为了模拟这种情况,我们可以在成员变量中定义两个栈,一个栈作为正常的出入数据使用,一个栈用来存储最小值。
首先是构造函数,由于我们的成员变量都是自定义类型,所以会自动调用他们的默认构造函数,即他们也会走初始化列表,所以默认构造函数我们是可以直接不用管的。甚至于我们可以直接删掉题目给的构造函数,因为我们不写,编译器自己生成一个。
其次我们的大逻辑是这样的,当我们最小栈为空的时候,我们的最小栈是需要入一个数据的,当我们将要插入的元素是小于等于最小栈要插入的元素的时候,我们会将这个元素给入最小栈
当我们pop的时候,我们也是同理的,如果我们要删除的数据等于最小栈的栈顶元素,那么就也要删除最小栈的栈顶元素。

class MinStack {
public:MinStack(){}void push(int val) {st.push(val);if(min.empty()||(val<=min.top())){min.push(val);}}void pop() {int val=st.top();st.pop();if(val==min.top()){min.pop();}}int top() {return st.top();}int getMin() {return min.top();}
private:stack<int> st;stack<int> min;
};/*** Your MinStack object will be instantiated and called as such:* MinStack* obj = new MinStack();* obj->push(val);* obj->pop();* int param_3 = obj->top();* int param_4 = obj->getMin();*/

2.栈的压入、弹出序列

题目链接:栈的压入弹出序列

题目解析:我们可以使用一个栈来模拟它的入栈出栈逻辑,只要顺着它的思路最终我们的这个栈是空栈的话,那么就说明是匹配的,否则不匹配

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;int n=pushV.size();int j=0;for(int i=0;i<n;i++){st.push(pushV[i]);while(!st.empty() && st.top()==popV[j]){st.pop();j++;}            }return st.empty();}
};

3.逆波兰表达式

题目链接:逆波兰表达式

再谈这道题之前,我们应该先知道什么是逆波兰表达式,我们正常的都是中缀表达式,即3+2*5这种的,都被称之为中缀表达式。

而中缀表达式在计算机中是很难进行运算的。我们需要先将其转换为后缀表达式,前文所说的中缀表达式转化为后缀表达式后应该为3 2 5 * +。后缀表达式的特点就是操作数的顺序不变,而操作符的顺序按照优先级进行了重排。

我们先来看一下后缀运算符是如何进行运算的:

  1. 操作数入栈
  2. 如果是操作符,取出栈顶的两个元素进行计算,计算结果放入栈中

在这里插入图片描述

那么如何使得中缀转为后缀呢?

  1. 操作数输出(即将操作数放到一个容器中)
  2. 操作符入栈 : ①栈为空,当前操作符比栈顶的优先级高,继续入栈 ②栈不为空,且当前操作符比栈顶的优先级低或者相等,则输出栈顶操作符(因为运算符的优先级只与它相邻的操作符有关,是相对的,如果后面出现了一个更高的操作符,我们无法确定后面是否还有更高的操作符,反而是如果有一个相对较低的操作符,那么前两个肯定是可以进行运算的)
  3. 表达式结束后,依次出栈顶的操作符
  4. 注意,有可能会在转换的中间出现连续出操作符的情况,即栈里面已经存储了好几个运算符了,下面的一个运算符要比好几个都要低,就要连续出好几个运算符

比如说2+4-1*3,这个中缀表达式,按照上面的规则可以化为
在这里插入图片描述

上面都是正常情况的下的处理,但是还有时候会出现括号的影响。

这里可以考虑加上一个特殊标记,当我们这个标记生效时,就代表进入括号内了。或者在这里走一个递归也是可以的。递归的方法就是在遇到括号的时候,我们将括号里面的运算符就需要放入一个新的栈中了。相当于我们只需要让括号返回一个结果就可以了。但是数据还是输出在原来的顺序表中的

我们在回过头来看这道题,我们有了上面的分析,就很容易写出下面代码了。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for(auto& str : tokens){if(str=="+"||str=="-"||str=="*"||str=="/"){int right=st.top();st.pop();int left=st.top();st.pop();switch(str[0]){case '+':st.push(left+right);break;case '-':st.push(left-right);break;case '*':st.push(left*right);break;case '/':st.push(left/right);break;}}else{st.push(stoi(str));}}return st.top();}
};

4.两个栈实现一个队列

题目链接:两个栈实现一个队列

对于这个题,我们在之前也已经做过一次分析了,只不过上一次是用C语言手撕了一个栈来实现了。而现在呢,我们有C++的库了,因此我们就可以直接使用C++的库来完成这件事。

class MyQueue {
public:MyQueue() {}void push(int x) {_push.push(x);}int pop() {if(_pop.empty()){while(!_push.empty()){int val=_push.top();_push.pop();_pop.push(val);}}int val=_pop.top();_pop.pop();return val;}int peek() {if(_pop.empty()){while(!_push.empty()){int val=_push.top();_push.pop();_pop.push(val);}}return _pop.top();}bool empty() {return (_push.empty()&&_pop.empty());}
private:stack<int> _push;stack<int> _pop;
};/*** Your MyQueue object will be instantiated and called as such:* MyQueue* obj = new MyQueue();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->peek();* bool param_4 = obj->empty();*/

5.用两个队列实现栈

题目链接:用两个队列实现栈

这道题与上面的题类似,我们也是曾经使用C语言做过,不过由于C语言没有轮子,就需要我们自己造轮子,有了很多的麻烦。

class MyStack {
public:MyStack() {}void push(int x) {if(q1.empty()){q2.push(x);}else{q1.push(x);}}int pop() {if(q1.empty()){while(q2.size()>1){int val=q2.front();q2.pop();q1.push(val);}int val=q2.front();q2.pop();return val;}else{while(q1.size()>1){int val=q1.front();q1.pop();q2.push(val);}int val=q1.front();q1.pop();return val;}}int top() {if(q1.empty()){return q2.back();}else{return q1.back();}}bool empty() {return (q1.empty()&&q2.empty());}
private:queue<int> q1;queue<int> q2;
};/*** Your MyStack object will be instantiated and called as such:* MyStack* obj = new MyStack();* obj->push(x);* int param_2 = obj->pop();* int param_3 = obj->top();* bool param_4 = obj->empty();*/

6.二叉树的层序遍历

题目链接:二叉树的层序遍历

对于这道题,如果不是用C++来完成的话,用C去完成的话是非常难的。不仅我们要确保我们造的轮子是正确的,而且还有很多细节需要进行处理,但我们如果使用C++的话可以极大的简化很多操作

1.双队列

我们可以使用两个队列去完成这件事,一个队列用来存储结点指针,一个队列用来存储该节点处于哪个层。这样我们就可以知道哪个结点是那个层的了,自然我们就很容易的得知层序遍历了。

2.用一个变量levelSize去控制

这种思路是比较奇妙的,我们使用一个变量来确定当前该层有多少个结点,用一个队列来存储结点,然后就是层序遍历的基本套路,每出一个结点,带来两个孩子。将每一层的数据存储在一个vector中,然后一层结束后将这一层的vector插入到vector<vector<int>>中。

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrder(TreeNode* root) {queue<TreeNode*> q;int levelSize=0;if(root){q.push(root);levelSize=1;}vector<vector<int>> vv;while(!q.empty()){vector<int> v;for(int i=0;i<levelSize;i++){TreeNode* front=q.front();q.pop();v.push_back(front->val);if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}vv.push_back(v);levelSize=q.size();}return vv;}
};

7.二叉树的层序遍历Ⅱ

题目链接:二叉树的层序遍历Ⅱ

对于这道题目,我们可以注意到他是让倒着遍历的。和前一道题基本是一样的,只是改变了vv的顺序。即相当于将vv给逆序。那么这道题就太简单了,直接将前面这道题给拷贝过来,然后调用库里面的reverse即可

/*** Definition for a binary tree node.* struct TreeNode {*     int val;*     TreeNode *left;*     TreeNode *right;*     TreeNode() : val(0), left(nullptr), right(nullptr) {}*     TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}*     TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}* };*/
class Solution {
public:vector<vector<int>> levelOrderBottom(TreeNode* root) {queue<TreeNode*> q;int levelSize=0;if(root){q.push(root);levelSize=1;}vector<vector<int>> vv;while(!q.empty()){vector<int> v;for(int i=0;i<levelSize;i++){TreeNode* front=q.front();q.pop();v.push_back(front->val);if(front->left){q.push(front->left);}if(front->right){q.push(front->right);}}vv.push_back(v);levelSize=q.size();}reverse(vv.begin(),vv.end());return vv;}
};

好了,本期内容就到这里了
如果对你有帮助的话,不要忘记点赞加收藏哦!!!

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

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

相关文章

K8S系列文章 之 编写自动化部署K8S脚本

介绍 通过ansible脚本shell实现自动化部署k8s基础集群(v1.25.0) 部署结构 1. 通过二进制部署包镜像安装k8s集群、目录etcd节点只支持1-3个节点、最多三个etcd节点 2. 因k8s版本相对较新、需要升级内核来支持后台程序、当前版本只支持Cento7&#xff0c;内核版本(5.19.4-1.el7…

ffmpeg+nginx实现rtsp协议摄像头web端播放

ffmpegnginx实现rtsp协议摄像头web端播放 环境准备准备nginx环境添加rtmp模块添加hls转发 使用ffmpeg&#xff0c;将摄像头rtsp转为rtmp并推送到nginxVLC播放验证 环境准备 nginx&#xff08;需要安装rtmp模块&#xff09;ffmpeg 6.0vlc播放器&#xff08;本地播放验证&#x…

大数据课程H2——TELECOM的电信流量项目实现

文章作者邮箱&#xff1a;yugongshiyesina.cn 地址&#xff1a;广东惠州 ▲ 本章节目的 ⚪ 了解TELECOM项目的数据收集&#xff1b; ⚪ 了解TELECOM项目的数据清洗&#xff1b; ⚪ 了解TELECOM项目的数据导出&#xff1b; ⚪ 了解TELECOM项目的数据可视化&…

观察者模式(C++)

定义 定义对象间的一种一对多(变化)的依赖关系&#xff0c;以便当一个对象(Subject)的状态发生改变时&#xff0c;所有依赖于它的对象都得到通知并自动更新。 ——《设计模式》GoF 使用场景 一个对象&#xff08;目标对象&#xff09;的状态发生改变&#xff0c;所有的依赖对…

SpringBoot第33讲:SpringBoot集成ShardingJDBC - 基于JPA的读写分离

SpringBoot第33讲&#xff1a;SpringBoot集成ShardingJDBC - 基于JPA的读写分离 本文是SpringBoot第33讲&#xff0c;主要介绍分表分库&#xff0c;以及SpringBoot集成基于 ShardingJDBC 的读写分离实践 文章目录 SpringBoot第33讲&#xff1a;SpringBoot集成ShardingJDBC - 基…

uni-app:实现点击按钮出现底部弹窗(uni.showActionSheet+自定义)

一、通过uni.showActionSheet实现底部选择 效果 代码 <template><view><button click"showActionsheet">点击打开弹窗</button></view> </template><script> export default {methods: {showActionsheet() {uni.showAct…

消息队列项目(2)

我们使用 SQLite 来进行对 Exchange, Queue, Binding 的硬盘保存 对 Message 就保存在硬盘的文本中 SQLite 封装 这里是在 application.yaml 中来引进对 SQLite 的封装 spring:datasource:url: jdbc:sqlite:./data/meta.dbusername:password:driver-class-name: org.sqlite.…

Python 中的机器学习简介:多项式回归

一、说明 多项式回归可以识别自变量和因变量之间的非线性关系。本文是关于回归、梯度下降和 MSE 系列文章的第三篇。前面的文章介绍了简单线性回归、回归的正态方程和多元线性回归。 二、多项式回归 多项式回归用于最适合曲线拟合的复杂数据。它可以被视为多元线性回归的子集。…

APP外包开发的学习流程

学习iOS App的开发是一项有趣和富有挑战性的任务&#xff0c;是一个不断学习和不断进步的过程。掌握基础知识后&#xff0c;不断实践和尝试新的项目将使您的技能不断提升。下面和大家分享一些建议&#xff0c;可以帮助您开始学习iOS App的开发。北京木奇移动技术有限公司&#…

DAY02_Spring—第三方资源配置管理Spring容器Spring注解开发Spring整合Mybatis和Junit

目录 一 第三方资源配置管理1 管理DataSource连接池对象问题导入1.1 管理Druid连接池1.2 管理c3p0连接池 2 加载properties属性文件问题导入2.1 基本用法2.2 配置不加载系统属性2.3 加载properties文件写法 二 Spring容器1 Spring核心容器介绍问题导入1.1 创建容器1.2 获取bean…

软件架构师思维塑造

一、软件系统设计的六项原则 1、单一职责原则&#xff08;Single Responsibility Principle&#xff09; 2、开闭原则&#xff08;Open Closed Principle&#xff09; 3、里氏替换原则&#xff08;Liskov Substitution Principle&#xff09; 4、迪米特法则&#xff08;Law of …

微服务 云原生:基于 Gogs + Drone 进行项目 CI/CD

传统构建部署 以一个简单的前后端项目来说&#xff0c;分别编写前后端的 Dockerfile 文件并构建镜像&#xff0c;然后编写 docker-compose.yml 构建部署&#xff0c;启动运行。 一个简单的例子&#xff1a; 前端&#xff1a; 项目名&#xff1a;kubemanagement-web技术栈&am…

Java中Date方法详解

先进行专栏介绍 本专栏是自己学Java的旅途&#xff0c;纯手敲的代码&#xff0c;自己跟着黑马课程学习的&#xff0c;并加入一些自己的理解&#xff0c;对代码和笔记 进行适当修改。希望能对大家能有所帮助&#xff0c;同时也是请大家对我进行监督&#xff0c;对我写的代码进行…

eeglab(自用)

目录 1.加载、显示数据 2.绘制脑电头皮图 3.绘制通道光谱图 4.预处理工具 5.ICA去除伪迹 5. 提取数据epoch 1.加载、显示数据 观察事件值(Event values)&#xff1a;该数据集中包含2400个事件&#xff0c;每个事件指定了EEG.event结构的字段Type(类型)、position(位置)和…

【Linux命令详解 | cat命令】Linux系统中用于显示或连接文件的命令

文章标题 简介一&#xff0c;参数列表二&#xff0c;使用介绍1. 显示文件内容2. 创建文件3. 连接文件4. 显示行号5. 压缩空行6. 显示特殊字符7. 显示行号和特殊字符8. 从标准输入读取9. 显示文件开头或结尾10. 备份文件11. 显示文件内容至多屏幕大小12. 转义正则表达式13. 显示…

java文件

一.File类 二.扫描指定目录&#xff0c;并找到名称中包含指定字符的所有普通文件&#xff08;不包含目录&#xff09;&#xff0c;并且后续询问用户是否要删除该文件 我的代码: import java.io.File; import java.io.IOException; import java.util.Scanner;public class Tes…

瑞芯微RK3568核心板-4G联网测试

​ &#x1f308;引言 RK3568是瑞芯微针对AIOT和工业市场推出的一款高性能、低功耗、功能丰富的应用处理器。它采用了四核ARM架构64位Cortex-A55处理器&#xff0c;主频高达2.0GHz&#xff0c;集成瑞芯微自研1TOPS算力NPU, 同时集成Mali-G52 2EE GPU&#xff0c;支持4K60fps …

React Native连接Zebra斑马打印机通过发送CPCL指令打印(Android 和 iOS通用)

自 2015 年发布以来&#xff0c;React Native 已成为用于构建数千个移动应用程序的流行跨平台移动开发框架之一。通常&#xff0c;我们有开发人员询问如何将 Link-OS SDK 与 React Native 应用程序集成&#xff0c;以便在 Zebra 打印机上打印标签。在本教程中&#xff0c;我们将…

深度学习常用的激活函数

深度学习的核心思想是通过多层次的神经网络结构&#xff0c;逐步抽取和表示数据中的高级特征&#xff0c;从而实现对复杂数据模式的学习和识别。 神经网络结构&#xff1a; 深度学习使用多层次的神经网络&#xff0c;包括输入层、隐藏层和输出层。这些网络结构允许模型自动学习…

一、Webpack相关(包括webpack-dev-server用以热更新和html-webpack-plugin)

概念与功能&#xff1a; webpack是前端项目工程化的具体解决方案。它提供了友好的前端模块化开发支持&#xff0c;以及代码压缩混淆、处理浏览器端JavaScript的兼容性、性能优化等强大的功能。 快速上手&#xff1a;隔行变色 -S实际是--save的简写&#xff0c;表示安装的第三方…