设计一个有getMin功能的栈

题目

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

要求

1.pop、push、getMin操作的时间复杂度都是O(1)。

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

题解

1.

public class MyStack1 {
	private Stack<Integer> stackData;
	private Stack<Integer> stackMin;
	
	public MyStack1(){
		this.stackData = new Stack<Integer>();
		this.stackMin = new Stack<Integer>();
	}
	
	// push,入栈。	先判断入栈的数是否较当前栈中最小的那个数小（拿该数与stackMin.peek()比较），是的话压入stackMin的栈顶，否则跳过。判断结束后直接压入stackData。
	public void push(int newNum){
		if(this.stackMin.isEmpty()){
			this.stackMin.push(newNum);
		}else if(newNum <= this.getmin()){	// 这里等于最小值时，也会压入栈顶，此时栈顶有2个最小值，pop时，哪怕出去一个该数，还有另外一个存在栈顶。
			this.stackMin.push(newNum);
		}
		this.stackData.push(newNum);
	}
	
	// pop,出栈。		先判断stackData是否为空，为空的话抛出运行时异常。
	// 获得出栈的这个值。判断这个值是否等于当前栈中所有值中的最小值，若是，则抛出栈顶的该最小值。再返回该pop的值
	public int pop(){
		if(this.stackData.isEmpty()){
			throw new RuntimeException("Your stack is empty.");
		}
		int value = this.stackData.pop();
		if(value == this.getmin()){
			this.stackMin.pop();
		}
		return value;
	}
	
	// stackMin的栈顶永远存放着最小的那个数，要获得stackData中当前最小值，即获得stackMin的栈顶，即stackMin.peek()
	public int getmin(){
		if(this.stackMin.isEmpty()){
			throw new RuntimeException("Your stack is Empty.");
		}
		return this.stackMin.peek();
	}     
}

2.

public class MyStack2 {
	
	private Stack<Integer> StackData;
	private Stack<Integer> StackMin;
	
	public MyStack2(){
		this.StackData = new Stack<Integer>();
		this.StackMin = new Stack<Integer>();
	}
	
	public void push(int num){
		if(this.StackMin.isEmpty()){
			this.StackMin.push(num);
		}else if(num <= this.getmin()){
			this.StackMin.push(num);
		}
		else{
			this.StackMin.push(this.getmin());
		}
		this.StackData.push(num);
		
	}
	
	public int pop(){
		if(this.StackData.isEmpty()){
			throw new RuntimeException("这个栈为空");
		}
		int value = this.StackData.pop();
		this.StackMin.pop();
		return value;
	}
	
	public int getmin(){
		if(this.StackMin.isEmpty()){
			throw new RuntimeException("栈空");
		}else{
			return this.StackMin.peek();
		}
	}
}

总结

1. 熟悉了栈的基本操作
   • int pop()
   • void push(int newNum)
   • int peek()
   • empty()
2. 练习了异常的抛出，可以被throw的需要时一个new出来的异常对象
   • 可以是RuntimeException("")，或则其他