2.2.4 数组队列复杂度分析
2.2.4 数组队列的问题
从上面的执行结果我们可以看到，对于队列的执行来说，删除队首元素，后面的元素就要往前移动，如果，有一个ｎ个元素的队列，数组下标 0 的一端是队首，入队操作（void enqueue(E e)）就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除（E dequeue()）队首元素，后面的元素就要往前移动，我们可以想象一下，有一个 10000 的元素，我们从下标 0 开始添加，添加完成后，删除 队首的元素，那么我们需要移动 9999 次， 这个操作的复杂度，对于 数组队列来说是非常耗时的一个操作。
如下图所示：
2.3 队列的实现（循环队列）
2.3.1 循环队列
每当我们删除队首元素，后面的元素就要往前移动，因为，我们可以使用另一种方式来实现队列，也就是我们上面提到的 链式存储，也称 循环队列，这种方式是使用 链表 实现，比如：有两个指针，front 指向队头，tail 指向对尾元素的下一个位置，元素出队时 front 往后移动，如果到了对尾则转到头部，同理入队时 tail 后移，如果到了对尾则转到头部，这样通过下标 front 出队时，就不需要移动元素了,如果当我们的 front == tail的时候，则说明队列为空。如下图所示：
这样我们的删除操作就变成了一个O(1) 的操作，如果当我们的 tail 满了，但是 front 前面还有空间，我们可以将 tail 引入之前在 front 前面删除的下标中 ，这样我们又可以继续添加数据了，这就是循环队列的来由，我们可以把我们的数组队列看成一个 “环”，7 之后的索引是 0 ，什么时候我们的队列才会满呢？当我们的 tail + 1 = front的时候，就说明我们的队列才算真正的满了，如下图所示：
那么，这个时候 front == tail为空 既可以标识为空也可以用于堆满，因此我们可以用 (tail + 1) % c == front的表示队列满了，在这里 c = 8就是我们队列的长度，例如我们的 front 指的是 2 而我们的 tail 指的是 1 的话，那么这个队列就是满的，因为 （1+1）% 8 = 2，大家可以想象一下，我们的钟表，我们的钟表十一点钟下一个时间，我们可以叫12点也可以叫0点，之后又变成了一点两点三点以此类推，我们整个循环队列的就想钟表一样形成了一个环。
注意：在这里我们需要在 capacity 中浪费一个空间，用来判断队列是否满了，因此我们需要在用户传递队列大小的时候，进行 +1 操作，再添加一个元素空间。
2.3.1 循环队列编码实现
首先我们需要以下几个元素：
int getSize(); // 获取队列的元素多少
boolean isEmpty(); //查看队列是否为空
void enqueue(E e); //添加队列元素
E dequeue(); //删除队列队首元素
E getFront(); //获取队首队列元素
1、接口类：
public interface Queue<E> { int getSize(); boolean isEmpty(); void enqueue(E e); E dequeue(); E getFront(); }
2、接口实现类：
public class LoopQueue<E> implements Queue<E> { private E[] data;//存放的元素 private int front, tail;//两个指针 private int size;//元素个数 public LoopQueue(int capacity){ data = (E[])new Object[capacity + 1];//进行 +1 操作，用来判断队列是否满了 front = 0; tail = 0; size = 0; } public LoopQueue(){ this(10); } public int getCapacity(){ return data.length - 1;//获取数据长度，需要在原来的基础上 -1 } @Override public boolean isEmpty(){ return front == tail;//判断队列是否满了，只需要判断是否 front == tail } @Override public int getSize(){ return size; } @Override public void enqueue(E e){//添加元素 if((tail + 1) % data.length == front)//如果判断 (tail + 1) % c == front 成立，表示队列满了，自动扩容 resize(getCapacity() * 2);//扩容原来的两倍 data[tail] = e; tail = (tail + 1) % data.length; size ++; } @Override public E dequeue(){//删除元素 if(isEmpty())//判断是否为空 throw new IllegalArgumentException("Cannot dequeue from an empty queue."); E ret = data[front];//获取队首元素 data[front] = null;//设置为null front = (front + 1) % data.length;//设置新队首的下标位置 size --;//大小 -1 if(size == getCapacity() / 4 && getCapacity() / 2 != 0)//如果长度大小为 getCapacity() / 4 并且 getCapacity() / 2 != 0 的时候，自动缩减 resize(getCapacity() / 2); return ret; } @Override public E getFront(){//获取队首元素 if(isEmpty()) throw new IllegalArgumentException("Queue is empty."); return data[front]; } private void resize(int newCapacity){//扩容操作 E[] newData = (E[])new Object[newCapacity + 1]; for(int i = 0 ; i < size ; i ++) newData[i] = data[(i + front) % data.length]; data = newData; front = 0; tail = size; } @Override public String toString(){ StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size = %d , capacity = %d\n", size, getCapacity())); res.append("front ["); for(int i = front ; i != tail ; i = (i + 1) % data.length){ res.append(data[i]); if((i + 1) % data.length != tail) res.append(", "); } res.append("] tail"); return res.toString(); } public static void main(String[] args){ LoopQueue<Integer> queue = new LoopQueue<>(5); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println(queue); if(i % 2 == 0){ queue.dequeue(); System.out.println(queue+"：================"+i % 2); } } } }
3、执行结果：
Queue: size = 1 , capacity = 5 front [0] tail Queue: size = 0 , capacity = 5 front [] tail：================0 Queue: size = 1 , capacity = 5 front [1] tail Queue: size = 2 , capacity = 5 front [1, 2] tail Queue: size = 1 , capacity = 2 front [2] tail：================0 Queue: size = 2 , capacity = 2 front [2, 3] tail Queue: size = 3 , capacity = 4 front [2, 3, 4] tail Queue: size = 2 , capacity = 4 front [3, 4] tail：================0 Queue: size = 3 , capacity = 4 front [3, 4, 5] tail Queue: size = 4 , capacity = 4 front [3, 4, 5, 6] tail Queue: size = 3 , capacity = 4 front [4, 5, 6] tail：================0 Queue: size = 4 , capacity = 4 front [4, 5, 6, 7] tail Queue: size = 5 , capacity = 8 front [4, 5, 6, 7, 8] tail Queue: size = 4 , capacity = 8 front [5, 6, 7, 8] tail：================0 Queue: size = 5 , capacity = 8 front [5, 6, 7, 8, 9] tail
Queue：大小个数
capacity：是队列长度，可以看到自动扩容和缩减
front：队首 tail：队尾
2.3.2 循环队列时间复杂度
方法 时间复杂度
void enqueue(E e) O(1) 均摊
E dequeue() O(1) 均摊
E getFront() O(1)
int getSize() O(1)
boolean isEmpty() O(1)
2.3 顺序存储和循环队列性能对比
测试代码：
public class Main { // 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒 private static double testQueue(Queue<Integer> q, int opCount){ long startTime = System.nanoTime(); Random random = new Random(); for(int i = 0 ; i < opCount ; i ++) q.enqueue(random.nextInt(Integer.MAX_VALUE)); for(int i = 0 ; i < opCount ; i ++) q.dequeue(); long endTime = System.nanoTime(); return (endTime - startTime) / 1000000000.0; } public static void main(String[] args) { int opCount = 100000; ArrayQueue<Integer> arrayQueue = new ArrayQueue<>(); double time1 = testQueue(arrayQueue, opCount); System.out.println("ArrayQueue, time: " + time1 + " s"); LoopQueue<Integer> loopQueue = new LoopQueue<>(); double time2 = testQueue(loopQueue, opCount); System.out.println("LoopQueue, time: " + time2 + " s"); } }
执行结果：
ArrayQueue, time: 3.552273371 s LoopQueue, time: 0.011760769 s
我们可以看到 LoopQueue 性能是远远高于 ArrayQueue 的，我们如果把数据加大 ，差异会更加明显，如果是 1000000 的话，我的新电脑是 ArrayQueue：234s，而LoopQueue 依旧是 0.几秒，大家可以自行测试感受下，不过就算是新电脑，在 1000000 数据下，也要等待一会才能执行完成。
到这里栈和队列就讲完了，大家文章中有改进的地方或者有什么不懂的地方，欢迎大家在下面留言，下一篇，我们将讲解数据结构中最重要一个知识点——链表，喜欢的可以关注我，我是牧小农，我喂自己带盐，学习路上你我同行，大家加油！
