面试题-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