包含min函数的栈

题目：

​ 定义栈的数据结构，请在该类型中实现一个能够得到栈的最小元素的min函数。在该栈中，调用min、push及pop的时间复杂度都是 O(1)。

分析：

​ 看到这个问题，第一反应是每次压入一个元素进栈都将栈里的元素排序，让最小的元素位于栈顶，这样 min 函数的事件复杂度就是 O(1) 了。但这种方法没法保证最后压入的元素最先出栈，因此这种数据结构已经不是栈了。

​ 接着想到使用一个成员变量存放最小的元素。每次压入一个新元素时，如果该元素比当前最小元素还要小，则更新最小的元素。最小元素弹出之后要能得到次小元素，因此也要把第二次小的元素保存起来。

​ 下面表格使用一个数据栈和一个辅助栈来保存元素，每次压入元素时要保存到数据栈，辅助栈里面保存有序的元素，min 使用辅助栈来获取元素，保证 O(1) 时间复杂度。

步骤	操作	数据栈	辅助栈	最小值
1	压入3	3	3	3
2	压入4	3, 4	3, 3	3
3	压入2	3, 4, 2	3, 3, 2	2
4	压入1	3, 4, 2, 1	3, 3, 2, 1	1
5	弹出	3, 4, 2	3, 3, 2	2
6	弹出	3, 4	3, 3	3
7	压入0	3, 4, 0	3, 3, 0	0

代码：

public class StackWithMin {

    private static Stack<Integer> data_stack = new Stack();
    private static Stack<Integer> min_stack = new Stack();

    public static void push(Integer num) {
        data_stack.push(num);

        if (min_stack.size() == 0 || num < min_stack.peek()) {
            min_stack.push(num);
        }else{
            min_stack.push(min_stack.peek());
        }
    }

    public static void pop() {
        data_stack.pop();
        min_stack.pop();
    }

    public static Integer min() {
        return min_stack.peek();
    }
}

测试：

@Test
public void test() {
    StackWithMin.push(3);
    StackWithMin.push(4);
    StackWithMin.push(2);
    System.out.println(StackWithMin.min());
    StackWithMin.pop();
    System.out.println(StackWithMin.min());
    StackWithMin.push(5);
    System.out.println(StackWithMin.min());
    StackWithMin.pop();
    System.out.println(StackWithMin.min());
    StackWithMin.push(1);
    StackWithMin.push(0);
    System.out.println(StackWithMin.min());
}