1522：包含min函数的栈 @jobdu

xitonga

浏览: 585390 次

最近访客更多访客>>

morelily

jccz_zys

haining128

u012363178

博主相关

博客

微博

相册

留言

关于我

文章分类

全部博客 (1278)

社区版块

存档分类

题目1522：包含min函数的栈

时间限制：1 秒

内存限制：128 兆

特殊判题：否

提交：488

解决：164

题目描述：

定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的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

样例输出：

两个栈s1,s2（保存最小元素），压栈时，先把元素压入s1，如果该元素比s2栈顶元素还要小，则也把该元素压入s2。

弹栈时，先把元素弹出s1，如果该元素等于s2栈顶元素，则也把该元素弹出s2。.

import java.io.BufferedInputStream;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.util.Scanner;
import java.util.Stack;


public class S21 {

	static Stack<Integer> s1;
	static Stack<Integer> s2;
	
	public static void main(String[] args) throws FileNotFoundException {
		BufferedInputStream in = new BufferedInputStream(new FileInputStream("in.in"));
		System.setIn(in);
		Scanner cin = new Scanner(System.in);
		
		while (cin.hasNextLine()) {
			int n = Integer.parseInt(cin.nextLine());
			s1 = new Stack<Integer>();
			s2 = new Stack<Integer>();
			for(int i=0; i<n; i++){
				String s = cin.nextLine();
				String[] ss = s.split(" ");
				if(ss[0].equals("s")){
					int val = Integer.parseInt(ss[1]);
					s1.push(val);
					if(s2.isEmpty() || val<s2.peek()){
						s2.push(val);
					}
				}else if(ss[0].equals("o")){
					int val = s1.pop();
					if(val == s2.peek()){
						s2.pop();
					}
				}
				if(s2.isEmpty()){
					System.out.println("NULL");
				}else{
					System.out.println(s2.peek());
				}
			}
		}
		
	}
	
	public static void push(){
		
	}
	
	
	
	
}

分享到：