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

【三】一起算法---栈:STL stack、手写栈、单调栈

纸上得来终觉浅,绝知此事要躬行。大家好!我是霜淮子,欢迎订阅我的专栏《算法系列》。

学习经典算法和经典代码,建立算法思维;大量编码让代码成为我们大脑的一部分。

⭐️已更系列

 1、基础数据结构

       1.1、链表➡传送门

       1.2、队列➡传送门

       1.3、 栈   ➡本章

专栏直达《算法系列》

目录

前言

文本翻转

问题描述:

输入:

输出:

1.3、栈

1.3.1、STL stack

1.3.2、手写栈

1.3.3、单调栈


前言

文本翻转

问题描述:

伊格内修斯喜欢用相反的方式写字。给定一行由伊格内修斯写的文字,你应该把所有的单词倒过来,然后输出。

输入:

测试样本:olleh !dlrow

输出:

hello world!

1.3、栈

“栈”的特点是”先进后出“。栈在生活中有许多表现:坐电梯,先进电梯的被挤在最里面,只能最后才出来;栈只有唯一的一个出入口,从这个口进入,也从这个口弹出,这是它与队列最大的区别。队列有一个出口和一个入口,所以手写栈比手写队列会简单一点,

在编程中常用的递归就是用栈来实现的。栈要用存储空间来存储,如果栈的深度太大,或者进栈的数组太大,那么总数会超过系统为栈分配的空间,就会爆栈导致栈溢出。为避免爆栈,需要严格控制栈的大小。

1.3.1、STL stack

STL  stack 的有关操作

  • stack<Type> s 定义栈,Type为数据类型,如int,float,char等。
  • a.push(item) 把item放到栈顶。
  • s.top() 返回栈顶元素,但不会删除。
  • s.pop()  删除栈顶元素,但不会返回。在出栈时需要执行两步操作:先使用pop()获得栈顶元素,在使用pop()删除栈顶元素。
  • s.size() 返回栈中的元素个数。
  • s.empty() 检查栈是否为空,如果为空,返回True,否则返回false.

文本翻转的代码如下:

