栈相关算法实现详解

news/2024/11/17 2:15:18/

目录

STLstack

栈的简单应用举例

手写栈

单调栈

STLstack

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

栈的简单应用举例

题目:翻转字符转

#include<bits/stdc++.h>
using namespace std;
int main(){int n;cin>>n;getchar();// 读取并丢弃换行符while(n--){stack<char> s;while(true){char ch=getchar();if(ch==' '||ch=='\n'||ch==EOF){while(!s.empty()){cout<<s.top();s.pop();}if(ch=='\n'||ch==EOF){break;}cout<<" ";}else{s.push(ch);}}cout<<endl;}return 0;
}

手写栈

针对上述题目,使用手写栈来实现。

#include<bits/stdc++.h>
const int N=100100;
using namespace std;
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;}
}st;
int main(){int n;cin>>n;getchar();while(n--){while(true){char ch=getchar();if(ch==' '||ch=='\n'||ch=='EOF'){while(!st.empty()){cout<<st.top();st.pop();}if(ch=='\n'||ch=='EOF'){break;}cout<<" ";}else{st.push(ch);}}cout<<endl;}return 0;
}

单调栈

题目

约翰的N\left ( 1\times 10^{5} \right )头奶牛站成一排,奶牛i的身高是H_{i}\left ( 1\times 10^{6} \right )。现在,每只奶牛都在向右看齐。对于奶牛i,如果奶牛j满足i<j且Hi<Hj​,我们可以说奶牛i可以仰望奶牛j。 求出每只奶牛离她最近的仰望对象。

输入格式

6 
3 
2 
6 
1 
1 
2 

输出格式

3 
3 
0 
6 
6 
0 

STL stack代码

#include<bits/stdc++.h>
using namespace std;
int h[100001],ans[100001];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}stack<int>st;for(int i=n;i>=1;i--){while(!st.empty()&&h[st.top()]<=h[i]){st.pop();}if(st.empty()){ans[i]=0;}else{ans[i]=st.top();}st.push(i);}for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}

手写栈代码

#include<bits/stdc++.h>
using namespace std;
const int N=100100;
struct mystack{int a[N];int t=0;void push(int x){a[++t]=x;} int top(){return a[t];}void pop(){t--;}int empty(){return t==0?1:0;}
}st;
int h[N],ans[N];
int main(){int n;cin>>n;for(int i=1;i<=n;i++){cin>>h[i];}for(int i=n;i>=1;i--){while(!st.empty()&&h[st.top()]<=h[i]){st.pop();}if(st.empty()){ans[i]=0;}else{ans[i]=st.top();}st.push(i);}for(int i=1;i<=n;i++){cout<<ans[i]<<endl;}return 0;
}

http://www.ppmy.cn/news/1547592.html

相关文章

Python网络爬虫简介

Python网络爬虫简介 网络爬虫(Web Crawler),又称为网络蜘蛛(Web Spider),是一种自动化程序,能够在互联网上自动抓取、分析和收集数据。Python作为一种简洁、易读且功能强大的编程语言,非常适合用于编写网络爬虫。其丰富的库和工具,如 requests 、 BeautifulSoup 、…

大数据学习15之Scala集合与泛型

1. 概述 大部分编程语言都提供了数据结构对应的编程库&#xff0c;并称之为集合库(Collection Library)&#xff0c;Scala 也不例外&#xff0c;且它还拥有以下优点&#xff1a; 易用&#xff1a;灵活组合运用集合库提供的方法&#xff0c;可以解决大部分集合问题 简洁&#xf…

力扣第 54 题 **螺旋矩阵**

力扣第 54 题是 螺旋矩阵&#xff08;Spiral Matrix&#xff09;。题目要求按螺旋顺序遍历一个 m x n 的矩阵&#xff0c;并返回遍历的结果。 解题思路 螺旋矩阵的遍历顺序是 从左到右&#xff0c;然后 从上到下&#xff0c;接着 从右到左&#xff0c;最后 从下到上&#xff…

AWS CLI

一、介绍 1、简介 aws configure 是 AWS 提供的一个命令行工具&#xff0c;用于快速配置 AWS CLI&#xff08;命令行界面&#xff09;和 AWS SDK&#xff08;软件开发工具包&#xff09;中使用的凭证、默认区域以及输出格式。这个命令是 AWS CLI 中的一个配置工具&#xff0c…

Mac解压包安装MongoDB8并设置launchd自启动

记录一下在mac上安装mongodb8过程&#xff0c;本机是M3芯片所以下载m芯片的安装包&#xff0c;intel芯片的类似操作。 首先下载安装程序包。 # M芯片下载地址 https://fastdl.mongodb.org/osx/mongodb-macos-arm64-8.0.3.tgz # intel芯片下载地址 https://fastdl.mongodb.org…

子网划分学习

举例 10.0.1.0/30&#xff0c;这个给的就是网络地址&#xff0c;那么意思就是网络地址就是一个网段 可以得到网络地址&#xff0c;主机地址&#xff0c;广播地址 这个就是一个网段&#xff0c;但是他有多少的子网呢&#xff0c;该怎么算呢&#xff0c;首先根据子网掩码&…

Spring Boot框架在电商领域的应用

1 绪论 1.1 研究背景 当前社会各行业领域竞争压力非常大&#xff0c;随着当前时代的信息化&#xff0c;科学化发展&#xff0c;让社会各行业领域都争相使用新的信息技术&#xff0c;对行业内的各种相关数据进行科学化&#xff0c;规范化管理。这样的大环境让那些止步不前&#…

Pytorch学习--神经网络--完整的模型验证套路

一、选取的图片 全部代码依托于该博客 二、代码&#xff08;调用训练好的模型&#xff09; import torch import torchvision from PIL import Image from model import *img_path "dog.png" image Image.open(img_path)print(image.size)transform torchvisi…