面试题21：包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min，push及pop函数的时间复杂度都是O(1)。

分析

栈应该是我们很熟悉的一种数据结构了，它是一种“后进先出”的数据结构，并且只能在栈的一端(栈顶)进行操作。所以其push和pop操作的时间复杂度都是O(1)。如果题目没有要求min函数的时间复杂度的话，我们可以在min函数里面遍历所有的元素并将其保存起来，找到最小的元素后再将所有元素以相反的顺序放回去。但现在这种方案显然不行。

我们可以定义两个栈，一个存放我们需要的元素，称为元素栈。另一个存放当前元素栈里面最小的一个元素值，称为最小值栈。这样，当调用min函数时，直接返回最小值栈的栈顶就可以了，达到了O(1)的时间复杂度。这是一个“以空间换时间”的方法。

这样，在插入元素时，先将其插入元素栈里，并判断该元素是否小于最小值栈的栈顶元素，若小于，则将该元素插入最小值栈，否则，将最小值栈的栈顶元素在此插入最小值栈。pop时，两个都pop即可。

代码如下：

class StackIsEmpty{};

template<typename T>
class MyStack{
public:
    void push(const T& t)
    {
        if(s.empty())
        {
            m.push(t);
        }
        else
        {
            if(t<m.top())
            {
                m.push(t);
            }
            else
            {
                m.push(m.top());
            }
        }
        s.push(t);
    }
    void pop()
    {
        if(!s.empty())
        {
            s.pop();
            m.pop();
        }
        else
            throw StackIsEmpty();
    }
    T& min()
    {
        if(!s.empty())
        {
            return m.top();
        }
        else
            throw StackIsEmpty();
    }
    bool empty()
    {
        return s.empty();
    }
private:
    stack<T> s;
    stack<T> m;//min
};

以上

如果你有任何想法或是可以改进的地方，欢迎和我交流！

完整代码及测试用例在github上：点我前往