// 面试题30：包含min函数的栈

// 题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min

// 函数。在该栈中，调用min、push及pop的时间复杂度都是O(1)。

#include <iostream>

#include <stack>

#include <assert.h>

//////////////////////////定义一个模板类///////////////////////////

template <typename T> 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<T>   m_data;     // 数据栈，存放栈的所有元素

    std::stack<T>   m_min;      // 辅助栈，存放栈的最小元素

};

template <typename T> void StackWithMin<T>::push(const T& value)//模板类的构造函数，好好看看这一行怎么写的

{

    // 把新元素添加到辅助栈

    m_data.push(value);

    // 当新元素比之前的最小元素小时，把新元素插入辅助栈里；

    // 否则把之前的最小元素重复插入辅助栈里

    if (m_min.size() ==  || value < m_min.top())

        m_min.push(value);

    else

        m_min.push(m_min.top());

}

template <typename T> void StackWithMin<T>::pop()//删除顶节点

{

    assert(m_data.size() >  && m_min.size() > );//检测括号中的话是真的不

    m_data.pop();

    m_min.pop();

}

template <typename T> const T& StackWithMin<T>::min() const//返回辅助栈的顶点

{

    assert(m_data.size() >  && m_min.size() > );

    return m_min.top();

}

//template <typename T> T& StackWithMin<T>::top()

//{

//    return m_data.top();

//}

template <typename T> const T& StackWithMin<T>::top() const//返回数据栈的顶点

{

    return m_data.top();

}

template <typename T> bool StackWithMin<T>::empty() const//检测数据栈空否

{

    return m_data.empty();

}

template <typename T> size_t StackWithMin<T>::size() const//返回数据栈size

{

    return m_data.size();

}

//////////////////////////测试代码///////////////////////////

void Test(const char* testName, const StackWithMin<int>& 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<int> stack;

    stack.push();

    Test("Test1", stack, );

    stack.push();

    Test("Test2", stack, );

    stack.push();

    Test("Test3", stack, );

    stack.push();

    Test("Test4", stack, );

    stack.pop();

    Test("Test5", stack, );

    stack.pop();

    Test("Test6", stack, );

    stack.pop();

    Test("Test7", stack, );

    stack.push();

    Test("Test8", stack, );

    system("pause");

    return ;

}