java-2.设计包含min函数的栈
具体思路参见：http://zhedahht.blog.163.com/blog/static/25411174200712895228171/
import java.util.ArrayList;import java.util.List;public class MinStack {//maybe we can use origin array rather than ArrayListprivate List<Integer> dataStack;private List<Integer> auxStack;//store the position of MinElementpublic static void main(String[] args) {MinStack minStack=new MinStack();minStack.push(3);minStack.printStatus();minStack.push(4);minStack.printStatus();minStack.push(2);minStack.printStatus();minStack.push(1);minStack.printStatus();minStack.pop();minStack.printStatus();minStack.pop();minStack.printStatus();minStack.push(0);minStack.printStatus();}public MinStack(){dataStack=new ArrayList<Integer>();auxStack=new ArrayList<Integer>();}public void push(int item){if(isEmpty()){dataStack.add(item);auxStack.add(0);//position=0}else{dataStack.add(item);int minIndex=auxStack.get(auxStack.size()-1);int min=dataStack.get(minIndex);if(min>item){auxStack.add(dataStack.size()-1);}else{auxStack.add(minIndex);}}}public int pop(){int top=-1;if(isEmpty()){System.out.println("no element,no pop");}else{auxStack.remove(auxStack.size()-1);top=dataStack.remove(dataStack.size()-1);}return top;}public int min(){int min=-1;if(!isEmpty()){int minIndex=auxStack.get(auxStack.size()-1);min=dataStack.get(minIndex);}return min;}public boolean isEmpty(){return dataStack.size()==0;}public void printStatus(){System.out.println("数据栈 辅助栈 最小值");for(int i=0;i<dataStack.size();i++){System.out.print(dataStack.get(i)+",");}System.out.print(" ");for(int i=0;i<dataStack.size();i++){System.out.print(auxStack.get(i)+",");}System.out.print(" ");System.out.print(this.min());System.out.println();}/*步骤 数据栈 辅助栈 最小值1.push 3 3 0 32.push 4 3,4 0,0 33.push 2 3,4,2 0,0,2 24.push 1 3,4,2,1 0,0,2,3 15.pop 3,4,2 0,0,2 26.pop 3,4 0,0 37.push 0 3,4,0 0,0,2 0 */}