题目描述(ID:12289)
标题: 最大栈
标签: 数据结构
详情: Artanis已经学会了栈的基本操作,于是去找Zeratul炫耀。为了打击Artanis的嚣张气焰,Zeratul给Artanis出了一道有关栈的习题:要求Artanis在实现一个栈的Push/Pop/Top操作同时,再实现一个查询栈中最大值的Max操作。这可难坏了Artanis。于是Artanis来找聪明的你求助,相信你一定能解决这个问题。
输入格式:
第一行是一个整数q。
接下来q行,每行代表一组操作。操作有如下四种:
pop:代表删除栈顶元素
push x:代表将x压入栈顶(x是int范围内的整数)
top:代表查询栈顶元素
max:代表查询栈中最大值
输出格式:
对于每个top和max操作,输出一行代表查询的结果。
限制: 对于50%的测试点,q<=1000;
对于80%的测试点,q<=100000;
对于100%的测试点,q<=2000000。
样例:

输入

6
push 1
push 2
max
pop
max
top

输出

2
1
1

解释

第一次操作之后,栈中元素只有1;
第二次操作之后,栈中元素为1、2;
第三次操作查询栈中最大值,结果为2,所以输出2;
第四次操作删除栈顶元素2,操作后栈中元素只有1;
第五次操作查询栈中最大值,结果为1,所以输出1;
第六次操作查询栈顶元素,结果为1,所以输出1。

输入

6
push 1
push 2
push 2
max
pop
max

输出

2
2
登录并解答