文档章节

100-29

da_d
 da_d
发布于 2012/11/12 15:05
字数 564
阅读 25
收藏 0
29.栈的push、pop序列(栈)
题目:输入两个整数序列。其中一个序列表示栈的push顺序,
判断另一个序列有没有可能是对应的pop顺序。
为了简单起见,我们假设push序列的任意两个整数都是不相等的。 
比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。
因为可以有如下的push和pop序列:
push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,
这样得到的pop序列就是4、5、3、2、1。

但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。

思路:看到这道题,还是按照最简单的思路,我就真的弄一个栈,然后往里面压数据。然后循环取栈顶的数据,如果跟要验证的数组相同就出栈,到最后要验证的数组都符合,就得到了结果。但如果不相等,就继续往里面压数据。直到数据压满了,然后栈顶还是不相等。这就说明不能由已知的栈pop得出。

贴上代码:

/*=======================================================*\
29.栈的push、pop序列(栈)
题目:输入两个整数序列。其中一个序列表示栈的push顺序,
判断另一个序列有没有可能是对应的pop顺序。
为了简单起见,我们假设push序列的任意两个整数都是不相等的。 
比如输入的push序列是1、2、3、4、5,那么4、5、3、2、1就有可能是一个pop系列。
因为可以有如下的push和pop序列:
push 1,push 2,push 3,push 4,pop,push 5,pop,pop,pop,pop,
这样得到的pop序列就是4、5、3、2、1。
但序列4、3、5、1、2就不可能是push序列1、2、3、4、5的pop序列。
\*=======================================================*/
#include <iostream>
#include <stack>

using namespace std;

int isPopList(int *pushIndex , int pushLength ,int *popIndex , int popLength){
	stack<int> s;
	int pushI = 0;
	int popI = 0;
	int ret = true;
	s.push(pushIndex[pushI]);
	++pushI;
	while(1){
		if( s.top() != popIndex[popI]){
			if(pushI < pushLength){
				s.push(pushIndex[pushI]);
				++pushI;
			}else{
				ret = false;
				break;
			}
		}else{
			s.pop();
			++popI;
			if(popI == popLength){
				break;
			}
		}
	}
	return ret;
}

int main(){
	int pushIndex[] = {1,2,3,4,5};
	//int popIndex[] = {4,3,5,1,2};
	int popIndex[] = {5,4,3,2,1};
	int ret = isPopList(pushIndex,sizeof(pushIndex)/sizeof(int),popIndex,sizeof(popIndex)/sizeof(int));
	cout << ret << endl;
	return 1;
}

© 著作权归作者所有

上一篇: 100-30
下一篇: 100-28
da_d
粉丝 7
博文 133
码字总数 53553
作品 0
东城
程序员
私信 提问
redis cluster搭建

服务器信息: redis版本 3.2.0 ruby版本 1.8.7.374 10.100.0.29 redis node 1 10.100.0.45 redis node 2 10.100.0.46 redis node 3 10.100.0.47 redis node 4 10.100.0.49 redis node 5 red......

jungong
2016/06/06
331
0
Golang 性能忽然增加变慢10倍的现象,推测是编译器在spilt stack,导致的问题

本测试分别执行三种测试: 1.程序嵌套调用时使用int; 2.程序嵌套调用时使用int+string; 3.程序嵌套调用时使用int+interface{}; 测试脚本如下: // stackSplitTestpackage main import ( "f...

wkh
2014/05/06
899
0
nagios邮件报警有时候能收到,有时候收不到

我用mail命令可以收到邮件,我把他写到commands.cfg 里 define command{ command_name notify-host-by-email command_line /usr/bin/printf "%b" "***** Nagios *****\n\nNotification Type......

抱着裸睡
2012/04/19
1K
2
SQL Server 日期格式化输出

转自:http://hi.baidu.com/%BC%D1%C0%D6%B1%C8%BA%A3/blog/item/fdaf6c9525adfa0f7af480ec.html T-SQL Script Output format SELECT CONVERT(VARCHAR(100), GETDATE(), 0) 03 6 2010 4:19PM ......

晨曦之光
2012/06/05
344
0
Android图表之-Echarts

ECharts是一款开源、功能强大的数据可视化产品,紧跟着大数据时代的步伐,是我接触过的最优秀的可视化工具,也是进步最快的软件,希望它早日成为世界级的开源项目,之前使用过MPAndroidChar...

cg19910712
2017/05/26
0
0

没有更多内容

加载失败,请刷新页面

加载更多

springboot2.0 maven打包分离lib,resources

springboot将工程打包成jar包后,会出现获取classpath下的文件出现测试环境正常而生产环境文件找不到的问题,这是因为 1、在调试过程中,文件是真实存在于磁盘的某个目录。此时通过获取文件路...

陈俊凯
今天
6
0
BootStrap

一、BootStrap 简洁、直观、强悍的前端开发框架,让web开发更加迅速、简单 中文镜像网站:http://www.bootcss.com 用于开发响应式布局、移动设备优先的WEB项目 1、使用boot 创建文件夹,在文...

wytao1995
今天
10
0
小知识:讲述Linux命令别名与资源文件的区别

别名 别名是命令的快捷方式。为那些需要经常执行,但需要很长时间输入的长命令创建快捷方式很有用。语法是: alias ppp='ping www.baidu.com' 它们并不总是用来缩短长命令。重要的是,你将它...

老孟的Linux私房菜
今天
8
0
《JAVA核心知识》学习笔记(6. Spring 原理)-5

它是一个全面的、企业应用开发一站式的解决方案,贯穿表现层、业务层、持久层。但是 Spring 仍然可以和其他的框架无缝整合。 6.1.1. Spring 特点 6.1.1.1. 轻量级 6.1.1.2. 控制反转 6.1.1....

Shingfi
今天
8
0
Excel导入数据库数据+Excel导入网页数据【实时追踪】

1.Excel导入数据库数据:数据选项卡------>导入数据 2.Excel导入网页数据【实时追踪】:

东方墨天
今天
11
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部