1     /* 2      * 设计一个栈，除了pop与push方法，还支持Min方法，可返回栈元素中的最小值， 3      * push、pop、min三个方法的时间复杂度必须是O(1) 4      * 一种解法是在Stack类里添加一个Int型的minValue，当minValue出栈时，我们会搜索整个栈 5      * 找出最新的最小值，但是却不符合操作时间为O(1)的要求 6      * 如有： 7      * push(4)//最小值：4 8      * push(5)//最小值：4 9      * push(3)//最小值：310      * push(1)//最小值：111      * pop()  //最小值312      * 由以上例子，只要记下每种状态的最小值，我们就能很容易找出最小值。13      * 每个节点记录当前最小值，只要找到Min,直接查看栈顶元素就能找到最小值14      * 在这个程序中，利用例外的栈来记录这些Min15      * 16      * */17     18     import java.util.Stack;19     20     public class StackMin extends Stack
     
       {21         22         Stack
      
        s;23         public StackMin()24         {25             s=new Stack
       
        ();26         }27         public int min()28         {29             if(s.isEmpty())30                 return Integer.MAX_VALUE;31             else 32                 return s.peek();33         }34         public void push(int value)35         {36             if(value<=min())  //比较当前值与最小值，如果当前值比最小值小，就把当前值进栈37                 s.push(value);38             super.push(value);39         }40         public Integer pop()41         {42             int value=super.pop();43             if(value==min())  //如果当前值出栈，且是最小值，应把在保存最小值栈的最小值弹出44             {45                 s.pop();46             }47             return value;48         }49         public static void main(String[] args) {50             // TODO Auto-generated method stub51                 StackMin stack = new StackMin();52                 System.out.println("当前最小值："+stack.min());53                 stack.push(5);54                 stack.push(6);55                 stack.push(3);56                 stack.push(7);57                 System.out.println("当前最小值："+stack.min());58                 stack.pop();59                 stack.pop();60                 System.out.println("当前最小值："+stack.min());61                 62         }63     64     }