玩转数据结构（九）数组队列、链式队列、循环队列性能测试

心已赠人 2022-05-21 09:05 199阅读 0赞

在前几篇博客中，分别基于动态数组实现了队列、基于链表实现了队列、基于数组实现了循环队列。

这次分别对这几种队列进行性能测试。

### 1、测试代码 ###

传递的参数为队列、操作次数。

private static double testQueue(Queue<Integer> q, int opCnt) {
            long start = System.nanoTime();
            Random random = new Random();
            for (int i = 0; i < opCnt; i++) {
                q.enqueue(random.nextInt(Integer.MAX_VALUE));
            }
            for (int i = 0; i < opCnt; i++) {
                q.dequeue();
            }
            long end = System.nanoTime();
            return (end - start) / 1000000000.0;
        }

public static void main(String[] args) {
            ArrayQueue<Integer> arrayQueue = new ArrayQueue<Integer>();
            LoopQueue<Integer> loopQueue = new LoopQueue<Integer>();
            LinkedListQueue<Integer> linkedListQueue = new LinkedListQueue<Integer>();
            int opCnt = 100000;
            double time1 = testQueue(arrayQueue, opCnt);
            double time2 = testQueue(loopQueue, opCnt);
            double time3 = testQueue(linkedListQueue, opCnt);
            System.out.println("ArrayQueue:" + time1 + "s");
            System.out.println("LoopQueue:" + time2 + "s");
            System.out.println("linkedListQueue:" + time3 + "s");
        }

### 2、测试结果 ###

当opCnt=10 0000时，结果为：

ArrayQueue:5.498680106s
    LoopQueue:0.01712342s
    linkedListQueue:0.012692485s

原因分析：因为实现的循环队列和LinkedListQueue的入队和出队操作的时间复杂度均为O（1），因此他们两个的性能差异不大。但是基于动态数组实现的队列，入队操作为时间复杂度O（1），出队操作时间复杂度却为O（n），因为涉及到后面数据向前移动一位。

当opCnt=100 0000时，ArrayQueue就歇菜了，等好长时间都不出结果，显然这种方式效率不高。

我们看看LinkedListQueue和LoopQueue：

LoopQueue:0.11758469s
    linkedListQueue:0.657725721s

差异也并不大，LinkedListQueue需要做更多的new操作，因此时间比LoopQueue长点。

当opCnt=1000 0000时，LinkedListQueue和LoopQueue差异更加明显：

LoopQueue:4.410247428s
    linkedListQueue:10.07853998s