算法之路_18、实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作

题目:实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返 回栈中最小元素的操作。 

【要求】 

1．pop、push、getMin操作的时间复杂度都是O(1)。 

2．设计的栈类型可以使用现成的栈结构。

设计思路：

1.为保证操作时间复杂度为O（1） 需要准备两个栈：data栈，min栈

2.栈空入栈的时候，data栈和min栈都需要压入这个数，栈不空时，data栈正常入栈，入min栈的时候，拿当前数与min栈栈顶的数比较，较小的数入min栈

3.弹栈的时候，data栈和min栈同时弹出栈顶数据

4.通过getMin获取最小值的时候，直接返回min栈的栈顶数但是不弹出

public class Code_02_GetMinStack {
    /**
     * 算法设计思路：
     * 1、初始化两个栈，一个数据栈，一个用作存储当前所有元素最小值的栈
     * 2、数据栈每压入一个元素，更新Min栈，保证Min栈栈顶始终为当前Data栈中的最小值
     * 3、Min栈的好处是，当最小值弹出时，Min栈相应也弹出，
     * 而此时Min栈栈顶也是弹出后的数据栈的最小值，也保证了时间复杂度O(1)
     */
    public Stack<Integer> stackData;
    public Stack<Integer> stackMin;
    public Code_02_GetMinStack(){
        this.stackData=new Stack<Integer>();
        this.stackMin =new Stack<Integer>();
    }

    /**
     * @Description: 压栈操作 当栈空或者待压入数字小于Min栈栈顶时 先压入Min
     * @param:   待压入数字
     * @date: 2019/4/23 15:52
     */
    public void push(int newNum){
        if (stackMin.isEmpty()||newNum <= getMin()){
            stackMin.push(newNum);
        }
        stackData.push(newNum);
    }

    /**
     * @Description: 弹栈操作 ：
     * 弹出data栈栈顶，若该数据与Min栈栈顶相等 则Min也做弹栈操作
     * 保证Min栈栈顶始终为栈内最小元素
     * @return:  返回data栈栈顶
     * @date: 2019/4/23 15:59
     * @throws   当空栈时 抛出数组越界异常
     */
    public Integer pop(){
        if (stackData.isEmpty())
            throw new ArrayIndexOutOfBoundsException("栈空");
        int temp=stackData.pop();
        if (temp==getMin())
            stackMin.pop();
        return temp;
    }
    /**
     * @Description: 获取栈中最小元素 时间复杂度O(1)
     * @date: 2019/4/23 15:53
     * @throws
     */
    public Integer getMin(){
        if (stackMin.isEmpty())
            throw new ArrayIndexOutOfBoundsException("栈空！");
        return stackMin.peek();
    }

最后

以上就是温柔蛋挞为你收集整理的算法之路_18、实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作的全部内容，希望文章能够帮你解决算法之路_18、实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。