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

【C++】---Stack和Queue的用法及其模拟实现

文章目录

  • Stack
    • 最小栈
    • 栈的弹出压入序列
    • 逆波兰表达式求值
    • 用栈实现队列
    • 模拟实现
  • queue
    • 用队列实现栈
    • 模拟实现

Stack

stack是一种容器适配器,专门用在具有后进先出操作的上下文环境中,其删除只能从容器的一端进行元素的插入与提取操作。它的使用和之前学习的vector等容器类似,都具有插入、删除、判空功能,具体的实现就做几道OJ题来感受一下,也可以查看文档进行了解。

最小栈

image-20230213193037356

因为栈的性质是后进先出,所以可以利用这个性质。首先创建两个栈,一个用于压栈(s1),一个用于记录较小元素的栈(s2)。首先每一次压栈s1都会将元素保存,如果s2栈顶的元素比最近压栈的元素大或者当s2为空时,则s2将元素入栈。这样操作就能保持每一次s2里面最近一次进栈的元素都是以压栈元素中最小的元素,此时我们只需要每次取出s2栈顶的元素就是最小元素。如果s1进行出栈操作,那么如果s2的栈顶元素等于s1出栈的元素,那么s2也要进行出栈,这样才能保持住s2的栈顶元素是最小的。

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

栈的弹出压入序列

image-20230213194455821

这道题考验的就是我们对于后进先出性质的应用,首先一定得判断一下两个序列的长度是否一样,如果不一样那就肯定不对了。接着我们可以对入栈序列进行依次入栈,每一次入栈的元素都和出栈序列的元素比较,如果相等那么出栈序列的比较元素就往后一个,刚入栈的元素就出栈。这样依次反复循环如果栈里的元素全部出栈完并且此时出栈序列所有元素都比较完即为匹配成功。反之其他情况匹配失败

