最小栈的实现

实现一个栈，该栈带有出栈（pop），进栈（push），取最小元素（getMin）3个方法，保证时间复杂度为O(1).

如果只声明一个变量储存最小值是不够的，因为如果最小值出栈的话，怎么更新？
因而，我们需要储存栈中 曾经的最小值，作为“备胎”

解法步骤

1. 设原有栈为A，此时创建个额外的“备胎”栈B，用于辅助栈A。
2. 当第一个元素进入栈A时，让新元素也进入栈B。因为这个唯一的元素时栈A目前最小值。
3. 之后，每当新元素入栈A时，比较 新元素 和 栈A目前最小值 的大小，如果小于 栈A目前的最小值，则让新元素也入栈B，此时 栈B的栈顶元素 是 栈A当前最小值。
4. 每当有栈A的元素出栈，如果 出栈元素 和 栈B栈顶元素 相同时，栈B栈顶元素也出栈，则接下去栈B栈顶元素变为栈A目前最小值，“备胎转正”。
5. 当调用getMin()时，返回 栈B的栈顶元素 ，这就是栈A目前最小值。

• 时间复杂度均是O(1)，最坏情况的空间复杂度为O(n)

实现

private Stack<Integer> mainStack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();

public void push(int element){
    mainStack.push(element);
    if(minStack.empty() || element <= minStack.peek())
        minStack.push(element);
}

public Integer pop(){
    if(mainStack.peek().equals(minStack.peek()))
        minStack.pop();
    return mainStack.pop();
}

public int getMin() throws Exception {
    if(mainStack.empty())
        throw new Exception("stack is empty");
    
    return minStack.peek();
}