剑指offer-问题21

太过爱你忘了你带给我的痛 2022-05-11 11:06 168阅读 0赞

package offer;
    
    import java.util.Stack;
    
    /**
     * offer interview 21
     */
    public class Test21 {
    
        public static class StackWithMin<T extends Comparable<T>>{
            private Stack<T> dataStack;
            private Stack<Integer> minStack;
    
            public StackWithMin(){
                this.dataStack = new Stack<>();
                this.minStack = new Stack<>();
            }
    
    
            public T pop(){
                if (dataStack.isEmpty()){
                    throw new RuntimeException("the stack is already empty!");
    
                }
    
                minStack.pop();
                return dataStack.pop();
            }
    
    
            public void  push(T t){
                if (null == t){
                    throw new RuntimeException("Element can be null");
                }
    
                if (dataStack.isEmpty()){
                    dataStack.push(t);
                    minStack.push(0);
                }else{
                    T e =  dataStack.get(minStack.peek());
                    dataStack.push(t);
                    if (t.compareTo(e) < 0){
                        minStack.push(dataStack.size() - 1);
                    }else{
                        minStack.push(minStack.peek());
                    }
                }
            }
    
            public T min(){
                if (minStack.isEmpty()){
                    throw new RuntimeException("No element in stack!");
                }
    
                return dataStack.get(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);
    
    
        }
    
    
    
    }