学步园

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

推荐指数：※※

来源：http://ac.jobdu.com/problem.php?pid=1522

这道题目是让在栈的操作基础上，在实现可以返回最小值的算法。直接想到的，就是在开一个最小值栈，要来记录每个次操作后的最小值。可参见海涛的博客： http://zhedahht.blog.163.com/blog/static/25411174200712895228171/

简单版本：

#include <iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
int main()
{
	int n,i;
	stack<int> st;
	stack<int> min_st;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		char ch[2];
		int tmp;
		scanf("%s",ch);
		if(ch[0]=='s'){
			scanf("%d",&tmp);
			if(min_st.empty()||min_st.top()>tmp){
				st.push(tmp);
				min_st.push(tmp);
			}else{
				st.push(tmp);
				min_st.push(min_st.top());
			}
		}
		else{
			if(!st.empty()){
				st.pop();
				min_st.pop();
			}	
		}
		if(!min_st.empty())
			printf("%d\n",min_st.top());
		else
			printf("NULL\n");
	}
	return 0;	
}
但这在空间上需要O（n）,看了@anchor89 提出http://blog.csdn.net/anchor89/article/details/6055412空间O(1）的方法，值得学习。
这个算法的本质是让栈顶的元素带有更多的信息。通过运算（tmp-min)，是的正负号带有的是否是min的信息。
#include<iostream>
#include<stdio.h>
#include<string.h>
#include<stack>
using namespace std;
int main()
{
int n,i;
	stack<int> st;
	int min;
	scanf("%d",&n);
	for(i=0;i<n;i++){
		char ch[2];
		int tmp;
		scanf("%s",ch);
		if(ch[0]=='s'){
			scanf("%d",&tmp);
			if(st.empty()){
				st.push(tmp);
				min=tmp;
			}
			else if(tmp<min)
			{
				st.push(tmp-min);
				min=tmp;
			}
			else{
				st.push(tmp);
			}
		}
		else{
			if(!st.empty()){
				if(st.top()<0)
					min=min-st.top();
				st.pop();
			}	
		}
		if(!st.empty())
			printf("%d\n",min);
		else
			printf("NULL\n");
	}
	return 0;	
}