题目描述：
Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
push(x) -- Push element x onto stack.
pop() -- Removes the element on top of the stack.
top() -- Get the top element.
getMin() -- Retrieve the minimum element in the stack.
设计一个最小栈，支持入栈，出栈，获取栈顶元素，获取栈最小值，要求时间复杂度0(1).
Stack(栈)是First in-Last out的数据结构。如果不考虑时间复杂度，实现题目的要求都比较简单，现在限定了不超过常量时间O（1），
就不能用简单的排序过滤实现了。
另外，栈顶(top)指的是允许操作数据的一端，要与堆栈中高低地址不同的栈顶和栈底区别开来，以前我经常搞混。
public class MinStack {
//声明数据栈
private Stack<Integer> elementsStack=new Stack<Integer>();
//声明辅助栈
private Stack<Integer> supportStack=new Stack<Integer>();
/**
* 考虑到时间复杂度的需求，添加一个辅助栈，
* 每次入栈时将元素分别存入数据栈和辅助栈，
* 辅助栈中的数据始终保持最小值在栈顶，需要获取最小值时，直接Peek()辅助栈即可。
*/
public static void main(String[] args){
MinStack minStack=new MinStack();
//以下测试用例
minStack.push(0);
minStack.push(1);
minStack.push(0);
System.out.print(minStack.getMin());
minStack.pop();
System.out.print(minStack.getMin());
}
public void push(int x) {
//始终保持辅助栈顶是最小元素
if(supportStack.empty() || x <= supportStack.peek()){
supportStack.push(x);
}
elementsStack.push(x);
}
public void pop() {
//更新辅助栈
if(elementsStack.peek().equals(supportStack.peek())){
supportStack.pop();
}
elementsStack.pop();
}
public int top() {
return elementsStack.peek();
}
public int getMin() {
//辅助栈
return supportStack.peek();
}
}
提交，可以AC.
本文转自邴越博客园博客，原文链接：http://www.cnblogs.com/binyue/p/4111369.html，如需转载请自行联系原作者
