【题目】

　　实现一个特殊的栈，在实现栈的基本功能的基础上，再实现返回栈中的最小元素的操作。

【要求】

　　1.pop、push、getMin操作的时间复杂度都是O(1)。

　　2.设计的栈类型可以使用现成的栈结构。

方案一的代码实现如下：

1 import java.util.Stack; 2 public class MyStack1 { 3     private Stack
     
       stackData; 4     private Stack
      
        stackMin; 5     public MyStack1() 6     { 7         this.stackData=new Stack
       
        (); 8         this.stackMin=new Stack
        
         (); 9     }10     public void push(int newNum)11     {12         if(this.stackMin.isEmpty()||newNum<=this.getmin())13             this.stackMin.push(newNum);14         this.stackData.push(newNum);15     }16     public int pop()17     {18         if(this.stackData.isEmpty())19             System.out.println("Your stack is empty!");20         int value=this.stackData.pop();21         if(value==this.getmin())22             this.stackMin.pop();23         return value;24     }25     public int getmin()26     {27         if(this.stackMin.isEmpty())28             System.out.println("Your stack is empty!");29         return this.stackMin.peek();30     }31     public static void main(String[] args)32     {33         MyStack1 s=new MyStack1();34         s.push(3);35         s.push(4);36         s.push(5);37         s.push(1);38         s.push(2);39         s.push(1);40         System.out.println(s.getmin());41         System.out.println(s.pop());42         System.out.println(s.pop());43         System.out.println(s.pop());44         System.out.println(s.pop());45         System.out.println(s.pop());46         System.out.println(s.pop());47         System.out.println(s.pop());48     }49 }
        
       
      
     

运行结果如下：

1121543Your stack is empty!

方法二的实现代码如下：

1 import java.util.Stack; 2 public class MyStack2 { 3     private Stack
     
       stackData; 4     private Stack
      
        stackMin; 5     public MyStack2() 6     { 7         this.stackData=new Stack
       
        (); 8         this.stackMin=new Stack
        
         (); 9     }10     public void push(int newNum)11     {12         if(this.stackMin.isEmpty()||newNum
        
       
      
     

运行结果如下：

1121543Your stack is empty!