题目

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

要求

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

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

java代码

/**

 * @Description:设计一个有getMin功能的栈

 * @Author: lizhouwei

 * @CreateDate: 2018/4/5 9:54

 * @Modify by:

 * @ModifyDate:

*/

public class Chapter1_1 {

    private Stack<Integer> stackData;//数据栈，压栈的数据

    private Stack<Integer> stackMin;//辅助栈，从栈顶到栈底 由小到大有序的数据

    public Chapter1_1(){

        stackData = new Stack<Integer>(); //在new的时候 初始化stackData内存空间

        stackMin = new Stack<Integer>(); //在new的时候 初始化stackMin内存空间

    }

    //压入栈中

    public void push(int value){

        //将数据压入栈中

        stackData.push(value);

        //如果辅助栈是空的则直接压入

        if(stackMin.isEmpty()){

            stackMin.push(value);

        }else if(value<stackMin.peek()){

            //value比栈顶元素小

            stackMin.push(value);

        }

    }

    //弹栈

    public int pop(){

        //如果数据栈中已空,则 返回 -1

        if(stackData.isEmpty()){

            return -1;

        }

        //数据栈弹出

       int value =  stackData.pop();

       if(value ==stackMin.peek()){

           stackMin.pop();

       }

        return value;

    }

    //获取最小值

    public int getMin(){

        //获取辅助栈顶元素即可

        return stackMin.peek();

    }

    //测试

    public static void main(String[] args){

        Chapter1_1 chapter = new Chapter1_1();

        for(int i=10,j=11;i<20;i=i+2,j=j+10) {

            chapter.push(j);

            chapter.push(i);

        }

        System.out.println(chapter.getMin());

        while(!chapter.stackData.isEmpty()){

            System.out.print(chapter.stackData.pop()+" ");

        }

    }

}