栈系列之-获取最小值

2019-11-29 本文已影响0人愤怒的谜团

一、栈获取最小值算法概述

获取栈的最小值算法：可以动态的获取一个栈中元素的最小值，动态的意思是，当该栈发生push或者pop操作，可能会导致最小值发生改变。实现该算法需要用到一个辅助栈，专门用于保存栈的最小值动态变化值。
实现步骤如下：

需要借助一个辅助栈，minStack，主栈为mainStack，初始两个栈都是空栈。
当需要往mainStack插入元素时，如果minStack为空，直接插入。
如果minStack不为空，则将要插入的元素elem与minStack.peek()进行比较，若elem<minStack.peek(),则同时插入到minStack和mainStack，若elem>minStack.peek()，则elem照常插入到mainStack当中，然后将minStack.push(minStack.peek())
当mianStack弹出元素时，minStack也同步弹出。
取mianStack当前最小值直接minStack.peek()就好了。

二、栈获取最小值算法实现

import java.util.Stack;

public class MinStack {
    Stack<Integer> minStack;
    Stack<Integer> mianStack;
    public MinStack(){
        this.minStack = new Stack<Integer>();
        this.mianStack = new Stack<Integer>();
    }

    public void push(Integer elem){
        if (minStack.isEmpty() && mianStack.isEmpty()){
            mianStack.push(elem);
            minStack.push(elem);
        }else if (elem < minStack.peek()){
            mianStack.push(elem);
            minStack.push(elem);
        }else if (elem > minStack.peek()){
            mianStack.push(elem);
            minStack.push(minStack.peek());
        }
    }

    public void pop(){
        if (mianStack.isEmpty() && minStack.isEmpty()){return;}
        mianStack.pop();
        minStack.pop();
    }

    public Integer getMinElem(){
        if (minStack.isEmpty()){return null;}
        else{
            return minStack.peek();
        }
    }

    public String toString(){
        return minStack.toString();
    }

    public static void main(String[] args) {
        MinStack minStack = new MinStack();
        minStack.push(4);
        minStack.push(3);
        minStack.push(5);
        System.out.println(minStack.toString());
        System.out.println(minStack.getMinElem());
    }
}