30. 包含min的函数栈(√)

题目要求：自定义栈的数据结构
实现push、pop、min函数，其中min函数可以得到栈中的最小元素
要求：调用 min、push 及 pop 的时间复杂度都是 O(1)

解题思路：
创建两个栈，栈1用来保证基础的push、pop、top操作，栈2用来实现min函数的功能。
其中栈2的思路：只压入比栈2栈顶小的元素（如果当前元素比栈2栈顶大，可以理解为：它是否弹出对min函数没有任何贡献）

图解

C++

class MinStack {
public:
    /** initialize your data structure here. */
    MinStack() {
    }
    
    void push(int x) {
        s.push(x);
        if(min_s.empty() || x <= min_s.top()) min_s.push(x);
    }
    
    void pop() {
        if(!s.empty()){
            if(s.top() == min_s.top()){
                s.pop();
                min_s.pop();
            }else s.pop();
        }  
    }
    
    int top() {
        if(!s.empty()) return s.top();
        else return NULL;
    }
    
    int min() {
        if(!min_s.empty()) return min_s.top();
        else return NULL;
    }
    stack<int> min_s;
    stack<int> s;
};

Java

class MinStack {

    /** initialize your data structure here. */
    public MinStack() {
        s1 = new LinkedList<Integer>();
        s2 = new LinkedList<Integer>();
    }
    
    public void push(int x) {
        s1.addLast(x);
        if(s2.isEmpty() || !s2.isEmpty() && s2.getLast() >= x) s2.addLast(x);
    }
    
    public void pop() {
        int e = s1.removeLast();
        if(e == s2.getLast()) s2.removeLast();
    }
    
    public int top() {
        return s1.getLast();
    }
    
    public int min() {
        return s2.getLast();
    }
    LinkedList<Integer> s1;
    LinkedList<Integer> s2;
}