【题目】

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

 

【要求】

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

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

 

【分析】

　　栈是一种只能在另一端进行操作的具有“先进后出”特性的数据结构，它有push(元素入栈)、pop(元素出栈)、peek(访问栈顶元素)、size(获取栈元素个数)和isEmpty(判断栈是否为空)等基本功能

　　一般来说，栈并没有提供返回当前栈中最小元素的方法。因为栈只允许在栈顶对元素进行操作，所以如果只使用一个栈来存储元素，那么我们是无法知道当前栈中的最小元素的，严格地说，对于一个非空栈，我们永远都只知道当前的栈顶元素是什么。所以只用一个栈结构难以实现getMin功能。可以考虑增加一个辅助栈结构，用来记录栈的所有可能最小元素序列。

　　

1 import java.util.Stack; 2  3 public class MyStack 4 { 5     private Stack
     
       dataStack; 6     private Stack
      
        minStack; 7  8     public MyStack() 9     {10     　　dataStack = new Stack<>();11     　　minStack = new Stack<>();12     }13 14     public void push(int data)15     {16     　　dataStack.push(data);17     　　if(minStack.empty())    // 辅助栈为空或者栈顶元素小于或等于data时将data入栈，说明将data压入dataStack中后，当前dataStack的最小元素就是data，所以要更新minStack18     　　{19     　　　　minStack.push(data);20     　　}21     　　else if(data <= minStack.peek())22　　　　　{23             minStack.push(data);24     　　}25     }26 27     public int pop()28     {29     　　if(dataStack.empty())30     　　{31             throw new RuntimeException("fail to pop, stack is empty.");32     　　}33     　　else34     　　{35             int data = dataStack.pop();36             if(data == getMin())          // 如果dataStack栈弹出的元素是当前dataStack中的最小元素，则弹出操作之后，需要对minStack栈进行更新37             {38                 minStack.pop();39             }40         　　return data;41     　　}42     }43     44     public int getMin()45     {46         if(minStack.empty())47         {48             throw new RuntimeException("fail to getMin, stack is empty.");49　　　　　}50     　　return minStack.peek();51     }52 53     public int size()54     {55     　　return dataStack.size();56     }57 58     public boolean isEmpty()59     {60         return dataStack.empty();61     }62 }
      
     

 

来源：左程云老师《程序源代码面试指南》