スタックの最小要素を実現するmin関数
10316 ワード
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で終了します.各テストケースについて、入力された第1の動作は整数n(1<=n<=1000000)であり、nは入力する操作のステップ数を表す.次にn行があり、各行に1文字Ciが始まります.Ci=’s’の場合、kをスタックに押し込むことを表す数字kが続く.Ci=’o’の場合、スタックトップ要素がポップアップされます.
出力:
各テストケースの各操作に対応し、スタックが空でない場合は、対応するスタックの最小要素を出力します.そうでなければNULLを出力します.