海涛老师的面试题作业21包含min函数的栈

View Code
  1 // 包含min函数的栈.cpp : 定义控制台应用程序的入口点。
  2 //
  3 /*****************************************
  4 
  5     设计者：cslave
  6     版本说明：本代码免费用于商用，拷贝，转移，使用，但是
  7     有本代码导致的问题，本人概不负责。
  8     设计时间：2012.6.29
  9     分发原则：遵守GNU规范。
 10 
 11 *******************************************/
 12 
 13 #include "stdafx.h"
 14 #include  <stack>
 15 #include  <iostream>
 16 using namespace std;
 17 
 18 
 19 template <typename T>
 20 class StackWithMin
 21 {
 22 public:
 23     StackWithMin();
 24     ~StackWithMin();
 25     void push(const T& value);
 26     void pop();
 27     const T& min();
 28     const T& top();
 29 private:
 30     stack<T> m_data;//元素栈
 31     stack<T> m_min; //小值栈
 32 };
 33 
 34 
 35 template <typename T>
 36 StackWithMin<T>::StackWithMin()
 37 {
 38 
 39 }
 40 
 41 template <typename T>
 42 StackWithMin<T>::~StackWithMin()
 43 {
 44 
 45 }
 46 
 47 template <typename T>
 48 void StackWithMin<T>::push(const T& value) //仅当推进值小于小值栈栈顶元素或者小值栈为空时可以推进。
 49 {
 50     m_data.push(value);
 51     if(m_min.size()==0||m_min.top()>value)
 52         m_min.push(value);
 53     else
 54         m_min.push(m_min.top());
 55 }
 56 
 57 template <typename T>
 58 void StackWithMin<T>::pop() //必须栈非空才能执行拉出操作
 59 {
 60     if(m_data.size()>0 &&m_min.size()>0)
 61     {
 62         m_data.pop();
 63         m_min.pop();
 64     }
 65     else
 66         throw  exception("StackWithMin Is Empty！");
 67 }
 68 
 69 
 70 template <typename T>
 71 const T& StackWithMin<T>::min() //得到最小元素
 72 {
 73     if(m_data.size()>0&&m_min.size()>0)
 74         return m_min.top();
 75     else
 76         throw exception("Empty! Nothing to Min!");
 77 }
 78 
 79 
 80 
 81 template <typename T>
 82 const T& StackWithMin<T>::top() //反应栈顶元素
 83 {
 84     if(m_data.size()>0&&m_min.size()>0)
 85         return m_data.top();
 86     else
 87         throw  exception("StackWithMin Is Empty!");
 88 }
 89 
 90 
 91 
 92 void Test()
 93 {
 94     StackWithMin<int> stack;
 95     stack.push(5);
 96     stack.push(7);
 97     stack.push(3);
 98     stack.push(6);
 99     stack.push(2);
100     int min=stack.min();
101     cout<<"期望值为 2！"<<endl;
102     cout<<min<<endl;
103     stack.pop();
104     min=stack.min();
105     cout<<"期望值为 3！"<<endl;
106     cout<<min<<endl;
107     min=stack.min();
108     cout<<"期望值为 3！"<<endl;
109     cout<<min<<endl;
110     min=stack.top();
111     cout<<"期望值为 6！"<<endl;
112     cout<<min<<endl;
113 
114     try
115     {
116         stack.pop();
117         stack.pop();
118         stack.pop();
119         stack.pop();
120     //    min=stack.min();
121         min=stack.top();
122     }
123     catch(exception& exception)
124     {
125         cout<<exception.what()<<endl;
126     }
127 
128 }
129 int _tmain(int argc, _TCHAR* argv[])
130 {
131    Test();
132     return 0;
133 }