import java.util.Arrays;

 /**

  * @author evasean www.cnblogs.com/evasean/

  */

 public class StackWithMax {

     public double[] items;// 为了方便展示结果，我也懒得写遍历方法，就设为public

     public double[] maximums; // 存放最大值的数组，为了方便展示结果，我也懒得写遍历方法，就设为public

     private int n;

     private int cap;

     public StackWithMax() {

         n = 0;

         cap = 2;

         items = new double[cap];

         maximums = new double[cap];

     }

     public boolean isEmpty() {

         return n == 0;

     }

     public void push(double item) {

         if (n == 0)

             maximums[0] = item;

         else {

             int i;

             int j;

             for (i = n - 1; i >= 0; i--) {// 这个循环用来找出item在maximums数组中应该放置的位置

                 if (item <= maximums[i])

                     continue;

                 else

                     break;

             }

             for (j = n - 1; j > i; j--) {// 将位置i以后的元素都往后挪一个位置

                 maximums[j + 1] = maximums[j];

             } // 循环结束时j指向i

             maximums[j + 1] = item;// j+1就是item应该放置的位置

         }

         items[n++] = item;

         if (n == cap)

             resize(2 * cap);

     }

     public double pop() {

         double item = items[--n];

         if (n > 0 && n == cap / 4)

             resize(cap / 2);

         return item;

     }

     public double maximum() {

         return maximums[n - 1];

     }

     private void resize(int cap) {

         double[] t1 = new double[cap];

         double[] t2 = new double[cap];

         for (int i = 0; i < n; i++) {

             t1[i] = items[i];

             t2[i] = maximums[i];

         }

         items = t1;

         maximums = t2;

         this.cap = cap;

     }

     public static void main(String[] args) {

         StackWithMax stack = new StackWithMax();

         stack.push(9);

         stack.push(8);

         stack.push(11);

         stack.push(0);

         stack.push(-9.9);

         stack.push(88);

         System.out.println(Arrays.toString(stack.items));

         System.out.println(Arrays.toString(stack.maximums));

         stack.pop();

         System.out.println(stack.maximum());

     }

 }