栈--最小栈问题

设计一个支持 push，pop，top 操作，并能在常数时间内检索到最小元素的栈。
push(x) -- 将元素 x 推入栈中。
pop() -- 删除栈顶的元素。
top() -- 获取栈顶元素。
getMin() -- 检索栈中的最小元素。

MinStack minStack = new MinStack();
minStack.push(-2);
minStack.push(0);
minStack.push(-3);
minStack.getMin(); --> 返回 -3.
minStack.pop();
minStack.top(); --> 返回 0.
minStack.getMin(); --> 返回 -2.

自己实现栈解决：如果pop为最小元素，则刷新

private static class MinStackNode {

        private int val;

        //下一结点
        private MinStackNode next;

        public MinStackNode(int val) {
            this.val = val;
        }

    }

    //栈顶元素
    private MinStackNode top;

    //最小元素结点
    private MinStackNode min;

    /**
     * initialize your data structure here.
     */
    public MinStack() {
        top = null;
        min = null;
    }

    public void push(int x) {
        MinStackNode node = new MinStackNode(x);
        if (top == null) {
            top = node;
            min = node;
        } else {
            node.next = top;
            top = node;
            refresh();
        }

    }

    public void pop() {
        //栈顶元素为空，为空栈
        if (top == null) {
            throw new RuntimeException("栈空");
        }

        //如果删除的是最小元素，则刷新
        if(top == min){
            min = null;
        }

        top = top.next;
        refresh();

    }

    private void refresh() {
        if (top == null) {
            return;
        }

        MinStackNode stackNode = top;
        while (stackNode != null) {

            if (min == null) {
                min = stackNode;
            } else {
                if (min.val > stackNode.val) {
                    min = stackNode;
                }
            }
            stackNode = stackNode.next;
        }
    }

    public int top() {
        //栈顶元素为空，为空栈
        if (top == null) {
            throw new RuntimeException("栈空");
        }
        return top.val;
    }

    public int getMin() {

        //栈顶元素为空，为空栈
        if (top == null) {
            throw new RuntimeException("栈空");
        }

        return min.val;

    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(1);
        minStack.push(2);
        minStack.push(0);
        System.out.println(minStack.top());


        minStack.pop();
        System.out.println(minStack.getMin());
    }

借用Stack实现。使用双栈存储。一个存储数据，一个存储最小值：

//存放入栈数据
    private Stack<Integer> first;

    //存放最小值数据
    private Stack<Integer> second;

    public MinStack2() {
        first = new Stack<>();
        second = new Stack<>();
    }

    public void push(int x) {
        first.add(x);
        
        //second存放比栈顶元素小，或者相等的元素
        if (second.isEmpty() || second.peek() >= x) {
            second.add(x);
        }
    }

    public void pop() {
        if (!first.isEmpty()) {
            //如果first栈顶元素的值等于second元素的栈顶值，则second也弹出
            int top = first.pop();
            if (top == second.peek()) {
                second.pop();
            }
        }

    }

    public int top() {
        if (first.isEmpty()) {
            throw new RuntimeException("为空");
        }

        return first.peek();
    }

    public int getMin() {
        if (second.isEmpty()) {
            throw new RuntimeException("为空");
        }

        return second.peek();

    }