1.4.43大小可变的数组与链表。通过实验验证对于栈来说基于大小可变的数组的实现快于基于链表的实现的猜想(请见练习1.4.35和练习1.4.36)。为此实现另一个版本的Doublingratio,计算两个程序的运行时间的比例。

答：

public class E1d4d43

{

    public static double timeTrialArray(int N)

    {

       ResizingArrayStack<Integer> s=new ResizingArrayStack<Integer>();

       Stopwatch timer=new Stopwatch();

        for (int i=0;i<N;i++)

            s.push(i);

        for (int i=0;i<N;i++)

            s.pop();

       

        return timer.elapsedTime();

    }

   

        public static double timeTrialLink(int N)

    {

       Stack<Integer> s=new Stack<Integer>();

       Stopwatch timer=new Stopwatch();

        for (int i=0;i<N;i++)

            s.push(i);

        for (int i=0;i<N;i++)

            s.pop();

       

        return timer.elapsedTime();

    }

       

   

    public static void main(String[] args)

    {

      

       double prevOfArray=timeTrialArray(125);

       double prevOfLink=timeTrialLink(125);

       StdOut.printf("      N  timeOfArray   timeOfLink   ArrayRatio    LinkRatio   Array/LinkRatio\n");

        for (int N=250;true;N+=N)

       {

           double timeOfArray=timeTrialArray(N);

           double timeOfLink=timeTrialLink(N);

           StdOut.printf("%7d %9.1f  %9.1f  ",N,timeOfArray,timeOfLink);

           StdOut.printf("%9.1f  %12.1f  %12.1f \n",timeOfArray/prevOfArray ,timeOfLink/prevOfLink,timeOfArray/timeOfLink);

           prevOfArray=timeOfArray;

           prevOfLink=timeOfLink;

       }

    }

}