剑指offer30:包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈中所含最小元素的min函数（时间复杂度应为O（1）.

思路：对于栈，要在O(1)时间内获得最小元素. 且最小元素要根据进栈出栈动态改变. 当栈为空时，插入一个元素，最小值为此元素. 当插入一个更小的元素时，最小值更新,若此时将新插入的元素出栈，则最小值需要恢复成第一个元素. 因此，最小值元素可用另一个栈来存放，栈顶为当前最小值，存放值的栈每次出栈时对比，若出栈元素为最小值，则将当前最小值从最小值栈弹出.

class Min_stack
{
private:
    stack<int> values;
    stack<int> min_val;
public:
    void push(int value) {
        if(min_val.empty())
            min_val.push(value);
        else{
            int top_min = min_val.top();
            if(value<=top_min)
                min_val.push(value);
        }
        values.push(value);
    }
    void pop() {
        int top = values.top();
        int top_min = min_val.top();
        if(top==top_min)
            min_val.pop();
        values.pop();
    }
    int top() {
        return values.top();
    }
    int min() {
        return min_val.top();
    }
};