数据结构篇-02：最小栈

 对于这道题，除了 getMin 外的功能，传统的 栈 结构中都有，所以重点在于如何实现 getMin 方法。

有两类方法：使用辅助栈/不使用辅助栈

使用辅助栈的解法一

定义一个 栈 来实现常规功能，另外定义一个栈（最小栈）专门用于实现 getMin 方法

使得 [最小栈] 的栈顶始终都是当前栈中的最小元素即可

class MinStack {
    private Stack<Integer> dataStack;
    private Stack<Integer> minStack;
    
    public MinStack() {
        dataStack = new Stack<>();
        minStack = new Stack<>();
    }
    
    public void push(int x) {
        // 先将 x 压入数据栈
        dataStack.push(x);
        // 如果 x 是当前的最小值，则也需要将 x 压入辅助栈
        if (minStack.isEmpty() || x <= minStack.peek()) {
            minStack.push(x);
        }
    }
    
    public void pop() {
        // 先删除数据栈的栈顶元素 x
        int x = dataStack.pop();
        // 若 x 是当前的最小值，则也需要删除辅助栈的栈顶元素
        if (x == minStack.peek()) {
            minStack.pop();
        }
    }
    
    public int top() {
        return dataStack.peek();
    }
    
    public int getMin() {
        return minStack.peek();
    }
}

 不使用辅助栈的解法一

不使用辅助栈的话，就需要额外保存当前的最小值

定义一个节点类Node，里面除了保存有当前元素外，还包含当前的最小元素。这样当需要最小元素时，直接弹出栈顶元素，然后获取栈顶元素中的最小值即可。 

class MinStack {

    private Stack<Node> stack;

    public MinStack() {
        stack = new Stack<>();
    }
    
    public void push(int x) {
        // 将元素值 x 和 当前最小值 同时入栈。
        if (stack.isEmpty()) {
            stack.push(new Node(x, x));
        } else {
            stack.push(new Node(x, Math.min(x, stack.peek().min)));
        }
    }
    
    public void pop() {
        stack.pop();
    }
    
    public int top() {
        // 返回栈顶元素中的元素值。
        return stack.peek().val;
    }
    
    public int getMin() {
        // 返回栈顶元素的最小值
        return stack.peek().min;
    }

    private static class Node {
        int val;
        int min;

        public Node(int val, int min) {
            this.val = val;
            this.min = min;
        }
    }
}