特殊栈(Java)

特殊栈(Java) 题目

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

要求

pop push getMin 时间复杂度都是O(1)

pop push getMin 时间复杂度都是O(1)

代码 

import java.util.Stack;
public class MyStack2 {
    private Stack stackData;
    private Stack stackMin;

    public MyStack2() {
        this.stackData = new Stack();
        this.stackMin = new Stack();
    }

    public void push(int newNum) {
        if (getMin() <= newNum) {
            int value = this.stackMin.peek();
            this.stackMin.push(value);
        } else {
            stackMin.push(newNum);
        }
        this.stackData.push(newNum);
    }

    public Integer pop() {
        if (stackData.isEmpty()) {
            throw new RuntimeException("Your stack is empty");
        }
        stackMin.pop();
        return stackData.pop();
    }

    public Integer getMin() {
        if (stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty");
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        MyStack1 stack = new MyStack1();
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(1);
        stack.push(4);
        stack.push(1);
        System.out.println(stack.getMin());

    }
}

//方式二
import java.util.Stack;

public class MyStack1 {
    private Stack stackDate;
    private Stack stackMin;

    public MyStack1() {
        this.stackDate = new Stack();
        this.stackMin = new Stack();
    }

    public void push(int newNum) {
        if (this.stackMin.isEmpty()) {
            stackMin.push(newNum);
        } else {
            //边界限制
            if (getMin() > newNum) {
                this.stackMin.push(newNum);
            }
        }

        this.stackDate.push(newNum);

    }

    public Integer pop() {
        if (stackDate.isEmpty()) {
            throw new RuntimeException("Your stack is empty");
        }
        Integer value = stackDate.pop();
        //判断stackMin 是否需要d出
        if (value == getMin()) {
            stackMin.pop();
        }
        return value;
    }

    public Integer getMin() {
        if (this.stackMin.isEmpty()) {
            throw new RuntimeException("Your stack is empty");
        }
        return stackMin.peek();
    }

    public static void main(String[] args) {
        MyStack1 stack = new MyStack1();
        stack.push(3);
        stack.push(4);
        stack.push(5);
        stack.push(1);
        stack.push(4);
        stack.push(1);

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

    }
}