1
#include<iostream>
2
#include<stack>
3
using
namespace
std;
4
class
min_stack
5
{
6
public
:
7
void
push(
int
);
8
void
pop();
9
int
min();
10
int
size()
11
{
12
return
data.size();
13
}
14
private
:
15
stack<
int
>
data;
16
stack<
int
>
min_data;
17
};
18
void
min_stack::push(
int
value)
19
{
20
data.push(value);
21
if
(min_data.size()==
0
|| min_data.top() >
value)
22
{
23
min_data.push(value);
24
}
25
else
26
{
27
min_data.push(min_data.top());
28
}
29
}
30
void
min_stack::pop()
31
{
32
if
(data.size()>
0
)
33
{
34
min_data.pop();
35
data.pop();
36
}
37
}
38
int
min_stack::min()
39
{
40
return
min_data.top();
41
}
42
43
int
main(
int
argc,
char
**
argv)
44
{
45
int
n,m;
46
char
ci;
47
while
(cin>>
n)
48
{
49
min_stack mystack;
50
for
(
int
i=
0
; i<n; i++
)
51
{
52
cin>>
ci;
53
switch
(ci)
54
{
55
case
'
s
'
:
56
cin>>
m;
57
mystack.push(m);
58
cout<<mystack.min()<<
endl;
59
break
;
60
case
'
o
'
:
61
mystack.pop();
62
if
(mystack.size()==
0
)
63
{
64
cout<<
"
NULL
"
<<
endl;
65
}
66
else
67
{
68
cout<<mystack.min()<<
endl;
69
}
70
break
;
71
}
72
}
73
}
74
return
1
;
75
}
76
/*
*************************************************************
77
Problem: 1522
78
User: xuebintian
79
Language: C++
80
Result: Accepted
81
Time:140 ms
82
Memory:1524 kb
83
***************************************************************
*/
- 题目描述：
-
定义栈的数据结构，请在该类型中实现一个能够得到栈最小元素的min函数。
- 输入：
-
输入可能包含多个测试样例，输入以EOF结束。
对于每个测试案例，输入的第一行为一个整数n(1<=n<=1000000)， n代表将要输入的操作的步骤数。
接下来有n行，每行开始有一个字母Ci。
Ci=’s’时，接下有一个数字k，代表将k压入栈。
Ci=’o’时，弹出栈顶元素。
- 输出：
-
对应每个测试案例中的每个操作，
若栈不为空，输出相应的栈中最小元素。否则，输出NULL。
