分析:除了題目要求的棧之外新開一個棧,用來記錄最小值,每當在原棧中push數據後,與最小值棧中的棧頂元素比較,如果新值較小,則在最小值棧中push新值;否則再次push棧頂元素.pop的時候,只要將最小值棧也pop一下就行了.這樣,min函數只需要返回最小值棧的棧頂元素即可.
1 #include<stack> 2 #include<assert.h> 3 #include<stdio.h> 4 #include<tchar.h> 5 6 template<typename T>class StackWithMin 7 { 8 public: 9 StackWithMin(void) {} 10 virtual ~StackWithMin(void) {} 11 12 T& top(void); 13 const T& top(void) const; 14 15 void push(const T& value); 16 void pop(void); 17 18 const T& min(void) const; 19 20 bool empty() const; 21 size_t size() const; 22 23 private: 24 std::stack<T> m_data; 25 std::stack<T> m_min; 26 }; 27 28 template <typename T>void StackWithMin<T>::push(const T& value) 29 { 30 m_data.push(value); 31 32 if(m_min.size() == 0 || value < m_min.top()) 33 m_min.push(value); 34 else 35 m_min.push(m_min.top()); 36 } 37 38 39 template <typename T>void StackWithMin<T>::pop() 40 { 41 assert(m_data.size() > 0 && m_min.size() > 0); 42 43 m_data.pop(); 44 m_min.pop(); 45 } 46 47 template<typename T>const T& StackWithMin<T>::min() const 48 { 49 assert(m_data.size()>0 && m_min.size() >0); 50 51 return m_min.top(); 52 } 53 54 template<typename T>T& StackWithMin<T>::top() 55 { 56 return m_data.top(); 57 } 58 template <typename T>const T& StackWithMin<T>::top() const 59 { 60 return m_data.top(); 61 } 62 63 template <typename T> bool StackWithMin<T>::empty() const 64 { 65 return m_data.empty(); 66 } 67 68 template<typename T> size_t StackWithMin<T>::size() const 69 { 70 return m_data.size(); 71 } 72 73 void Test(char* testName, const StackWithMin<int>& stack, int expected) 74 { 75 if(testName != NULL) 76 printf("%s begins: \n", testName); 77 if(stack.min() == expected) 78 printf("Passed.\n"); 79 else 80 printf("Failed.\n"); 81 } 82 83 int main() 84 { 85 StackWithMin<int> stack; 86 stack.push(3); 87 printf("min = %d\n", stack.min()); 88 stack.push(4); 89 printf("min = %d\n", stack.min()); 90 stack.push(2); 91 printf("min = %d\n", stack.min()); 92 stack.pop(); 93 printf("min = %d\n", stack.min()); 94 95 return 0; 96 }