文档章节

【九度OJ1522】|【剑指offer21】包含min函数的栈

aqia358
 aqia358
发布于 2013/12/23 20:29
字数 508
阅读 153
收藏 1
题目描述:

定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。

输入:

输入可能包含多个测试样例,输入以EOF结束。
对于每个测试案例,输入的第一行为一个整数n(1<=n<=1000000), n代表将要输入的操作的步骤数。
接下来有n行,每行开始有一个字母Ci。
Ci=’s’时,接下有一个数字k,代表将k压入栈。
Ci=’o’时,弹出栈顶元素。

输出:

对应每个测试案例中的每个操作,
若栈不为空,输出相应的栈中最小元素。否则,输出NULL。

样例输入:
7
s 3
s 4
s 2
s 1
o
o
s 0
样例输出:
3
3
2
1
2
3
0
解:注意首先要求是一个栈,即先进后出

解题思路:使用两个栈,一个是普通的数据栈,data,和另外一个help辅助栈,首先在空的时候都压入两个栈,然后对于压入的序列,比较 这个元素和辅助栈栈顶元素,如果小于这个栈顶那么在压入数据栈的时候也压入辅助站,否则,将辅助栈的顶部元素再次压入一次,这样保证了两个栈的大小相等, 这样才能在pop的时候同步。这样需要的空间就是两个相等的栈 。

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.StreamTokenizer;
import java.util.Stack;
/**
 * 两个栈方法
 * @author aqia358
 *
 */
public class Main {
	
	public Stack<Integer> data = new Stack<Integer>();
	public Stack<Integer> help = new Stack<Integer>();
	
	public void push(int value){
		data.push(value);
		if(help.isEmpty()){
			help.push(value);
			System.out.println(value);
		}else{
			int temp = help.peek();
			if(temp < value){
				help.push(temp);
				System.out.println(temp);
			}else{
				help.push(value);
				System.out.println(value);
			}
		}
	}
	public void pop(){
		if(help.isEmpty()){
			System.out.println("NULL");
		}else{
			data.pop();
			help.pop();
			if(help.isEmpty()){
				System.out.println("NULL");
			}else
				System.out.println(help.peek());
		}
	}

	public static void main(String[] args) throws IOException {
		StreamTokenizer st = new StreamTokenizer(new BufferedReader(new InputStreamReader(System.in)));
		while(st.nextToken() != StreamTokenizer.TT_EOF){
			int n = (int)st.nval;
			Main m = new Main();
			for(int i = 0; i < n; i++){
				st.nextToken();
				String op = st.sval;
				if(op.equals("s")){
					st.nextToken();
					int data = (int)st.nval;
					m.push(data);
				}else if(op.equals("o")){
					m.pop();
				}
			}
		}
	}
}



© 著作权归作者所有

共有 人打赏支持
aqia358
粉丝 6
博文 82
码字总数 30297
作品 0
海淀
程序员
[算法总结] 3 道题搞定 BAT 面试——堆栈和队列

本文首发于我的个人博客:尾尾部落 0. 基础概念 栈:后进先出(LIFO) 队列:先进先出(FIFO) 栈的 java 实现 2. 队列的 java 实现 1. 用两个栈实现队列 剑指offer:用两个栈实现队列 Leet...

繁著
09/04
0
0
[剑指offer]包含min函数的栈

题目描述 定义栈的数据结构,请在该类型中实现一个能够得到栈最小元素的min函数。 解题思路 用一个栈stack保存数据,用另外一个栈temp保存依次入栈最小的数 比如,stack中依次入栈 则temp依次...

繁著
06/30
0
0
python剑指offer66题

二维数组的查找 替换空格 从头到尾打印链表 重建二叉树 用两个栈实现队列 选择数组中的最小数字 斐波那契数列 跳台阶 变态跳台阶 矩形覆盖 二进制中1的个数 数值的整数次方 调整数组顺序使奇...

lyy0905
06/03
0
0
剑指Offer学习总结-用两个栈实现队列

剑指Offer学习总结-用两个栈实现队列 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000
01/16
0
0
剑指Offer学习总结-从尾到头打印链表

剑指Offer学习总结-从尾到头打印链表 本系列为剑指Offer学习总结,主要是代码案例的分析和实现: 书籍链接:http://product.dangdang.com/24242724.html 原作者博客:http://zhedahht.blog....

wwlcsdn000
01/16
0
0

没有更多内容

加载失败,请刷新页面

加载更多

C++ std::function 和 std::bind

C++11提供了std::function和std::bind两个工具,用于引用可调用对象。这些可调用对象包括 普通函数,Lambda表达式,类的静态成员函数,非静态成员函数以及仿函数等。引用可调用对象,可以用于...

yepanl
37分钟前
0
0
python:可迭代对象的索引

关于 python的range的用法: 注意是[ 开始,结束)的半开区间,不包括结束 http://www.runoob.com/python/python-func-range.html import collectionsfrom collections import Iterable字符串......

Oh_really
52分钟前
2
0
docker-compose ,docker-stack

1.例子 version: "3"services: php: image: registry.cn-hangzhou.aliyuncs.com/lxepoo/apache-php5 ports: - "38080:80" networks: - my_php_mysql volum......

chenbaojun
今天
3
0
SQL_Server2000示例数据库NorthWind的分析(转)

SQL_Server2000示例数据库NorthWind的分析 表名:Categories(食品类别表) 表结构: 字段名称 数据类型 长度 允许为空 CategoryID(主键) int 4 否 CategoryName nvarchar 15 否 Description ...

QQZZFT
今天
1
0
laravel 5.5 Session store not set on request.

laravel 5.5 数据存入session,会出现Session store not set on request.错误。查了下laravel 5.5将session放到global middleware中,需要laravel的文件 ./app/Http/Kernel.php中的加上一句:...

MichaelShu
今天
2
0

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部