设计一个具有getMin功能的栈

要求：

• 1、pop、push、getMin操作时间复杂度都是O(1)
• 2、设计的栈类型可以使用现有的栈

解法1

import java.util.Stack;

public class GetMinStack {

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

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

    public Integer pop() {
        if (stackData.isEmpty()) {
            throw new RuntimeException("Stack is Empty!");
        }
        int val = stackData.pop();
        if (val == getMin()) {
            stackMin.pop();
        }
        return val;
    }

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

    public Integer getMin() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Stack is Empty!");
        }
        return stackMin.peek();
    }

}

解法2

import java.util.Stack;

public class GetMinStack2 {

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

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

    public Integer pop() {
        if (stackData.isEmpty()) {
            throw new RuntimeException("Stack is Empty!");
        }
        stackMin.pop();
        return stackData.pop();
    }

    public void push(Integer val) {
        if (stackMin.isEmpty()) {
            stackMin.push(val);
        } else if(val <= getMin()){
            stackMin.push(val);
        } else {
            int min = stackMin.peek();
            stackMin.push(min);
        }
        stackData.push(val);
    }

    public Integer getMin() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Stack is Empty!");
        }
        return stackMin.peek();
    }
}