实现带有getMin的栈

题目

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

要求

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<T extends Comparable<T>> {
        Stack<T> stack;
        Stack<T> minElementStack;

        public GetMinStack(){
            stack = new Stack<T>();
            minElementStack = new Stack<T>();
        }

        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();
        }
    }

Github地址