特殊栈的实现：返回栈中最小元素

特殊栈的实现：返回栈中最小元素

目标：实现一个特殊的栈，在实现栈的基础功能上，再实现返回栈中最小元素的操作； 要求：pop、push、getMin 的操作的时间复杂度都是 O（1），同时设计的栈类型可以使用现成的栈结构；

解答思路： 因为时间复杂度要求：O(1)，因此不能使用遍历，因为遍历的结果就是 O（N），这里使用两个栈；一个栈为 Data 栈，用于存放数据，另一个栈为 min 栈，用于存放最小值，两个栈一起增长；
步骤：放入第一个数据，放入 Data 栈中，同时因为 Min 栈中当前为空，因此放入第一个元素之后最小值也是第一个元素，因此将第一个元素也放入 min 栈中；在 Data 栈中放入第二个数据时候，将当前元素与 min 栈顶比较，如果当前数大于等于 min 栈顶，方法一是不动，方法二是将原来 Min 栈的栈顶元素再次压入一遍；反之如果当前数小于 min 栈顶，就将原来 min 栈顶的元素再次在 min 栈中压入一遍。push 和 pop 方法都有修改

package cn.test;

import java.util.Stack;

/**
 * @Author smallmartial
 * @Date 2020/3/2
 * @Email [email protected]
 */
public class GetStackMin {

    public static class  MyStack{
        private Stack<Integer> stackData;
        private Stack<Integer> stackMin;

        public MyStack() {
            this.stackData = new Stack<Integer>();
            this.stackMin = new Stack<Integer>();
        }

        public void push(Integer num){
            //判断最小栈是否为空 /当前数字是否小于 最小栈的栈顶元素
            if(this.stackMin.isEmpty()){
                this.stackMin.push(num);
            }else if(num < this.getMin()){
                this.stackMin.push(num);
            }
            this.stackData.push(num);
        }

        public Integer pop(){
            if(this.stackMin.isEmpty()){
                throw new RuntimeException("the stack is empty");
            }
            int value = this.stackData.pop();
            if(value == this.getMin()){
                this.stackMin.pop();
            }
            return value;
        }
        private Integer getMin() {
            if(this.stackMin.isEmpty()){
                throw new RuntimeException("the stack is empty");
            }
            return this.stackMin.peek();
        }
    }
    public static void main(String[] args) {
        MyStack stack1 = new MyStack();
        stack1.push(3);
        System.out.println("加入 3 之后栈中最小值：" + stack1.getMin());
        stack1.push(4);
        System.out.println("加入 4 之后栈中最小值：" + stack1.getMin());
        stack1.push(1);
        System.out.println("加入 1 之后栈中最小值：" + stack1.getMin());
        System.out.println(stack1.pop());
        System.out.println("弹出栈头之后最小值：" + stack1.getMin());

    }
}