最小栈的实现

题目：实现一个栈，该栈带有出栈（pop）、入栈（push）、取最小元素 （getMin）3个方法。要保证这3个方法的时间复杂度都是O(1)。

解题思路：

step1：设原栈为栈A，辅组栈为B，当第一个元素进栈A时，同时让新元素也进入栈B，这个唯一元素即原栈A的最小值。

Step2：每当有新元素进入栈A时，如果新元素比栈A小就同时让新元素也进入栈B，此时栈B的栈顶元素同时也是栈A的最小值。

Step3：每当栈A有元素出栈时，如果出栈元素是栈A当前最小值，则让栈B的栈顶元素也出栈。此时栈B余下的栈顶元素所指向的，是栈A当中原本第2小的元素，代替刚才的出栈元素成为栈A的当前最小值。

Step4：当调用getMin方法时，返回栈B的栈顶所存储的值，这也是栈A的最 小值。

这个解法中进栈、出栈、取最小值的时间复杂度都是O(1)，最坏 情况空间复杂度是O(n)。

代码实现：

private Stack<Integer> mainStack = new Stack<Integer>();
private Stack<Integer> minStack = new Stack<Integer>();

/**
* 入栈操作
* @param element 入栈的元素
*/
public void push(int element) {
	mainStack.push(element);
	//如果辅助栈为空，或者新元素小于或等于辅助栈栈顶，则将新元素压入辅助栈
	if (minStack.empty() || element <= minStack.peek()) {
		minStack.push(element);
	}
}

/**
* 出栈操作
*/
public Integer pop() {
//如果出栈元素和辅助栈栈顶元素值相等，辅助栈出栈
 if (mainStack.peek().equals(minStack.peek())) {
	minStack.pop();
 }
	return mainStack.pop();
}

/**
* 获取栈的最小元素
*/
public int getMin() throws Exception {
 	if (mainStack.empty()) {
 		throw new Exception("stack is empty");
 	}

 	return minStack.peek();
 }

public static void main(String[] args) throws Exception {
	MinStack stack = new MinStack();
	stack.push(4);
	stack.push(9);
	stack.push(7);
	stack.push(3);
	stack.push(8);
	stack.push(5);
	System.out.println(stack.getMin());
	stack.pop();
	stack.pop();
	stack.pop();
	System.out.println(stack.getMin());
}