Java队列Queue及循环队列

队列是一种线性结构。

相比数组，队列对应的操作是数组的子集。

只能从一段（队尾）添加元素，只能从另一端（队首取出元素）。

队列的操作：

队列的实现：

添加元素（入队）      ： void enqueue(E)
删除、取出元素（出队）      ：  E dequeue()。
取得队首元素             ：E getFront()
查看队列有多少元素  ：int getSize()
判断队列是否为空      ：boolean isEmpty()

Queue接口：

public interface Queue {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}

这里我们将复用之前我的一篇文章中讲到的数组类Array,这里就不进行展示了。有兴趣可以了解动态数组的操作：

• https://blog.csdn.net/qq_41723615/article/details/88413667
• https://blog.csdn.net/qq_41723615/article/details/85456789

ArrayQueue:基于Array类实现的队列

public class ArrayQueue implements Queue {
//创建私有Array对象
private Array 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.getFirst();
}
@Override
public String toString(){
StringBuilder res = new StringBuilder();
res.append("Queue: ");
res.append("front [");
//遍历array元素，逐次加入队列中
for(int i = 0 ; i res.append(array.get(i));
if(i != array.getSize() - 1) {
res.append(", ");
}
}
res.append("] tail");
return res.toString();
}
public static void main(String[] args) {
ArrayQueue 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);
}
}
}
}


打印结果：

下面对数组队列的操作，进行复杂度分析：

取出队列元素时间复杂度为O(n),每取出一个元素，后面的元素都要做相应的位置调整。怎么优化它呢？

没错，可以利用循环队列的实现。

当队列为空时，front和tail指向同一个地方。

当插入一个元素时：只需要维护tail这个位置

当出队一个元素时：只需要改变front的位置即可

当tail加满了怎么办？

此时可以把此数组队列看成一个环行结构。7位置紧接着0这个位置，两个位置是相连的，也就是环形结构。

那么当tail插入满了的时候，就可以重新利用前面取出的空间进行下面的操作了。

tail的计算公式：tail =（当前的索引+1）% （整个数组的长度）

当再入队一个元素时：

tail则继续 +1即可。

此时有一个空出来的位置，那么此位置下还能入队一个元素吗？

答案是不能，队列满的设计是：   

前面已经给出了队列空的设计：

如果再加入一个元素，则会与我们前面的设计产生矛盾。其实整个设计操作，就和时钟一样。

循环队列的实现：LoopQueue

此时不再复用之前实现的动态数组，这里将重新进行逻辑设计：

public class LoopQueue implements Queue {
//定义一个数组
private E[] data;
//定义用于描述队首，队尾的变量
private int front, tail;
//定义成员变量，描述队列有多少个元素
private int size;
//用户希望数组队列要传入多少元素
public LoopQueue(int capacity){
//capacity + 1：队列需要空出一个位置
data = (E[])new Object[capacity + 1];
//空队列初始化成员变量
frOnt= 0;
tail = 0;
size = 0;
}
//用户不知道要设置队列容量为多少时，新建队列默认容量为10
public LoopQueue(){
this(10);
}
//获取队列有多少个元素的个数
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return frOnt== tail;
}
@Override
public int getSize(){
return size;
}
//入队
@Override
public void enqueue(E e){
//根据设计要求，判断队列是否满了
if((tail + 1) % data.length == front) {
//扩容
resize(getCapacity() * 2);
}
//存放元素
data[tail] = e;
//当存放元素后，需要设置循环队列tail
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;
frOnt= (front + 1) % data.length;
size --;
if(size == 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 //把旧队列元素放入新队列空间
//偏移位置量：front
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 [");
//由于是循环操作，所以tail值可能比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 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] tail
Queue: size = 2 , capacity = 10
front [0, 1] tail
Queue: size = 3 , capacity = 10
front [0, 1, 2] tail
Queue: size = 2 , capacity = 5
front [1, 2] tail
Queue: size = 3 , capacity = 5
front [1, 2, 3] tail
Queue: size = 4 , capacity = 5
front [1, 2, 3, 4] tail
Queue: size = 5 , capacity = 5
front [1, 2, 3, 4, 5] tail
Queue: size = 4 , capacity = 5
front [2, 3, 4, 5] tail
Queue: size = 5 , capacity = 5
front [2, 3, 4, 5, 6] tail
Queue: size = 6 , capacity = 10
front [2, 3, 4, 5, 6, 7] tail
Queue: size = 7 , capacity = 10
front [2, 3, 4, 5, 6, 7, 8] tail
Queue: size = 6 , capacity = 10
front [3, 4, 5, 6, 7, 8] tail
Queue: size = 7 , capacity = 10
front [3, 4, 5, 6, 7, 8, 9] tail

下面对循环队列做时间复杂度分析：

虽然循环队列的实现比较复杂，不过相比性能考虑，是值得这么做的。

下面对数组队列及循环队列的性能进行对比：

import java.util.Random;
public class Main {
// 测试使用q运行opCount个enqueueu和dequeue操作所需要的时间，单位：秒
private static double testQueue(Queue q, int opCount){
long startTime = System.nanoTime();
Random random = new Random();
//入队
for(int i = 0 ; i q.enqueue(random.nextInt(Integer.MAX_VALUE));
}
//出队
for(int i = 0 ; i q.dequeue();
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int opCount = 100000;
//数组队列
ArrayQueue arrayQueue = new ArrayQueue<>();
double time1 = testQueue(arrayQueue, opCount);
System.out.println("ArrayQueue, time: " + time1 + " s");
//循环队列
LoopQueue loopQueue = new LoopQueue<>();
double time2 = testQueue(loopQueue, opCount);
System.out.println("LoopQueue, time: " + time2 + " s");
}
}


结果：

忽略硬件与JVM版本的影响。知道了队列的具体实现，之后，我需要知道队列其实对于队首可以多种定义，根据队列的应用场景的不同而定义。队列还分广义的队列，我实现的只是普通的队列，不过对于这种普通队列的实现，在应用算法的时候，有它重要的用处，例如广度优先遍历的应用，后续将会对广度优先遍历做进一步探究。