两种队列的实现以及性能测试
队列介绍
队列是一种常见的数据结构，也是我们学习，工作中必须掌握的基础，众所周知，在计算机的世界里，基础的数据结构只有两种，一种是线性连续的存储结构–数组，还有一种是随机的存储结构—链表，很多知名或者常用的数据结构都是基于这两种基础数据结构衍生出来的，今天介绍的队列也一样，队列如它的名字，是一种先进先出(FIFO)的数据结构,在我们的实际生活或者技术方面由很广泛的应用，比如各种消息队列，阻塞队列，等等。。。
队列常用API定义
package com.tangbaobao.data.queue;
/**
* @author tangxuejun
* @version 2018/9/29 8:37 PM
*/
public interface MyQueue<E> {
/**
* 入队
* @param e
*/
void enqueue(E e);
/**
* 出对
* @return
*/
E dequeue();
/**
* 获取对首元素
* @return
*/
E getFront();
/**
* 获取队里大小
* @return
*/
int getSize();
/**
* 队列是否为空
* @return
*/
boolean isEmpty();
}
用线性表实现队列
在Java中jdk已经帮我们封装好了基于数组的动态数组–ArrayList，这个例子就用基于ArrayList的来讲述队列，从某种角度来看，ArrayList其实也是队列，但是为了更加方便的展示，我们手动实现；
package com.tangbaobao.data.queue;
import java.util.ArrayList;
/**
* @author tangxuejun
* @version 2018/9/29 8:43 PM
*/
public class MyQueueArray<E> implements MyQueue<E> {
private ArrayList<E> list;
public MyQueueArray() {
list = new ArrayList<>();
}
public MyQueueArray(int capacity) {
list = new ArrayList<>(capacity);
}
@Override
public void enqueue(E e) {
list.add(e);
}
@Override
public E dequeue() {
E e = list.get(0);
list.remove(0);
return e;
}
@Override
public E getFront() {
return list.get(0);
}
@Override
public int getSize() {
return list.size();
}
@Override
public boolean isEmpty() {
return list.isEmpty();
}
}
基于数组直线的队列缺点：
上面的队列实现底层是基于动态数组的，我们也知道，每次队列的出对，都会进行一个队列长度-1的一个复制，这在队列中很浪费性能，但是如果不让复制，我们维护两个指针，分别指向开始元素和结束元素上，这样减少了队列的复制，但是又增加了空间的浪费，当队列出对之后，队列出对之后的空间就会被浪费，我们想利用出对之后的元素剩余的空间，就要用到循环队列。
循环队列的实现
package com.imooc.data.queue;
/**
* @author tangxuejun
* @version 2018/9/29 8:48 PM
*/
public class LoopQueue<E> implements MyQueue<E> {
//用来存储数据
private E[] data;
//指向头
private int front;
//指向尾
private int tail;
//队列的大小
private int size;
//初始化循环队列
//因为循环队列会浪费掉一个空间，所以我们初始化队列的时候应该+1
public LoopQueue(int capacity) {
data = (E[]) new Object[capacity + 1];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue() {
this(10);
}
/**
* 队列容量的实际大小
*
* @return
*/
public int getCapacity() {
return data.length - 1;
}
@Override
public void enqueue(E e) {
if ((tail + 1) % data.length == front) {
resize((getCapacity() * 2));
}
//新加元素入队
data[tail] = e;
//对尾指针进行修改
tail = (tail + 1) % data.length;
size++;
}
/**
* 重新计算容量
*
* @param newCapacity
*/
private void resize(int newCapacity) {
E[] newData = (E[]) new Object[newCapacity + 1];
for (int i = 0; i < size; i++) {
//新的队列对首还是从0开始，对原来的队列做偏移之后得到所有的值
newData[i] = data[(i + front) % data.length];
}
data = newData;
front = 0;
tail = size;
}
@Override
public E dequeue() {
if (isEmpty()) {
throw new RuntimeException("已经没有啦");
}
//获取对头元素
E datum = data[front];
//移除元素
data[front] = null;
//维护对头
front = (front + 1) % data.length;
//维护大小
size--;
//缩容操作
//当实际数目为容量的1/4时，将容量缩小为一半
if (size == getCapacity() / 4 && getCapacity() / 2 != 0) {
resize(getCapacity() / 2);
}
return datum;
}
@Override
public E getFront() {
if (isEmpty()) {
throw new RuntimeException("已经没有啦");
}
return data[front];
}
@Override
public int getSize() {
return size;
}
@Override
public boolean isEmpty() {
return tail == front;
}
}
循环队列和普通队列的性能分析
测试脚本：
package com.imooc.test;
import com.imooc.data.queue.LoopQueue;
import com.imooc.data.queue.MyQueue;
import com.imooc.data.queue.MyQueueArray;
import java.util.Random;
/**
* @author tangxuejun
* @version 2018/9/29 9:24 PM
*/
public class QueueTest {
public static void main(String[] args) {
int n = 100000;
System.out.println(getTime(new MyQueueArray<>(), n) + "s");
System.out.println(getTime(new LoopQueue<>(), n) + "s");
}
/**
* 测试性能
*
* @param queue 队列类型
* @param n 元素大小
* @return
*/
private static double getTime(MyQueue<Integer> queue, int n) {
long startTime = System.nanoTime();
Random random = new Random();
for (int i = 0; i < n; i++) {
queue.enqueue(random.nextInt(Integer.MAX_VALUE));
}
for (int i = 0; i < n; i++) {
queue.dequeue();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1_000_000_000.0;
}
}
数量为十万时候：我们可以看到基于ArrayList的queue花费时间在0.78s左右，而loopQueue则0.016s
数量为一百万的时候：