数据结构第三课了，今天我们再介绍一种很常见的线性表——队列
就像它的名字，队列这种数据结构就如同生活中的排队一样，队首出队，队尾进队。以下一段是百度百科中对队列的解释：
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。队列中没有元素时，称为空队列。
队列的数据元素又称为队列元素。在队列中插入一个队列元素称为入队，从队列中删除一个队列元素称为出队。因为队列只允许在一端插入，在另一端删除，所以只有最早进入队列的元素才能最先从队列中删除，故队列又称为先进先出（FIFO—first in first out）线性表。
队列主要分为顺序队列以及循环队列，在这我两种队列都会实现一下， 并在最后进行一下性能上的测试比较。
ok,让我们开始今天的学习吧。
首先，还是先创建一个队列的接口：
public interface Queue<E> { int getSize(); //得到队列元素个数 boolean isEmpty(); //判断队列是否为空 void enqueue(E e); //入队 E dequeue(); //出队 E getFront(); //查看队首元素 }
由于在<数据结构系列1>（https://www.cnblogs.com/LASloner/p/10721407.html）中我们已经实现了ArrayList，所以今天我们依旧就用Array来作为Queue的数据存储方式吧：
public class ArrayQueue<E> implements Queue<E> { //这里用的是自己实现的Array，当然读者可以直接用Java自带的ArrayList,效果相同 private Array<E> array=new Array<>(); //有参构造 public ArrayQueue(int capacity) { array=new Array<>(capacity); } //无参构造 public ArrayQueue() { array=new Array<>(); } //获取队列元素个数 @Override public int getSize() { return array.getSize(); } //判断队列是否为空 @Override public boolean isEmpty() { return array.isEmpty(); } //获得队列的容量 public int getCapacity(){ return array.getCapacity(); } @Override public void enqueue(E e) { array.addLast(e); } @Override public E dequeue() { return array.removeFirst(); } @Override public E getFront() { return array.get(0); }
@Override public String toString() { StringBuilder res=new StringBuilder(); res.append("Queue: "); res.append("front ["); for(int i = 0 ; i < array.getSize() ; i ++){ res.append(array.get(i)); if(i != array.getSize() - 1) res.append(", "); } res.append("] rear"); return res.toString(); } }
这并不是一件难事吧，那再让我们测试一下吧：
public static void main(String[] args) { ArrayQueue<Integer> queue = new ArrayQueue<>(); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println("入队："+queue); if(i % 3 == 2){ queue.dequeue(); System.out.println("出队："+queue); } } }
输出如下：
入队：Queue: front [0] rear 入队：Queue: front [0, 1] rear 入队：Queue: front [0, 1, 2] rear 出队：Queue: front [1, 2] rear 入队：Queue: front [1, 2, 3] rear 入队：Queue: front [1, 2, 3, 4] rear 入队：Queue: front [1, 2, 3, 4, 5] rear 出队：Queue: front [2, 3, 4, 5] rear 入队：Queue: front [2, 3, 4, 5, 6] rear 入队：Queue: front [2, 3, 4, 5, 6, 7] rear 入队：Queue: front [2, 3, 4, 5, 6, 7, 8] rear 出队：Queue: front [3, 4, 5, 6, 7, 8] rear 入队：Queue: front [3, 4, 5, 6, 7, 8, 9] rear
这样就算是实现了顺序队列了，但是呢，由于顺序队列存储数据的方式使用了之前封装好的ArrayList,并不能很好的体现队列的这种数据结构，都没使用到front和rear，接下来，我们再实现一下循环队列，以此更好的了解队列。
那之前先看看什么是循环队列：
public class LoopQueue<E> implements Queue<E>{ private E[] data; private int front;//队首 private int rear;//队尾 private int size; //有参构造 public LoopQueue(int capacity) { data =(E[])new Object[capacity+1];//浪费一个空间用作判断 front==(rear+1)%（capacity+1）时为满 front=0; rear=0; size=0; } //无参构造 public LoopQueue() { this(10); } //返回队列中元素的个数 @Override public int getSize() { return size; } //判断队列是否为空 @Override public boolean isEmpty() { return front==rear; } //返回队列容量 public int getCapacity(){ return data.length - 1; } //入队 @Override public void enqueue(E e) { if((rear+1)%data.length==front)//当队列满了之后扩容 resize(getCapacity()*2); data[rear]=e; rear=(rear+1)%data.length;//这里的data.length就代表Maxsize size++; } //出队 @Override public E dequeue() { if(isEmpty()) throw new IllegalArgumentException("Cannot dequeue from an empty queue."); E res=data[front]; data[front]=null; front=(front+1)%data.length; size--; if(size==getCapacity()/4&&getCapacity()/2!=0)//动态缩容 resize(getCapacity()/2); return res; } //获取队首元素 @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[(front+i)%data.length]; } data=newData; front=0; rear=size; } @Override public String toString() { StringBuilder res = new StringBuilder(); res.append(String.format("Queue: size = %d , capacity = %d\t", size, getCapacity())); res.append("front ["); for(int i = front ; i != rear ; i = (i + 1) % data.length){ res.append(data[i]); if((i + 1) % data.length != rear) res.append(", "); } res.append("] rear"); return res.toString(); } }
再写一个Main方法测试一下：
public static void main(String[] args) { LoopQueue<Integer> queue = new LoopQueue<>(); for(int i = 0 ; i < 10 ; i ++){ queue.enqueue(i); System.out.println("入队："+queue); if(i % 3 == 2){ queue.dequeue(); System.out.println("出队："+queue); } } }
输出：
入队：Queue: size = 1 , capacity = 10 front [0] rear 入队：Queue: size = 2 , capacity = 10 front [0, 1] rear 入队：Queue: size = 3 , capacity = 10 front [0, 1, 2] rear 出队：Queue: size = 2 , capacity = 5 front [1, 2] rear 入队：Queue: size = 3 , capacity = 5 front [1, 2, 3] rear 入队：Queue: size = 4 , capacity = 5 front [1, 2, 3, 4] rear 入队：Queue: size = 5 , capacity = 5 front [1, 2, 3, 4, 5] rear 出队：Queue: size = 4 , capacity = 5 front [2, 3, 4, 5] rear 入队：Queue: size = 5 , capacity = 5 front [2, 3, 4, 5, 6] rear 入队：Queue: size = 6 , capacity = 10 front [2, 3, 4, 5, 6, 7] rear 入队：Queue: size = 7 , capacity = 10 front [2, 3, 4, 5, 6, 7, 8] rear 出队：Queue: size = 6 , capacity = 10 front [3, 4, 5, 6, 7, 8] rear 入队：Queue: size = 7 , capacity = 10 front [3, 4, 5, 6, 7, 8, 9] rear
那现在，循环队列相关的代码就全部完成了，需要注意的是，我们实现的循环队列是可以动态扩容的，实际上我实现的所有的线性表都是动态扩容的，希望读者注意。
既然实现了两种队列，就自然的做一下比较吧，首先做一下性能比较：
测试函数如下：
public class PerformanceTest { private static double queueTest(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 = queueTest(arrayQueue, opCount); System.out.println("ArrayQueue, time: " + time1 + " s"); LoopQueue<Integer> loopQueue = new LoopQueue<>(); double time2 = queueTest(loopQueue, opCount); System.out.println("LoopQueue, time: " + time2 + " s"); } }
输出为：
ArrayQueue, time: 6.924613333 s
LoopQueue, time: 0.020527111 s
再看时间复杂度的比较：
ArrayQueue<E> void enqueue(E) O(1) E dequeue() O(n) E front() O(1) int getSize() O(1) boolean isEmpty O(1) LoopQueue<E> void enqueue(E) O(1) E dequeue() O(1) E front() O(1) int getSize() O(1) boolean isEmpty O(1)
经过对比不难看出，循环队列的效率要高于顺序队列，但是，也不得不说，循环队列在实现上要复杂一些。
哈哈，真是难得，竟然一天内更了两篇博文，继续加油！！
对于学习，四个字概括：至死方休
原文：https://www.cnblogs.com/LASloner/p/10834507.html