題目：定義棧的數(shù)據(jù)結構，請在該類型中實現(xiàn)一個能夠得到棧的最小素的min 函數(shù)。在該棧中，調(diào)用min、push 及pop的時間復雜度都是0(1)

代碼如下：

package demo;

import java.util.Stack;

public class Test21 {
    public static class StackWithMin<T extends Comparable<T>> {
        // 數(shù)據(jù)棧
        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");
            }
            // 如果數(shù)據(jù)棧是空的，直接將元素入棧
            if(dataStack.isEmpty()) {
                dataStack.push(t);
                minStack.push(t);
            } else {
                // 獲取未插入t之前的數(shù)據(jù)棧中的最小元素
                T e = minStack.peek();
                // 將t入棧
                dataStack.push(t);
                // 如果插入的數(shù)據(jù)比棧中的最小元素小
                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