Design a stack that supports push, pop, top, and retrieving the minimum element in constant time.
Example:
MinStack minStack = new MinStack(); minStack.push(-2); minStack.push(0); minStack.push(-3); minStack.getMin(); --> Returns -3. minStack.pop(); minStack.top(); --> Returns 0. minStack.getMin(); --> Returns -2.
In Java
public class MinStack { private Stack _stack; private Stack _stackMin; /** initialize your data structure here. */ public MinStack() { _stack = new Stack(); _stackMin = new Stack(); } public void push(int x) { _stack.push(x); if(_stackMin.isEmpty() || (int)_stackMin.peek() >= x) { _stackMin.push(x); } } public void pop() { if(!_stack.isEmpty() && (int)_stack.pop() <= (int)_stackMin.peek()) _stackMin.pop(); } public int top() { if(_stack.isEmpty()) return 0; return (int)_stack.peek(); } public int getMin() { if(_stackMin.isEmpty()) return 0; return (int)_stackMin.peek(); } }
原文：http://www.cnblogs.com/renyualbert/p/5874216.html