剑指offer——面试题30：包含min函数的栈
1 #include"iostream" 2 #include"stdio.h" 3 using namespace std; 4 5 const int MAXN=1000; 6 const int INF=10000000; 7 8 template<typename T>class StackWithMin 9 { 10 public: 11 void push(const T& value); 12 void pop(); 13 T min(); 14 private: 15 int mSize=-1; 16 int minNum=INF; 17 T* mData=new T[MAXN]; 18 T* mMin=new T[MAXN]; 19 }; 20 21 template<typename T> void StackWithMin<T>::push(const T& value) 22 { 23 mData[++mSize]=value; 24 if(value<minNum) 25 { 26 minNum=value; 27 } 28 mMin[mSize]=minNum; 29 } 30 31 template<typename T>void StackWithMin<T>::pop() 32 { 33 if(mSize<0) 34 { 35 cout<<"stack is empty!"<<endl; 36 return; 37 } 38 mSize--; 39 } 40 41 template<typename T>T StackWithMin<T>::min() 42 { 43 if(mSize<0) 44 { 45 cout<<"stack is empty!"<<endl; 46 return INF; 47 } 48 return mMin[mSize]; 49 } 50 51 int main() 52 { 53 StackWithMin<double> s; 54 s.push(3); 55 cout<<s.min()<<endl; 56 s.push(4); 57 cout<<s.min()<<endl; 58 s.push(2); 59 cout<<s.min()<<endl; 60 s.push(1); 61 cout<<s.min()<<endl; 62 s.pop(); 63 cout<<s.min()<<endl; 64 s.pop(); 65 cout<<s.min()<<endl; 66 s.pop(); 67 cout<<s.min()<<endl; 68 s.pop(); 69 cout<<s.min()<<endl; 70 s.pop(); 71 cout<<s.min()<<endl; 72 73 return 0; 74 }
官方代码：
1 // 面试题30：包含min函数的栈 2 // 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min 3 // 函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。 4 5 #pragma once 6 7 #include <stack> 8 #include <assert.h> 9 10 template <typename T> class StackWithMin 11 { 12 public: 13 StackWithMin() {} 14 virtual ~StackWithMin() {} 15 16 T& top(); 17 const T& top() const; 18 19 void push(const T& value); 20 void pop(); 21 22 const T& min() const; 23 24 bool empty() const; 25 size_t size() const; 26 27 private: 28 std::stack<T> m_data; // 数据栈，存放栈的所有元素 29 std::stack<T> m_min; // 辅助栈，存放栈的最小元素 30 }; 31 32 template <typename T> void StackWithMin<T>::push(const T& value) 33 { 34 // 把新元素添加到辅助栈 35 m_data.push(value); 36 37 // 当新元素比之前的最小元素小时，把新元素插入辅助栈里； 38 // 否则把之前的最小元素重复插入辅助栈里 39 if(m_min.size() == 0 || value < m_min.top()) 40 m_min.push(value); 41 else 42 m_min.push(m_min.top()); 43 } 44 45 template <typename T> void StackWithMin<T>::pop() 46 { 47 assert(m_data.size() > 0 && m_min.size() > 0); 48 49 m_data.pop(); 50 m_min.pop(); 51 } 52 53 54 template <typename T> const T& StackWithMin<T>::min() const 55 { 56 assert(m_data.size() > 0 && m_min.size() > 0); 57 58 return m_min.top(); 59 } 60 61 template <typename T> T& StackWithMin<T>::top() 62 { 63 return m_data.top(); 64 } 65 66 template <typename T> const T& StackWithMin<T>::top() const 67 { 68 return m_data.top(); 69 } 70 71 template <typename T> bool StackWithMin<T>::empty() const 72 { 73 return m_data.empty(); 74 } 75 76 template <typename T> size_t StackWithMin<T>::size() const 77 { 78 return m_data.size(); 79 }