Java 数据结构 最小栈的实现

在O（N）时间复杂度内找出最小值：

1. 创建两个栈
2. 当普通栈只有一个数据时，把该数据放入最小栈
3. 往普通栈放入数据时，把要放入的数据和最小栈的栈顶数据相比较，若要放入的数据比最小栈的栈顶数据小，则把该数据放入最小栈
4. 需要找栈的最小值时，直接取栈顶数据

入栈（push）操作小结：

• 普通栈一定要放，最小栈放的原则是：
• 最小栈为空，放
• 若当前元素比最小栈栈顶元素小，则放

问题：如果要放的元素  等于  最小栈栈顶元素，要放吗？

答：要放

理由：这涉及到出栈（pop）操作，如果pop把最上面的-2出出去了，最小栈栈顶的-2也会出去，但是实际上普通栈内还有一个最小的值-2，但最小栈栈顶已经不是-2了

 出栈（pop）操作小结：

• 需要判断  出栈的元素  和 最小栈栈顶的元素 是否相同，相同则最小栈也要出栈

import java.util.Stack;

//最小栈代码实现
public class Minstack {
    public Stack<Integer> stack;
    public Stack<Integer> minStack1;

    public Minstack(){
stack=new Stack<>();
minStack1=new Stack<>();
    }



    public void push(int val){//入栈操作
stack.push(val);//由于普通栈是一定要放的
        if(minStack1.empty()){//如果最小栈是空的，则往里放
            minStack1.push(val);
        }else {//当最小栈不为空时，放入的元素要和最小栈的栈顶元素去比较，小于等于栈顶则放入最小栈
            int peekVal=minStack1.peek();//先拿到最小栈栈顶元素
            if(val<=peekVal){
                minStack1.push(val);
            }

        }
    }


    public void pop(){//出栈操作
        if(stack.empty()){//如果栈为空，无法出栈
            return;
        }
        //如果栈不为空，先判断两栈顶元素是否相同，相同则最小栈的栈顶也出出去
        int popVal=stack.pop();
        if(popVal==minStack1.peek()){
            minStack1.pop();
        }



    }


    public int top(){//获取普通栈的栈顶元素
        if(stack.empty()){//如果栈为空，无法出栈，此时应该要报一个异常
            return -1;
        }
        return stack.peek();
    }

    public int getMin(){
        if(minStack1.empty()){//如果栈为空，无法出栈，此时应该要报一个异常
            return -1;
        }
        return minStack1.peek();
    }
}