背景

各自完成插入 10万、20万 条随机数，然后再将这些随机数出队列；

测试代码



/**

* 测试速度

*/

 public String testSpeed(Queue<Integer> queue, int num) {

        long start = System.currentTimeMillis();

        Random random = new Random(47);

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

            queue.enQueue(random.nextInt(num));

        }

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

            queue.deQueue();

        }

        long end = System.currentTimeMillis();

        return (end - start) / 1000.0 + " s";

    }

    @Test

    public void test() {

//        十万、二十万的数据

        int num = 200000;

        ArrayQueue<Integer> arrayQueue = new ArrayQueue();

        LoopQueue<Integer> loopQueue = new LoopQueue();

        // 十万测试的时间： 16.374 s     |  二十万测试的时间： 63.724 s

        System.out.println(testSpeed(arrayQueue, num));

        // 十万测试的时间： 0.085 s 、   |  二十万测试的时间： 0.128 s

        System.out.println(testSpeed(loopQueue, num));

    }

结果

从打印的时间看，二者的差距是 天壤之别；

循环队列 在完成 10万、20万数据入列、出列的时候，均在 1 s 之内；

测试 二百万 的时间是 0.8 s，二千万 数据，时间在 28 s；

数组队列 在完成 10万、20万数据入列、出列的时候，分别使用 16 s、64 s ；

二百万、二千万，我没测试；但是，我测试 一百万 我等了 17 分钟，没跑完，然后我结束了运行，二千万的数据，估计得按 小时 算；

备注：我的 CPU 是 i7-4710mq ，具体测试，跟 CPU 型号有关；

链表

之前实现的 动态数组 、队列 、栈 其实本质上都是静态的，底层都是利用 静态数组 创建的，我们需要考虑，什么时候 扩容，什么时候 缩小；

而 链表，是真正的动态结构，它根本不需要去考虑 扩容、缩小 ，因为它本身就是动态的变化着；

随机访问

但是 链表 也有缺点，由于底层不再是利用 静态数组 实现的，因此，丧失了 随机访问 能力；

因为 静态数组 底层开辟的内存，是连在一起的，可以根据下标，直接计算出偏移量，直接去访问对应地址的内存；

链表 由于是动态的变化的，它的节点之间，是通过 引用 相互连接在一起的，是 无法直接计算 出某一个节点的内存地址的，因此，也就不具备随机访问了；

巴特西

（四）循环队列 VS 数组队列（效率对比）

背景

测试代码

结果

链表

随机访问

最新文章

热门文章

巴特西

（四）循环队列 VS 数组队列 （效率对比）

背景

测试代码

结果

链表

随机访问

最新文章

热门文章

（四）循环队列 VS 数组队列（效率对比）