【剑指Offer 21】包含min函数的栈

题目：定义栈的数据结构，请在该类型中实现一个能够得到栈的最小素的min 函数。在该栈中，调用min、push 及pop的时间复杂度都是0(1)

代码如下：

package demo;

import java.util.Stack;

public class Test21 {
    public static class StackWithMin<T extends Comparable<T>> {
        // 数据栈
        private Stack<T> dataStack;
        // 最小元素栈
        private Stack<T> minStack;
    
        public StackWithMin() {
            this.dataStack = new Stack<>();
            this.minStack = new Stack<>();
        }
    
        /**
         * 出栈
         * @return
         */
        public T pop() {
            if(dataStack.isEmpty()) {
                throw new RuntimeException("The stack is already empty");
            }
            // 两个栈同时出栈
            minStack.pop();
            return dataStack.pop();
        }
    
        /**
         * 入栈
         * @param t 入栈的元素
         */
        public void push(T t) {
            // 如果入栈的元素为空，就抛出异常
            if(t == null) {
                throw new RuntimeException("Element can be null");
            }
            // 如果数据栈是空的，直接将元素入栈
            if(dataStack.isEmpty()) {
                dataStack.push(t);
                minStack.push(t);
            } else {
                // 获取未插入t之前的数据栈中的最小元素
                T e = minStack.peek();
                // 将t入栈
                dataStack.push(t);
                // 如果插入的数据比栈中的最小元素小
                if(t.compareTo(e) < 0) {
                    minStack.push(t);
                } else {
                    minStack.push(minStack.peek());
                }
            }
        }
    
        /**
         * 获取栈中的最小元素
         * @return
         */
        public T min() {
            if(minStack.isEmpty()) {
                throw new RuntimeException("No element in Stack");
            }
            return minStack.peek();
        }
    }

    public static void main(String[] args) {
        StackWithMin<Integer> stack = new StackWithMin<>();
        stack.push(3);
        System.out.println(stack.min() == 3);
        stack.push(4);
        System.out.println(stack.min() == 3);
        stack.push(2);
        System.out.println(stack.min() == 2);
        stack.push(3);
        System.out.println(stack.min() == 2);
        stack.pop();
        System.out.println(stack.min() == 2);
        stack.pop();
        System.out.println(stack.min() == 3);
        stack.push(0);
        System.out.println(stack.min() == 0);
    }
}

来源：http://blog.csdn.net/derrantcm/article/details/46691057