#include<bits/stdc++.h>
using namespace std;
int main(){int n;   scanf("%d",&n);  getchar();while(n--){stack<char> s;while(true){char ch = getchar();              //一次读入一个字符if(ch==' '||ch=='\n'||ch==EOF){while(!s.empty()){ printf("%c",s.top()); s.pop();} //输出并清除栈顶if(ch=='\n'||ch==EOF)  break;printf(" ");}else    s.push(ch);               //入栈}printf("\n");
}
return 0;
}

1.3.2、手写栈

手写栈代码简单且节省空间。

#include<bits/stdc++.h>
const int N = 100100;
struct mystack{char a[N];                            //存放栈元素,字符型int t = 0;                            //栈顶位置void push(char x){ a[++t] = x; }      //送入栈char top()       { return a[t]; }     //返回栈顶元素void pop()       { t--;         }     //弹出栈顶int empty()      { return t==0?1:0;}  //返回1表示空
}st;
int main(){
int n;	scanf("%d",&n);  getchar();
while(n--){
while(true){
char ch = getchar();            //一次读入一个字符
if(ch==' '||ch=='\n'||ch==EOF){while(!st.empty()){ printf("%c",st.top()); st.pop();}  //输出并清除栈顶	if(ch=='\n'||ch==EOF)  break;printf(" ");}else    st.push(ch);              //入栈}printf("\n");}return 0;
}

1.3.3、单调栈

单调栈不是一种新的栈结构,它在结构上仍然是一个普通的栈,它是栈的一种使用方式。

单调栈内的元素是单调递增或单调递减的,有单调递增栈、单调递减栈。单调栈可以用来处理比较问题。

单调栈使用时始终保持栈内的元素是单调的。例如,单调递减栈从栈顶到栈底是从小到大的顺序。当一个数入栈时,与栈顶比较,若比栈顶小,则入栈,若比栈顶大,则弹出栈顶,直到这个数能入栈为止。注意:每个数都一定入栈。

-END-

 

相关文章:

【三】一起算法---栈:STL stack、手写栈、单调栈

纸上得来终觉浅&#xff0c;绝知此事要躬行。大家好&#xff01;我是霜淮子&#xff0c;欢迎订阅我的专栏《算法系列》。 学习经典算法和经典代码&#xff0c;建立算法思维&#xff1b;大量编码让代码成为我们大脑的一部分。 ⭐️已更系列 1、基础数据结构 1.1、链表➡传送门 1…...

电路设计的一些概念

锁存器的产生 论述1 (转)时序电路&#xff0c;生成触发器&#xff0c;触发器是有使能端的&#xff0c;使能端无效时数据不变&#xff0c;这是触发器的特性。 组合逻辑&#xff0c;由于数据要保持不变&#xff0c;只能通过锁存器来保存。 第一个代码&#xff0c;由于是时序逻…...

【Linux】Linux下权限的理解

前言&#xff1a;在之前我们已经对基本的指令进行了深入的学习&#xff0c;接下来我将带领大家学习的是关于权限的相关问题。在之前&#xff0c;我们一直是使用的【root】用户&#xff0c;即为“超级用户”&#xff0c;通过对权限的学习之后&#xff0c;我们就会慢慢的切换到普…...

Prometheus监控实战系列十七:探针监控

目前对于应用程序的监控主要有两种方式&#xff0c;一种被称为白盒监控&#xff0c;它通过获取目标的内部信息指标&#xff0c;来监控目标的状态情况&#xff0c;我们前面介绍的主机监控、容器监控都属于此类监控。另一种则是“黑盒监控”&#xff0c;它指在程序外部通过探针的…...

题目:JPA的懒加载失效是什么情况?

题目&#xff1a;JPA的懒加载失效是什么情况&#xff1f;Q1&#xff1a;什么是JPA的懒加载&#xff1f;Q2&#xff1a;JPA的懒加载会在什么情况下失效&#xff1f;Q3&#xff1a;如何避免JPA的懒加载失效&#xff1f;前言&#xff1a;在使用JPA进行数据库操作时&#xff0c;懒加…...

十六、消息推送

一、什么是消息推送&#xff1f; 消息推送通常是指网站的运营工作等人员&#xff0c;通过某种工具对用户当前网页或移动设备 APP 进行的主动消息推送。 消息推送一般又分为 Web 端消息推送和移动端消息推送。 消息推送无非是推&#xff08;push&#xff09;和拉&#xff08;p…...

PMP项目管理-【第一章】引论

项目知识体系&#xff1a; 项目管理知识体系&#xff1a; 1.1 项目特性 独特性&#xff1a;独特性会带来不确定性(风险) 临时性&#xff1a;1> 任何项目都有起始终止时间 2> 项目具备临时性&#xff0c;项目成果可能是永久的 1.2 项目驱动变革 从商业角度来看&#xff0c…...

前端布局小案例,分享3个漂亮的卡片组件

当今互联网发展迅猛&#xff0c;各种应用、网站和软件层出不穷&#xff0c;其中前端技术的发展更是让人瞩目。随着用户对于界面设计的要求越来越高&#xff0c;漂亮的卡片组件在各类网页设计中变得越来越流行。本文将分享三个精美的卡片组件&#xff0c;帮助您在前端开发中轻松…...

博客重载记录

博客重载记录流控算法实现open系统调用流程二分查找前言&#xff1a; 有时候看了一些比较好的文章&#xff0c;过几天就忘了&#xff0c;想想不如自己实现一遍博客代码或按博客结构自己写一遍&#xff0c;加深印象&#xff0c;但把别人的内容改个名字变成自己的博客&#xff0c…...

open-cv绘制简单形状line() circle() rectangle() polylines() putText() cvtColor()

OpenCV彩色图像中一个像素是按照“B-G-R”模式组织的。 绘图函数的一些公众参数&#xff1a; img &#xff1a;图像对象 color&#xff1a; 颜色&#xff0c;如果彩色用一个三元组表示&#xff0c;三元组的元素按照B-G-R组织&#xff0c;三元组(0,255,0)中B为0&#xff0c;G为2…...

基于 PyTorch + LSTM 进行时间序列预测(附完整源码)

时间序列数据&#xff0c;顾名思义是一种随时间变化的数据类型。 例如&#xff0c;24小时内的温度、一个月内各种产品的价格、某家公司一年内的股票价格等。深度学习模型如长短期记忆网络&#xff08;LSTM&#xff09;能够捕捉时间序列数据中的模式&#xff0c;因此可以用于预…...

GEE页面介绍

目录一、背景二、用户界面三、数据类型&#xff1a;栅格1、请求图像集合2、学习查看栅格元数据3、矢量实例一&#xff1a;四、数据集五、数据属性1、空间分辨率2、时间分辨率六可视化多个波段1、真彩色(TCI)2彩色红外&#xff08;CI&#xff09;3、伪色 1 和 2 (FC1/FC2)七、可…...

python自动发送邮件,qq邮箱、网易邮箱自动发送和回复

在python中&#xff0c;我们可以用程序来实现向别人的邮箱自动发送一封邮件&#xff0c;甚至可以定时&#xff0c;如每天8点钟准时给某人发送一封邮件。今天&#xff0c;我们就来学习一下&#xff0c;如何向qq邮箱&#xff0c;网易邮箱等发送邮件。 一、获取邮箱的SMTP授权码。…...

hastcat

hashcat 下载地址: https://hashcat.net/hashcat/ 案例 Usage: hashcat [options]... hash|hashfile|hccapxfile [dictionary|mask|directory]...https://xz.aliyun.com/t/4008破解linux shadow /etc/shadow中密码格式: $id$salt$encrypted如:$1$2eWq10AC$NaQqalCk3 1表…...

242. 一个简单的整数问题

Powered by:NEFU AB-IN Link 文章目录242. 一个简单的整数问题题意思路代码242. 一个简单的整数问题 题意 给定长度为 N的数列 A&#xff0c;然后输入 M行操作指令。 第一类指令形如 C l r d&#xff0c;表示把数列中第 l∼r个数都加 d 第二类指令形如 Q x&#xff0c;表示询问…...

docker安装Redis高可用(一主二从三哨兵)

本次教程使用docker swarm安装 准备三台机器 hostIP用途node1192.168.31.130redis-master01&#xff0c;redis哨兵节点01node2192.168.31.131redis-slave01, redis哨兵节点02node3192.168.31.132redis-slave02 redis哨兵节点02 注意事项&#xff1a; 1&#xff1a;需要保证三…...

安全防御之入侵检测篇

目录 1.什么是IDS&#xff1f; 2.IDS和防火墙有什么不同&#xff1f;3.IDS的工作原理&#xff1f; 4.IDS的主要检测方法有哪些&#xff1f;请详细说明 5.IDS的部署方式有哪些&#xff1f; 6.IDS的签名是什么意思&#xff1f;签名过滤器有什么用&#xff1f;例外签名的配置作…...

学习系统编程No.10【文件描述符】

引言&#xff1a; 北京时间&#xff1a;2023/3/25&#xff0c;昨天摆烂一天&#xff0c;今天再次坐牢7小时&#xff0c;难受尽在不言中&#xff0c;并且对于笔试题&#xff0c;还是非常的困难&#xff0c;可能是我做题不够多&#xff0c;也可能是没有好好的总结之前做过的一些…...

网络基础认识

目录 一、计算机网络背景 1.1 网络发展 1.2 "协议"由来 二、网络协议初识 2.1 协议分层 2.2 OSI七层模型 2.3 TCP/IP五层模型 三、网络协议栈 四、数据包封装与分用 五、网络传输基本流程 5.1 同局域网的两台主机通信 5.2 跨网络的两台主机通信 六、网络…...

【蓝桥杯_练习】

蓝桥杯1.创建工程2.LED灯点亮led.c3.LCD液晶屏显示lcd.c4.定时器按键单机interrupt.hinterrupt.cman.c5.定时器&#xff08;长按键&#xff09;interrupt.hinterrupt.cmain.c6.PWMmain.c7.定时器-输入捕获&#xff08;频率&#xff0c;占空比测量&#xff09;interrupt.cmain.c…...

【入坑系列】TiDB 强制索引在不同库下不生效问题

文章目录 背景SQL 优化情况线上SQL运行情况分析怀疑1:执行计划绑定问题?尝试:SHOW WARNINGS 查看警告探索 TiDB 的 USE_INDEX 写法Hint 不生效问题排查解决参考背景 项目中使用 TiDB 数据库,并对 SQL 进行优化了,添加了强制索引。 UAT 环境已经生效,但 PROD 环境强制索…...

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

剑指offer20_链表中环的入口节点

链表中环的入口节点 给定一个链表&#xff0c;若其中包含环&#xff0c;则输出环的入口节点。 若其中不包含环&#xff0c;则输出null。 数据范围 节点 val 值取值范围 [ 1 , 1000 ] [1,1000] [1,1000]。 节点 val 值各不相同。 链表长度 [ 0 , 500 ] [0,500] [0,500]。 …...

页面渲染流程与性能优化

页面渲染流程与性能优化详解&#xff08;完整版&#xff09; 一、现代浏览器渲染流程&#xff08;详细说明&#xff09; 1. 构建DOM树 浏览器接收到HTML文档后&#xff0c;会逐步解析并构建DOM&#xff08;Document Object Model&#xff09;树。具体过程如下&#xff1a; (…...

视频字幕质量评估的大规模细粒度基准

大家读完觉得有帮助记得关注和点赞&#xff01;&#xff01;&#xff01; 摘要 视频字幕在文本到视频生成任务中起着至关重要的作用&#xff0c;因为它们的质量直接影响所生成视频的语义连贯性和视觉保真度。尽管大型视觉-语言模型&#xff08;VLMs&#xff09;在字幕生成方面…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

今日学习:Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据

微软PowerBI考试 PL300-在 Power BI 中清理、转换和加载数据 Power Query 具有大量专门帮助您清理和准备数据以供分析的功能。 您将了解如何简化复杂模型、更改数据类型、重命名对象和透视数据。 您还将了解如何分析列&#xff0c;以便知晓哪些列包含有价值的数据&#xff0c;…...

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数

高效线程安全的单例模式:Python 中的懒加载与自定义初始化参数 在软件开发中,单例模式(Singleton Pattern)是一种常见的设计模式,确保一个类仅有一个实例,并提供一个全局访问点。在多线程环境下,实现单例模式时需要注意线程安全问题,以防止多个线程同时创建实例,导致…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...