//O(1)时间找到栈中最小元素
#include <iostream>
#include<stack>
#include<assert.h>
using namespace std;
template <typename T> class StackWithMin{
public:
    StackWithMin(void){};
    ~StackWithMin(void) {};
    void push(const T& value);
    void pop();
   const T minV();
private:
    stack<T> m_data;//原始的数据栈
    stack<T> m_min;//存放每次 压入栈的最小值
};
template <typename T> void StackWithMin<T>::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());//比如m_data 有的是3,4 ,那么m_min就会相应的是 3 3
}
template <typename T> void StackWithMin<T>::pop(){
    assert(m_data.size()>0 && m_min.size()>0);
    m_data.pop();
    m_min.pop();
}
template <typename T>const T StackWithMin<T>::minV(){
    assert(m_data.size()>0&& m_min.size()>0);
    return m_min.top();
}
int main()
{
    StackWithMin<int> s;
    s.push(3);
    s.push(4);
    s.push(2);
    s.push(1);
    cout<<s.minV();
    cout<<endl;
    s.pop();
    cout<<s.minV();
    cout<<endl;
    s.pop();
    cout<<s.minV();
    cout<<endl;
    s.push(0);
    cout<<s.minV();
    cout<<endl;
    return 0;
}