设计一个有getMin功能的栈

一 题目

实现一个特殊的栈，实现栈的基本功能并实现返回栈中最小元素的操作。

二 要求

1、pop、push、getMin操作时间复杂度都是O（1）

2、设计的栈类型可以使用现成的栈结构

三 分析

我们可以使用两个栈，一个用来保存当前栈中的元素，其功能为正常的栈，记为stackData；另外一个用于保存每一步中的最小值，记为stackMin。

四 设计思路

4.1 压入规则

设当前数据为newNum，先将其压入stackData；

然后判断stackMin是否为空：

1.为空则将newNum压入stackMin中

2.不为空则比较newNum和stackMin栈顶元素哪一个更小

2.1如果newNum更小或者两者相等，则newNum也压入stackMin中；

2.2如果stackMin更小，则stackMin不压入任何内容；

4.2 弹出规则

1.先弹出stackMin栈顶元素，记为value

2.然后比较value和stackMin栈顶元素（记为min）的大小：

2.1 value == min，则stackMin弹出栈顶元素；

2.2否则stackMin不弹出任何内容。

4.3 查询栈中最小值操作

由压入和弹出规则可知，stackMin栈顶始终保存着stackData中最小的元素，所以只需要弹出栈顶元素即可。

五 代码实现

public 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(int newNum){
        	if(this.stackMin.isEmpty()){
            	this.stackMin.push(newNum);
            }else if(newNum <= this.getMin()){
            	this.stackMin.push(newNum);
            }
            this.stackData.push(newNum);
        }
        
        public int pop(int newNum){
        	if(this.stackData.isEmpty()){
            	throw new RuntimeException("stackData is empty!");
            }
            int value = this.stackData.pop();
            if(value == this.getMin()){
            	this.stackMin.pop();
            }
            return value;
        }
        
        public void getMin(){
        	if(this.stackMin.isEmpty()){
            	throw new RuntimeException("stackMin is empty!");
            }
            return this.stackMin.pop();
        }
    
    
}