题目描述

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

要求

1 pop、push、getMin操作的时间复杂度都是O(1)
2 设计的栈类型可以使用现成的栈结构

代码如下：

本来返回栈中最小元素的操作时，需要弹出最小元素，但是实际不需要这样做。代码如下：

import java.util.Stack;

public class GetMinStack {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;
    public GetMinStack(){
        this.stack1 = new Stack<>();
        this.stack2 = new Stack<>();
    }
    public void push(int num){
        if(stack2.isEmpty()||getMin()>=num){
            stack2.push(num);
        }
        stack1.push(num);
    }
    public int pop(){
        if(this.stack1.isEmpty()){
            throw new RuntimeException("Your stack is empty.");
        }
        int value = this.stack1.pop();
        if(value == this.getMin()){
            this.stack2.pop();
        }
        return value;
    }

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