栈和队列之设计一个有getMin(得到最小值)功能的栈

有2中方案，分别用类和内部类实现了

  

   

    

     

    
    

     

      import java.util.Stack;
     
    
   

    

     

    
    

     
 
     
    
   

    

     

    
    

     

      /**
     
    
   

    

     

    
    

     

       * @author chenyu  第一种设计：
     
    
   

    

     

    
    

     

       *  题目：设计一个有getMin功能的栈，设计一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中最小元素的操作
     
    
   

    

     

    
    

     

       *  要求：1 pop push getMin操作的时间复杂度都是O(1)
     
    
   

    

     

    
    

     

       * 2 设计的栈类型可以使用线程的栈结构
     
    
   

    

     

    
    

     

       *   思路：压入数据规则：假设当前数据时value,先将其压入stackData，然后判断stackMin是否为空，
     
    
   

    

     

    
    

     

       * 如果为空，则value压入stackMin
     
    
   

    

     

    
    

     

       * 如果不能空，则比较value和stackMin中栈顶元素的哪一个更小
     
    
   

    

     

    
    

     

       * 如果value更小或者两者相等，则将value也压入stackMin
     
    
   

    

     

    
    

     

       * 如果value中栈顶元素小，则stackMin不压入任何内容，如下例子
     
    
   

    

     

    
    

     

       * 1-------->1
     
    
   

    

     

    
    

     

       * 2------->无
     
    
   

    

     

    
    

     

       * 1-------->1
     
    
   

    

     

    
    

     

       * 5-------->无
     
    
   

    

     

    
    

     

       * 4-------->无
     
    
   

    

     

    
    

     

       * 3-------->3
     
    
   

    

     

    
    

     

       * 弹出数据规则：由压入数据规则可知，栈顶元素是最小的，先弹出stackData栈顶元素value，当value等于stackMin栈顶元素的时候，stackMin弹出数据
     
    
   

    

     

    
    

     

       * 当
     
    
  
 

文章来源: chenyu.blog.csdn.net，作者：chen.yu，版权归原作者所有，如需转载，请联系作者。

原文链接：chenyu.blog.csdn.net/article/details/49983293