如何用O(1)的时间复杂度求栈中最小元素

由于栈具有先进后出的特点，push和pop也只能对栈顶元素进行操作。而题目要求的是在O（1）的时间复杂度求得最小元素，显然是不可以遍历求取的。这里可以用两个栈来实现，一个栈用来存取数据，另一个用来存栈的最小元素。思路如下：如果当前入栈的元素比最小栈中的栈顶元素还小，则如最小栈。在出栈时，如果当前出栈元素正好是最小栈的栈顶元素，则最小栈的栈顶元素也出栈。

import java.util.Stack;

/**
 * Created by Liu on 2016/7/6.
 */
public class MinStack {
private Stack<Integer> MyStack;
private Stack<Integer> MyminStack;
public MinStack() {
MyStack=new Stack();
MyminStack=new Stack();
    }
public void push( int data){
MyStack.push(data);
if(MyminStack.isEmpty())
MyminStack.push(data);
else{
if (MyminStack.peek()>data)
MyminStack.push(data);
        }
    }
public int pop(){
int topData =MyStack.peek();
MyStack.pop();
if (topData==MyminStack.peek())
MyminStack.pop();
return topData;
    }
public int min(){
if (MyminStack.isEmpty())
return Integer.MAX_VALUE;
else
 return MyminStack.peek();
    }
public static void main (String[] args){
        MinStack minStack=new MinStack();
        minStack.push(8);
        minStack.push(9);
        minStack.push(5);
        System.out.println(minStack.min());
    }

}