package com.hzins.suanfa;

import java.util.Stack;

/**

 * 实现stack 加上·getMin功能 时间复杂度为O(n)

 * @author Administrator

 *

 */

public class GetMinStack {

    private Stack<Integer> stackData;

    private Stack<Integer> stackMin;

    public GetMinStack(){

        this.stackData = new Stack<Integer>();

        this.stackMin = new Stack<Integer>();

    }

    public void push(int newNum){

        if(this.stackMin.isEmpty()){

            stackMin.push(newNum);

        }else if(newNum <this.getMin()){

            stackMin.push(newNum);

        }else{

            stackMin.push(this.getMin());

        }

        stackData.push(newNum);

    }

    public int pop(){

        if(stackData.isEmpty()){

            throw new RuntimeException("Your stack is empty");

        }

        stackMin.pop();

        return stackData.pop();

    }

    public int getMin(){

        if(this.stackMin.isEmpty()){

            throw new RuntimeException("Your stack is empty");

        }

        return this.stackMin.peek();

    }

}