设计一个有getMin功能的栈

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

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

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

解答：使用两个栈，一个栈stackData就是保存所有的元素，另一个栈stackMin就是保存当前栈中每一步的最小值。具体实现方式有两种：

第一种：

压入数据规则：

将当前的数num放到stackData栈的时候，判断stackMin栈是否为空，如果为空，就将当前数num也放到stackMin中，如果不为空，就判断stackMin栈顶元素和num的大小，如果num<=stackMin栈顶元素，就把num也放到stackMin栈里面。

弹出数据规则：

现在stackData栈弹出栈顶元素num，判断num和stackMin栈顶元素是否相等。如果不相等（这里的不相等肯定是大于）就不用管；如果相等，就把那个stackMin栈顶元素也弹出来。

查询最小值：

stackData的最小值始终是stackMin栈的栈顶元素。

代码：

package text11;

import java.util.Stack;

public class MyStack1 {
	private Stack<Integer> stackData;
	private Stack<Integer> stackMin;
	public MyStack1() {
		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() {
		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;
	}
	public int getmin() {
		if(this.stackMin.empty()){
			throw new RuntimeException("Your stack is empty.");
		}
		return this.stackMin.peek();
	}
}

第二种：

压入数据规则：

将当前的数num放到stackData栈的时候，判断stackMin栈是否为空，如果为空，就将当前数num也放到stackMin中，如果不为空，就判断stackMin栈顶元素和num的大小，如果num<=stackMin 栈顶 元素，就把num也放到stackMin栈里面。否则，将stackMin栈顶元素再压入stackMin栈中。

弹出数据规则：

弹出一个stackData栈元素，同时也弹出一个stackMin栈元素

查询最小值：

stackData的最小值始终是stackMin栈的栈顶元素。

代码：

package text11;

import java.util.Stack;

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

}