// 面试题30：包含min函数的栈// 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min// 函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。#include 
     
      #include 
      
       #include 
       
        //定义一个模板类///template 
        
          class StackWithMin{public:    StackWithMin() {}    virtual ~StackWithMin() {}//虚析构函数    //T& top();    const T& top() const;    void push(const T& value);    void pop();    const T& min() const;    bool empty() const;    size_t size() const;private:    std::stack
         
             m_data;     // 数据栈，存放栈的所有元素    std::stack
          
            m_min; // 辅助栈，存放栈的最小元素};template 
           
             void StackWithMin
            
             ::push(const T& value)//模板类的构造函数，好好看看这一行怎么写的{ // 把新元素添加到辅助栈 m_data.push(value); // 当新元素比之前的最小元素小时，把新元素插入辅助栈里； // 否则把之前的最小元素重复插入辅助栈里 if (m_min.size() == 0 || value < m_min.top()) m_min.push(value); else m_min.push(m_min.top());}template 
             
               void StackWithMin
              
               ::pop()//删除顶节点{ assert(m_data.size() > 0 && m_min.size() > 0);//检测括号中的话是真的不 m_data.pop(); m_min.pop();}template 
               
                 const T& StackWithMin
                
                 ::min() const//返回辅助栈的顶点{ assert(m_data.size() > 0 && m_min.size() > 0); return m_min.top();}//template 
                 
                   T& StackWithMin
                  
                   ::top()//{// return m_data.top();//}template 
                   
                     const T& StackWithMin
                    
                     ::top() const//返回数据栈的顶点{ return m_data.top();}template 
                     
                       bool StackWithMin
                      
                       ::empty() const//检测数据栈空否{ return m_data.empty();}template 
                       
                         size_t StackWithMin
                        
                         ::size() const//返回数据栈size{ return m_data.size();}//测试代码///void Test(const char* testName, const StackWithMin
                         
                          & stack, int expected){ if (testName != nullptr) printf("%s begins: ", testName); if (stack.min() == expected) printf("Passed.\n"); else printf("Failed.\n");}int main(int argc, char* argv[]){ StackWithMin
                          
                            stack; stack.push(3); Test("Test1", stack, 3); stack.push(4); Test("Test2", stack, 3); stack.push(2); Test("Test3", stack, 2); stack.push(3); Test("Test4", stack, 2); stack.pop(); Test("Test5", stack, 2); stack.pop(); Test("Test6", stack, 3); stack.pop(); Test("Test7", stack, 3); stack.push(0); Test("Test8", stack, 0); system("pause"); return 0;}