面试题-Stack的最小值o(1)

 1 // Stack.cpp : 定义控制台应用程序的入口点。
 2 //
 3 
 4 #include "stdafx.h"
 5 #include <iostream>
 6 using namespace std;
 7 
 8 template <class Type>
 9 struct Stack
10 {
11 private:
12 Type *_stack;
13 int _top;
14 int _min;
15 int _size;
16 
17 
18 public:
19 Stack(const Type &size):_size(size),_top(0),_min(0)
20 {    
21 _stack = new Type[size];//(Type*)malloc(sizeof())
22 }
23 void push(const Type &value)
24 {
25 
26 if(_top == 0)
27 {
28 _min = value;
29 }
30 else if(_top == _size)
31 {
32 cout<<"Push failed,the stack is full"<<endl;
33 return;
34 }
35 _stack[_top++] = value-_min;
36 if(value < _min)
37 {    
38 _min = value;
39 }
40 
41 }
42 Type pop()
43 {
44 if(_top == 0)
45 {
46 cout<<"Pop failed,the stack is emply."<<endl;
47 return -1;
48 }
49 Type popvalue;
50 if(_stack[--_top]<0)
51 {
52 popvalue = _min;
53 _min = _min-_stack[_top];
54 }
55 else
56 {
57 popvalue = _min + _stack[_top];
58 }
59 return popvalue;
60 }
61 Type min()
62 {
63 return _min;
64 }
65 
66 };
67 
68 int _tmain(int argc, _TCHAR* argv[])
69 {
70 Stack<int> sk(30);
71 sk.push(8);
72 sk.push(7);
73 sk.push(6);
74 sk.push(5);
75 sk.push(9);
76 sk.push(4);
77 sk.push(3);
78 
79 cout<<sk.min()<<endl;//3
80 cout<<sk.pop()<<endl;//3
81 cout<<sk.min()<<endl;//4
82 cout<<sk.pop()<<endl;//4
83 cout<<sk.min()<<endl;//5
84 cout<<sk.pop()<<endl;//9
85 cout<<sk.min()<<endl;//5
86 cout<<sk.pop()<<endl;//5
87 cout<<sk.min()<<endl;//6
88 cout<<sk.pop()<<endl;//6
89 cout<<sk.min()<<endl;//7
90 cout<<sk.pop()<<endl;//7
91 cout<<sk.min()<<endl;//8
92 cout<<sk.pop()<<endl;//8
93 
94 return 0;
95 }
96 
97