class Solution {
public:bool IsPopOrder(vector<int> pushV,vector<int> popV) {if(pushV.size() != popV.size())return false;//创建栈和记录两个序列的比较个数int out = 0;int in = 0;stack<int> s;//如果出栈序列比较完即推出训话while(out < popV.size()){//如果栈为空或者栈顶元素不等于出栈序列的比较元素则继续入栈while(s.empty() || s.top() != popV[out]){if(in < pushV.size())s.push(pushV[in++]);//如果全部元素都入栈但出栈序列没有比较完则匹配失败elsereturn false;}//如果栈顶元素等于出栈序列比较元素则出栈s.pop();++out;}return true;}
};

逆波兰表达式求值

image-20230213200705721

逆波兰表达式简单理解就是将运算符放到运算数的后面,因此这道题可以使用栈来完成。首先如果遇到数字就入栈,遇到运算符就不用入栈了,用两个变量来接受栈的两个元素进行运算之后再把结果入栈,这样每一次的运算结果都是栈顶元素,依次循环直至结束。此时栈顶的元素就是最后的运算结果。

class Solution {
public:int evalRPN(vector<string>& tokens) {stack<int> st;for (auto e : tokens) {if (e == "+" || e == "*" || e == "-" || e == "/") {int right = st.top();st.pop();int left = st.top();st.pop();switch (e[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(e));}return st.top();}
};

用栈实现队列

image-20230213203053798

这道题如果用C语言写就十分的不方便,什么都得自己造。但是用C++有了STL之后就十分的轻松。思路很简单,用两个栈实现队列的先进先出性质。

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

模拟实现

stack其实是一种适配器设计模式,它的接口实现和vector非常的相像,因此我们可以直接使用vector去实现stack

#pragma once#include<iostream>
#include<string>
#include<vector>
#include<list>
#include<stack>
using namespace std;namespace my {template<class T, class con = vector<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 empty() {return _con.empty();}private:con _con;};
}

queue

队列和栈其实都是一样的接口和功能,不同的是队列是一种先进先出的容器,和栈刚好相反。还有就是栈的底层是数组而队列的底层是链表,因此queue多了返回队头和队尾的接口。

用队列实现栈

image-20230213205546685

这个和上面的用栈实现队列是一样的,都是为了模拟出各自的性质,所以这里也可以用两个队列去实现。

class MyStack {
public:MyStack() {}void push(int x) {//元素先入第二个队列,保证最先入队列的元素在队头q2.push(x);//将原队列的所有元素依次入第二个队列,保证队列结构//再进行交换while(!q1.empty()){q2.push(q1.front());q1.pop();}swap(q1, q2);}int pop() {int x = q1.front();q1.pop();return x;}int top() {return q1.front();}bool empty() {return q1.empty();}private:queue<int> q1;queue<int> q2;};

模拟实现

queue也是一种适配器设计模式,所以也可以用已有的容器去实现它,因为queue的底层实现是链表,所以我们用list去实现

#pragma once#include"stack.h"namespace my2 {template<class T, class con = list<T>>class queue {public:void push(const T& x) {_con.push_back(x);}void pop() {_con.pop_front();}const T& top() {return _con.front();}bool empty() {return _con.empty();}private:con _con;};
}

相关文章:

【C++】---Stack和Queue的用法及其模拟实现

文章目录Stack最小栈栈的弹出压入序列逆波兰表达式求值用栈实现队列模拟实现queue用队列实现栈模拟实现Stack stack是一种容器适配器&#xff0c;专门用在具有后进先出操作的上下文环境中&#xff0c;其删除只能从容器的一端进行元素的插入与提取操作。它的使用和之前学习的ve…...

Python GUI编程

Python 提供了多个图形开发界面的库&#xff0c;几个常用 Python GUI 库如下&#xff1a; Tkinter&#xff1a; Tkinter 模块(Tk 接口)是 Python 的标准 Tk GUI 工具包的接口 .Tk 和 Tkinter 可以在大多数的 Unix 平台下使用,同样可以应用在 Windows 和 Macintosh 系统里。Tk8…...

2023年浙江水利水电施工安全员精选真题题库及答案

百分百题库提供水利水电施工安全员考试试题、水利水电施工安全员考试预测题、水利水电施工安全员考试真题、水利水电施工安全员证考试题库等&#xff0c;提供在线做题刷题&#xff0c;在线模拟考试&#xff0c;助你考试轻松过关。 119.下列关于大模板按照的说法正确的是&#x…...

Solon2 开发之插件,三、插件体外扩展机制(E-Spi)

插件体外扩展机制&#xff0c;简称&#xff1a;E-Spi。用于解决 fatjar 模式部署时的扩展需求。比如&#xff1a; 把一些“业务模块”做成插件包放到体外把数据源配置文件放到体外&#xff0c;方便后续修改 其中&#xff0c; .properties 或 .yml 文件都会做为扩展配置加载&a…...

数据结构与算法(Java版) | 数据结构与算法的关系

从这一节起&#xff0c;咱们就要开始进入到「第二章——数据结构与算法的介绍」的学习中了&#xff0c;总的来说&#xff0c;第二章要讲解的内容其实也不是特别的多&#xff0c;内容也多偏理论&#xff0c;相信大家学起来是会比较轻松愉快的。 接下来&#xff0c;就请大家跟随…...

华科万维C++章节练习3_7

题目&#xff1a; 编程实现两种温度体系华氏温度和摄氏温度的相互转换; 以F作为华氏温度体系的单位&#xff0c;以C作为摄氏温度体系的单位。 要求当输入以F作为单位的温度值时(温度值范围[-500F~500F]&#xff0c; 否则提示“数据输入有误!”&#xff09;将其转换为对应的摄氏…...

CHAPTER 5 Jenkins SonarQube

Jenkins & SonarQube5.1 安装SonarQube1. 下载镜像2. 导出到其他服务器3. 准备工作4. docker-compose文件5. 启动容器5.2 登录SonarQube1.登录2. 安装中文语言插件3. 安装其他插件5.3 部署扫描器sonar-scanner1. 部署sonar-scanner2. 新建项目3. 扫描代码4. 查看报告5.4 Je…...

[AAAI 2023] Oral : Zero-shot 零样本/ Few-shot 少样本收录论文集合

零样本 (7篇)&#xff1a; CALIP: Zero-Shot Enhancement of CLIP with Parameter-free AttentionGuo Ziyu; Zhang Renrui; Qiu Longtian; ma Xianzheng; Miao Xupeng; He Xuming; Cui BinMaximum Entropy Population-Based Training for Zero-Shot Human-AI CoordinationZhao …...

驱动开发 2.13

设备树 设备树就是一种描述硬件信息的树形结构&#xff0c;设备树上有很多设备节点&#xff0c;每一个设备节点都描述了一个硬件设备信息&#xff0c;设备节点中也可以再包含子设备节点和设备属性&#xff0c;同一个节点的不同属性是以链表结构存储&#xff0c;设备树有.dts设…...

【数据库】sql函数和多表关联查询

目录 一&#xff0c;SQL函数 1&#xff0c;聚合函数 1&#xff0c; count函数 2&#xff0c; AVG函数 3&#xff0c; SUM函数 4&#xff0c; MAX函数 5&#xff0c; MIN函数 6&#xff0c;数据分组——GROUP BY 7&#xff0c;限定组的结果&#xff0c;HAVING 8&#x…...

6-周赛332总结

6-周赛332总结 过了Q1和Q2&#xff0c;Q2知道用二分但是边界处理的不是很好&#xff0c;迷迷糊糊过的&#xff08;手动再移动了下返回值…&#xff09; Q3知道将子字符串的值取出来&#xff0c;将最短位置放在哈希表中&#xff0c;然后异或在哈希表中找值。但是我这个猪头脑袋…...

嵌入式Qt 开发一个音乐播放器

上篇文章&#xff1a;RK3568源码编译与交叉编译环境搭建&#xff0c;进行了OK3568开发板软件开发环境搭建&#xff0c;通过编译RK3568的源码&#xff0c;可以得到Qt开发的交叉编译相关工具。 本篇&#xff0c;就来在搭建好的软件开发中&#xff0c;进行Qt软件的开发测试。由于…...

2023秋招万得集团AI算法岗面经分享

本专栏分享 计算机小伙伴秋招春招找工作的面试经验和面试的详情知识点 专栏首页:秋招算法类面经分享 主要分享计算机算法类在面试互联网公司时候一些真实的经验 2022年 11.22下午AI算法岗面试 (1)一面35min 1、自我介绍 2、科研:长文本MRC...

RoI Transformer论文翻译详解

Learning RoI Transformer for Oriented Object Detection in Aerial Images 0.摘要 航空图像中的目标检测是计算机视觉中一个活跃而又具有挑战性的任务&#xff0c;因为它具有鸟瞰视角、高度复杂的背景和变化的物体外观。特别是在航空图像中检测密集的目标时&#xff0c;基于…...

Prometheus 自动发现监控AWS EC2实例

本文章简述对接自动发现AWS云EC2实例 前提环境&#xff1a; PromethuesGrafanaAWS IAM权限 涉及参考文档&#xff1a; AWS EC2Grafana 通用监控模板 一、IAM 用户创建 1、创建Prometheus 策略 策略规则&#xff1a; {"Version": "2012-10-17",&quo…...

从recat源码角度看setState流程

setState setState() 将对组件 state 的更改排入队列批量推迟更新&#xff0c;并通知 React 需要使用更新后的 state 重新渲染此组件及其子组件。其实setState实际上不是异步&#xff0c;只是代码执行顺序不同&#xff0c;有了异步的感觉。 使用方法 setState(stateChange | u…...

【Java|golang】1234. 替换子串得到平衡字符串---双指针

有一个只含有 ‘Q’, ‘W’, ‘E’, ‘R’ 四种字符&#xff0c;且长度为 n 的字符串。 假如在该字符串中&#xff0c;这四个字符都恰好出现 n/4 次&#xff0c;那么它就是一个「平衡字符串」。 给你一个这样的字符串 s&#xff0c;请通过「替换一个子串」的方式&#xff0c;…...

自监督表征学习方法——BYOL(Bootstrap Your Own Latent)

自监督表征学习方法——BYOL(Bootstrap Your Own Latent) 参考文献&#xff1a;《Bootstrap Your Own Latent A New Approach to Self-Supervised Learning》 1.前言背景 学习良好的图像表示是计算机视觉中的一个关键挑战&#xff0c;因为它允许对下游任务进行有效的训练。许…...

均衡负载集群(LBC)-1

均衡负载集群&#xff08;LBC&#xff09; 客户–>通过Internet—>负载调度器—>n台真实服务器 负载调度器&#xff1a; 软件&#xff1a;LVS&#xff1b;Nginx&#xff1b;Haproxy硬件&#xff1a;F5&#xff1b; LVS架构&#xff1a; 使用到C/S&#xff08;B/S…...

WebSocket

关于WebSocket&#xff1a; WebSocket 协议在2008年诞生&#xff0c;2011年成为国际标准。现在所有浏览器都已经支持了。 WebSocket 的最大特点就是&#xff0c;服务器可以主动向客户端推送信息&#xff0c;客户端也可以主动向服务器发送信息&#xff0c;是真正的双向平等对话…...

RestClient

什么是RestClient RestClient 是 Elasticsearch 官方提供的 Java 低级 REST 客户端&#xff0c;它允许HTTP与Elasticsearch 集群通信&#xff0c;而无需处理 JSON 序列化/反序列化等底层细节。它是 Elasticsearch Java API 客户端的基础。 RestClient 主要特点 轻量级&#xff…...

conda相比python好处

Conda 作为 Python 的环境和包管理工具&#xff0c;相比原生 Python 生态&#xff08;如 pip 虚拟环境&#xff09;有许多独特优势&#xff0c;尤其在多项目管理、依赖处理和跨平台兼容性等方面表现更优。以下是 Conda 的核心好处&#xff1a; 一、一站式环境管理&#xff1a…...

51c自动驾驶~合集58

我自己的原文哦~ https://blog.51cto.com/whaosoft/13967107 #CCA-Attention 全局池化局部保留&#xff0c;CCA-Attention为LLM长文本建模带来突破性进展 琶洲实验室、华南理工大学联合推出关键上下文感知注意力机制&#xff08;CCA-Attention&#xff09;&#xff0c;…...

MySQL 隔离级别:脏读、幻读及不可重复读的原理与示例

一、MySQL 隔离级别 MySQL 提供了四种隔离级别,用于控制事务之间的并发访问以及数据的可见性,不同隔离级别对脏读、幻读、不可重复读这几种并发数据问题有着不同的处理方式,具体如下: 隔离级别脏读不可重复读幻读性能特点及锁机制读未提交(READ UNCOMMITTED)允许出现允许…...

Swift 协议扩展精进之路:解决 CoreData 托管实体子类的类型不匹配问题(下)

概述 在 Swift 开发语言中&#xff0c;各位秃头小码农们可以充分利用语法本身所带来的便利去劈荆斩棘。我们还可以恣意利用泛型、协议关联类型和协议扩展来进一步简化和优化我们复杂的代码需求。 不过&#xff0c;在涉及到多个子类派生于基类进行多态模拟的场景下&#xff0c;…...

解决Ubuntu22.04 VMware失败的问题 ubuntu入门之二十八

现象1 打开VMware失败 Ubuntu升级之后打开VMware上报需要安装vmmon和vmnet&#xff0c;点击确认后如下提示 最终上报fail 解决方法 内核升级导致&#xff0c;需要在新内核下重新下载编译安装 查看版本 $ vmware -v VMware Workstation 17.5.1 build-23298084$ lsb_release…...

大数据学习(132)-HIve数据分析

​​​​&#x1f34b;&#x1f34b;大数据学习&#x1f34b;&#x1f34b; &#x1f525;系列专栏&#xff1a; &#x1f451;哲学语录: 用力所能及&#xff0c;改变世界。 &#x1f496;如果觉得博主的文章还不错的话&#xff0c;请点赞&#x1f44d;收藏⭐️留言&#x1f4…...

React---day11

14.4 react-redux第三方库 提供connect、thunk之类的函数 以获取一个banner数据为例子 store&#xff1a; 我们在使用异步的时候理应是要使用中间件的&#xff0c;但是configureStore 已经自动集成了 redux-thunk&#xff0c;注意action里面要返回函数 import { configureS…...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

STM32HAL库USART源代码解析及应用

STM32HAL库USART源代码解析 前言STM32CubeIDE配置串口USART和UART的选择使用模式参数设置GPIO配置DMA配置中断配置硬件流控制使能生成代码解析和使用方法串口初始化__UART_HandleTypeDef结构体浅析HAL库代码实际使用方法使用轮询方式发送使用轮询方式接收使用中断方式发送使用中…...