/*
【题目】
实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作
【要求】
1.pop、push、getMin 操作的时间复杂度都是 O(1)。
2.设计的栈类型可以使用现成的栈结构。
*/

//第一种方法，min栈不重复压入数据

import java.util.Stack;

public class MyStack1 {

    public Stack<Integer> stackdata;
    public Stack<Integer> stackmin;

    public MyStack1() {
        this.stackdata=new Stack<>();
        this.stackmin=new Stack<>();
    }

    public void push(Integer num) {
        if(this.stackmin.isEmpty()) {
            stackmin.push(num);
        }else {
            int value=getmin();//获取最小的数据
            if(num<=value) {//比较当前数据和最小数据
                this.stackmin.push(num);//如果当前数据小最则压入栈中，否则min栈不压入数据
            }
        }
        this.stackdata.push(num);
    }

    public int pop() {
        if(this.stackdata.isEmpty()) {
            throw new RuntimeException("栈为空了");
        }
        int sdata=this.stackdata.pop();
        int min=getmin();
        if(sdata==min) {
            this.stackmin.pop();//当出栈数据和min栈栈顶数据相同时，表示当前的最小元素要出栈
        }
        return sdata;
    }

    public int getmin() {
        if(this.stackmin.isEmpty()) {
            throw new RuntimeException("栈是空的");
        }else {
            return this.stackmin.peek();
        }
    }
}

//第二种方法：min栈重复压入数据

import java.util.Stack;

public class MyStack2 {

    public Stack<Integer> stackdata;

    public Stack<Integer> stackmin;

    public MyStack2() {
        this.stackdata=new Stack<>();
        this.stackmin=new Stack<>();
    }

    public void push(int num) {
        if(this.stackmin.isEmpty()) {
            this.stackmin.push(num);
        }else {
            int min=getmin();
            if(num<=min) {//获得最小值，压入min栈中
                this.stackmin.push(num);
            }else {
                this.stackmin.push(min);
            }
        }
        this.stackdata.push(num);
    }

    public int pop() {
        if(this.stackmin.isEmpty()) {
            throw new RuntimeException("栈空了");
        }
        //min栈和data栈同步pop
        this.stackmin.pop();
        return this.stackdata.pop();

    }

    public int getmin() {
        if(this.stackmin.isEmpty()) {
            throw new RuntimeException("栈空了");
        }else {
            return this.stackmin.peek();
        }
    }
}

/*
对比：
方法一 压入数据时省空间，弹出数据时耗时间
方法二 压入数据时耗空间，弹出数据时省时间
*/