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 */}