【题目】实现一个特殊的栈，在实现栈的基本功能上再实现一个实现返回栈中最小元素的操作。
【要求】
1，pop、push、getMin操作的时间复杂度都是O（1）；
2，设计的栈类型额可以使用现成的栈结构。

第一种代码实现：

public class GetMinStack_1 {

    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public GetMinStack_1(){
        stackData = new Stack<Integer>();
        stackMin = new Stack<Integer>();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        if (value == getMin()) {
            stackMin.pop();
        }
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_1 stack = new GetMinStack_1();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }

}

第二种代码实现 ：

public class GetMinStack_2 {

    private Stack<Integer> stackData;
    private Stack<Integer> stackMin;

    public GetMinStack_2(){
        stackData = new Stack<Integer>();
        stackMin = new Stack<Integer>();
    }

    public void push(int newNum){
        if (stackMin.isEmpty()) {
            stackMin.push(newNum);
        }
        else if (newNum <= getMin()) {
            stackMin.push(newNum);
        }else {
            stackMin.push(getMin());
        }
        stackData.push(newNum);
    }

    public int pop(){
        if (stackData.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        int value = stackData.pop();
        stackMin.pop();
        return value;
    }

    private int getMin() {
        // TODO Auto-generated method stub
        if (stackMin.isEmpty()) {
            System.out.println("stack is empty");
            return -1;
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub

        GetMinStack_2 stack = new GetMinStack_2();
        int[] testNum = {4,2,4,6,5,0,1,10};
        for(int i:testNum){
            stack.push(i);
        }
        for(int i = 0; i < testNum.length; i++){
            System.out.println(stack.getMin()+" "+stack.pop());
        }
    }
}