一、简介
队列是一种特殊的线性表，特殊之处在于它只允许在表的前端（front）进行删除操作，而在表的后端（rear）进行插入操作，和栈一样，队列是一种操作受限制的线性表。进行插入操作的端称为队尾，进行删除操作的端称为队头。——出自百度百科
- 队列的应用场景
- 生活中的排队
二、队列的实现
实现这个队列在这里我选择复用之前实现的数组的一些方法，链接如下：
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}
将实现的Array类拷贝过来之后，然后我们再创建一个接口，这个接口的方法如上所示，getSize()方法是获取队列中元素的个数，isEmpty()是判断队列中是否为空，enqueue()方法是向队列中添加一个E类型的元素e，dequque()方法是让队列中队首的元素进行出队，getFront()是查看队首的元素。
三、实现类的设计
public class ArrayQueue<E> implements Queue<E> {
private Array<E> array;
public ArrayQueue(int capacity){
array = new Array<>(capacity);
}
public ArrayQueue(){
array = new Array<>();
}
}
创建完接口之后再创建一个实现类ArrayQueue，因为需要复用引入进来的Array类，所以先声明一个Array类型的参数array，然后进行构造方法的编写。第一个构造方法是有参的，适用于用户已知需要多大容量的情况下，参数为整形的capacity，意思是可以传入队列的容量，所以在方法中就直接实例化Array类并将capacity传入进去。再编写一个无参的构造方法，这个方法适用于不知道容量的情况，所以再方法中直接实例化Array类。
- getSize()、isEmpty()方法
@Override
public int getSize(){
return array.getSize();
}
@Override
public boolean isEmpty(){
return array.isEmpty();
}
getSize()方法是为了获取队列中元素的个数，所以直接调用array类的getSize()方法即可。isEmpty()方法是为了判断队列中是否为空，所以也就是直接调用Array类中的方法即可。
- getCapacity()方法
public int getCapacity(){
return array.getCapacity();
}
getCapacity()方法是为了获取队列中的容量，那么是同样的调用Array类的getCapacity方法即可。
- enqueue()、dequeue()、getFront()方法
@Override
public void enqueue(E e){
array.addLast(e);
}
@Override
public E dequeue(){
return array.removeFirst();
}
@Override
public E getFront(){
return array.get(0);
}
第一个方法是入队方法，因为队列的特性是先入先出的，所以添加元素要向队列的对位添加，所以调用Array类的addLast()方法即可，同样的dequeue()方法是需要从队首删除一个元素的，所以调用Array类的removeFirst()方法即可。第三个方法是获取队首的元素并进行返回，因为这个队列是基于数组进行实现的，所以直接适用get()方法，参数传入0即可。
- toString()方法
@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("] tail");
return res.toString();
}
这个方法主要用于进行函数的测试。
四、复杂度分析
getSize()为O(1)的时间复杂度
isEmpty()为O(1)的时间复杂度
enqueue(E)因为是向数组的末尾进行添加，所以是O(1)的复杂度。
dequeue()出队操作因为是从队首进行元素的删除，删除之后还需要将后面的元素向前移动，所以复杂度是O(n)的。
getFront()方法直接通过数组的get()方法即可实现，所以是O(1)的。
注意：实现的队列的方法中出队操作是比较耗时的，虽然在元素个数较少的时候这种时间的消耗可以忽略不计，但是在元素非常多的情况下对效率的影响是很大的，所以接下来我们要对队列进行改进。这就是下面要介绍的循环队列。
五、循环队列的设想
-
当数组中没有元素时，队首和队尾相同
image.png
-
当数组中进行元素添加之后，只需进行tail++即可
image.png
-
队首元素进行出队之后，只需进行front++即可，这样不需要每个元素都向前移动，所以也就减小了时间消耗。
image.png
-
再次添加元素，tail进行++操作，此时tail就不要进行++了，因为再次++就会出现front==tail的情况，这和空数组时是类似的。所以此时数组就是满的了。
image.png
- 计算队列情况的公式
tail = (当前最后元素的索引 + 1) % 数组容量;
front = (tail + 1) % capacity; 数组为满
front == tail 数组为空
六、循环队列的实现
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];
front = 0;
tail = 0;
size = 0;
}
public LoopQueue(){
this(10);
}
}
创建一个类LoopQueue实现Queue接口，其中包含三个属性，首先是创建了一个E类型的数组data，然后是设置了队首和队尾，第三个是统计队列元素个数的size属性。定义完属性之后再来编写循环队列的构造方法，首先第一个是一个有参的构造方法，参数是整形的capacity，也就是容量。
在方法中首先是将数组data进行初始化，这里可能有人会想，为什么要把容量加1呢？原因是因为循环队列需要有意的浪费一个空间，所以需要将数组的容量设置为用户传入的容量+1，然后将fornt、tail和size都初始化为0。接着是无参构造方法，这里就直接复用有参构造方法将容量设置为10。
- getCapacity()、isEmpty()、getSize()方法
public int getCapacity(){
return data.length - 1;
}
@Override
public boolean isEmpty(){
return front == tail;
}
@Override
public int getSize(){
return size;
}
getCapacity()方法是为了获取队列的容量，因为在初始化数组时容量设置的比用户传入的容量多1个，所以在这里应该将数组的长度-1，这样便可以计算出队列可用的容量。isEmpty()方法可以通过第五点循环队列的设想看出当数组为空时，front和tail是相等的。getSize()方法就很简单啦，直接返回size即可。
- resize()方法
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;
tail = size;
}
resize()方法用于进行数组的扩容操作，在这里需要传入扩容需要的容量。在方法中首先需要创建一个E类型的数组newData，并将容量传入，具体为什么需要将容量+1，还是因为循环队列需要对1个空间进行浪费。然后对原数组也就是data进行循环，将newData的第1个元素也就是0的位置，赋值为data的front。这里为什么要这么写，也是因为队列是循环的。循环结束后只需要将data指向newData，front赋值为0，tail与元素个数一致即可。
- enqueue()方法
@Override
public void enqueue(E e){
if ((tail + 1) % data.length == front){
resize(getCapacity() * 2);
}
data[tail] = e;
tail = (tail + 1) % data.length;
size++;
}
enqueue方法是向队列中添加元素，首先需要判断数组是否为满，因为队列是循环的，所以需要使用(tail + 1) % data.length == front计算数组的容量情况，当数组为满时需要进行扩容，这里我就将新的数组扩容为原来的2倍了。然后将e添加到数组中的最后一个位置，然后对tail和size进行维护。
- dequeue()
@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;
}
在进行出队方法编写时首先需要判断当前数组是否为空，如果为空就抛出异常。因为需要将出队的元素进行返回，所以先将队首的元素进行保存。然后将队首的元素置为null。然后对front和size进行维护。因为是出队操作，所以可能需要进行缩容的操作，在这里先进行判断如果条件满足的话就将容量缩小至原来的二分之一。最后将保存的结果返回。
- getFront()方法
@Override
public E getFront(){
if (isEmpty()){
throw new IllegalArgumentException("Queue is empty.");
}
return data[front];
}
getFront()方法非常简单，首先将数组进行判断，如果为空抛出异常。不为空就将数组中的front位置的元素进行返回。
- toString()
@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();
}
最后为了方便测试，我们将toString方法进行重写，在这里特别要注意的一点就是循环的时候，需要从front位置开始，到tail位置结束，可是因为是循环队列的缘故tail很有可能小于front。那么就使用 i != tail 进行判断，然后对i进行增加。然后将data[i]进行append。最后将res进行返回即可。
就这样，我们就实现了两种队列。有兴趣的可以创建测试用例进行测试，测试过之后就会发现用了这么长时间实现的循环队列的效率真的很高呢！
网友评论