题目

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

要求

1. pop、push、getMin的时间复杂度是O(1)
2. 可以使用现成的栈类型

思路

如下图所示，在栈结构中，每次pop的过程中，产生的最小值，分别为：1、2、6，在pop过程会出现两个规律：

1. 每次pop的元素不是最小值时，整个栈的最小值保持不变，
2. 越上的最小值越小

那么只需要引入多一个栈（minElementStack），在push时，在minElementStack的栈顶里面保存比当前最小值还小的元素就可以了，而minElementStack的栈顶始终保持当前栈中最小的元素。在pop时，当pop掉栈的最小值元素，只需同时pop掉minElementStack中的元素就好了。

代码

package com.github.zhanyongzhi.interview.algorithm.stacklist;    import java.util.Stack;    /**     * 带有getMin的栈     * @author zhanyongzhi     */    public class GetMinStack
    
     > {        Stack
     
       stack;        Stack
      
        minElementStack;        public GetMinStack(){            stack = new Stack
       
        ();            minElementStack = new Stack
        
         ();        }        public void push(T item) {            stack.push(item);            if(minElementStack.empty()) {                minElementStack.push(item);                return;            }            T topItem = getMin();            if(0 <= item.compareTo(topItem))                return;            //当前加入的元素是最小的则加入到minElementStack中            minElementStack.push(item);        }        public T pop(){            T item = stack.pop();            T topItem = getMin();            //如果当前弹出的是最小的元素            if(topItem.equals(item))                minElementStack.pop();            return item;        }        public T getMin(){            return minElementStack.peek();        }    }