微软算法100题02设计包含min函数的栈

 1 package com.rui.microsoft; 2  3 import java.util.Stack; 4  5 public class Test02_MinStack { 6  7     public static void main(String[] args) { 8         MyStack myStack = new MyStack(); 9         myStack.push(5);10         myStack.push(3);11         myStack.push(1);12         myStack.push(6);13         14         System.out.PRintln(myStack.min());15         16         myStack.pop();17         System.out.println(myStack.min());18         19         myStack.pop();20         System.out.println(myStack.min());21         22     }23     24     static class MyStack{25         private Stack<Integer> stack = new Stack<Integer>();26         private Stack<Integer> minStack = new Stack<Integer>();27         28         public void push(int i){29             stack.push(i);30             31             if(minStack.isEmpty()){32                 minStack.push(i);33             }else{34                 int min = minStack.peek();35                 //minStack only push item smaller than its top item36                 //minStack只入栈比其栈顶元素小的元素37                 if(i < min){38                     minStack.push(i);39                 }40             }41         }42         43         public Integer pop(){44             Integer i = stack.pop();45             //when pop an item from original stack46             //we need to process the minStack also47             //if the item popped from original stack is larger than minStack's top item48             //it means this item should not exist in minStack49             if(i <= minStack.peek()){50                 minStack.pop();51             }52             return i;53         }54         55         public Integer min(){56             return minStack.peek();57         }58     }59 }