当前位置：首页 > 编程日记 > 正文

【ACM】【STL】stack应用

编程日记 2024-10-15 20:40:00

C++ Stacks（堆栈）

C++ Stack（堆栈）是一个容器类的改编，为程序员提供了堆栈的全部功能，——也就是说实现了一个先进后出（FILO）的数据结构。

操作	比较和分配堆栈
empty()	堆栈为空则返回真
pop()	移除栈顶元素
push()	在栈顶增加元素
size()	返回栈中元素数目
top()	返回栈顶元素

现学现用：

一、POJ 1363 Rails

http://poj.org/problem?id=1363

应用stack，本题还需要注意输入格式，输出格式。

题目大意：给你一个出栈顺序，判断这个出栈顺序是否合法。先将出栈顺序保存在数组output中，然后按照顺序进栈，让目前这个进栈的数和与正在指向的那个output数组里的数相同时，则说明这个进栈的数是要出栈的，所以input.pop()，当所有的数都都按照顺序放在stack中，即i==n时，结束循环之前i++，则推出了循环，这时如果k==n 或者栈为空，都可以作为判断条件

#include <iostream>
#include <cstdio>
#include <stack>
using namespace std;
int output[1000+5];
int main()
{int n,i,k;while(scanf("%d",&n) && n){while(scanf("%d",&output[0]) && output[0])//b数组用来储存出栈顺序{for(i=1;i<n;i++)scanf("%d",&output[i]);stack<int> input;i=1;//赋值k=0;while(i<=n){input.push(i);//表示进栈while(input.top()==output[k])//当目前进栈的元素等于要出栈的元素时，则表示，该元素出栈，从input数组里去掉{if(!input.empty())	input.pop();k++;if(input.empty())	break;//全部出栈}i++;//这里的j++表示新的进栈元素的下标是刚出栈元素的下标，新的进栈元素就是i++之后的。}if(k==n)//if(input.empty())printf("Yes\n");elseprintf("No\n");}printf("\n");}return 0;
}

还有不利用stack，直接用两个数组进行模拟

#include <iostream>
#include <cstdio>
using namespace std;
int output[1000+10],input[1000+10];
int main()
{int n,i,j,k;while(scanf("%d",&n) && n){while(scanf("%d",&output[0]) && output[0])//b数组用来储存出栈顺序{for(i=1;i<n;i++)scanf("%d",&output[i]);i=1;j=0;k=0;while(i<=n && j<n){input[j]=i;//表示进栈while(input[j]==output[k])//当目前进栈的元素等于要出栈的元素时，则表示，该元素出栈，从input数组里去掉{j--;k++;if(j==-1)	break;//全部出栈}i++;j++;//这里的j++表示新的进栈元素的下标是刚出栈元素的下标，新的进栈元素就是i++之后的。}if(k==n)printf("Yes\n");elseprintf("No\n");}printf("\n");}return 0;
}

二、Text Reverse

http://acm.hdu.edu.cn/showproblem.php?pid=1062

遇到空格，就输出栈里的内容，可能存在又两个空格的情况，所以中间的continue要特别注意

#include <iostream>
#include <cstdio>
#include <stack>
#include <cstring>
using namespace std;
int output[1000+5];
int main()
{int i,T,len;char str[1010];stack<char> s;cin >>T;getchar();while(T--){i=0;memset(str,0,sizeof(str));gets(str);while(str[i]){if(str[i]==' '){while(!s.empty()){printf("%c",s.top());s.pop();}printf(" ");i++;continue;}s.push(str[i]);i++;}while(!s.empty()){printf("%c",s.top());s.pop();}printf("\n");}return 0;
}

还有另外一种做法，用到一个函数strrev()

#include<stdio.h>
#include<string.h>
int main()
{int t;scanf("%d\n",&t);while(t--){char s[1005]={};while(scanf("%[^ \n]",s)!=EOF){printf("%s",strrev(s));s[0]=0;putchar(getchar());}}return 0;
}

如果：

scanf("%[^ \n]",s)

换成

scanf("%[^\n]",s)

则是一整行进行反转

三、Train Problem I

http://acm.hdu.edu.cn/showproblem.php?pid=1022

和第一题不一样的地方在于在判断满足条件以后，需要把火车进站出站的顺序写出来，所以第一个stack用来判断是否满足条件，第二次右重新来一遍，来输出in 和 out 。（这只是我的方法，如果大家有更好的方法，希望大家能够评论，一起探讨）

#include <iostream>
#include <set>
#include <cstdio>
#include <string>
#include <map>
#include <queue>
#include <stack>
#include <algorithm>
#include <sstream>
typedef long long ll;
using namespace std;int main ()
{string in,out;int N;while(scanf("%d",&N)!=EOF){cin >> in >> out;stack<char> s1,s2;int i,j;i=0;j=0;while(i<in.length()){s1.push(in[i]);while(s1.top()==out[j]){s1.pop();j++;if(s1.empty())break;}i++;}if(j==out.length())cout << "Yes.\n";else{cout << "No.\nFINISH\n";continue;}i=0;j=0;while(i<in.length()){s2.push(in[i]);cout << "in\n";while(s2.top()==out[j]){s2.pop();cout << "out\n";j++;if(s2.empty())break;}i++;}cout << "FINISH\n";}return 0;
}

暂时只找到这三个题，之后有发现会继续补充，大家也可以在评论中推荐！：）

https://www.dkcj.cn/info/23197.html

【ACM】【STL】stack应用

C++ Stacks（堆栈）

现学现用：

一、POJ 1363 Rails

二、Text Reverse

三、Train Problem I

相关文章：

CHUCK手把手带你搞定OPENSTACK

JVM基础面试题及原理讲解

SLAM前端 ---------特征提取之ORB（ORB与SIFT与SURF）

oracle 内存分配和调优总结

【ACM】Doubly Linked List（STL list）

IOS获取焦点页面上移问题

SLAM之特征匹配(二)————RANSAC--------翻译以及经典RANSAC以及其相关的改进的算法小结

【ACM】树小结

【cocos2d-js官方文档】九、cc.loader

更换VC后DDC提示证书不可用

尺度空间理论与图像金字塔

【ACM】 multiset 的一些应用

apache2.2 做后端,增加真实ip到日志中

高可用方案系统架构

OpenCV3.2.0+VS2017在window10开发环境配置记录

C++vector迭代器失效的问题

【HDU】1251统计难题（字典树：二维数组，结构体数组，链表，map）

Jmeter干货不常用却极其有用的几个地方

图像滤波总结（面试经验总结）

【小贴士】DEV 多行注释

JSP+Servlet基础一

Chameleon跨端框架——壹个理想主义团队的开源作品

尺度空间理论与图像金字塔（二）

仿桌面通知pnotify插件

【HDU】1305 Immediate Decodability（字典树：结构体数组，二维数组，链表/指针）

Hyperledger Grid：一个用于分布式供应链解决方案的框架

尺度不变特征变换匹配算法详解

【POJ】2503 Babelfish（字典树，map，指针）

ndk-build: CreateProcess error=193

AI芯片初创公司单纯卖芯片还是捆绑算法的商业模式更好？...