Question

数据结构篇|队列

Answer 1

实现这个队列在这里我选择复用之前实现的数组的一些方法，链接如下：

将实现的Array类拷贝过来之后，然后我们再创建一个接口，这个接口的方法如上所示， getSize() 方法是获取队列中元素的个数， isEmpty() 是判断队列中是否为空， enqueue() 方法是向队列中添加一个E类型的元素e， dequque() 方法是让队列中队首的元素进行出队， getFront() 是查看队首的元素。

创建完接口之后再创建一个实现类ArrayQueue，因为需要复用引入进来的Array类，所以先声明一个Array类型的参数array，然后进行构造方法的编写。第一个构造方法是有参的，适用于用户已知需要多大容量的情况下，参数为整形的 capacity ，意思是可以传入队列的容量，所以在方法中就直接实例化Array类并将capacity传入进去。再编写一个无参的构造方法，这个方法适用于不知道容量的情况，所以再方法中直接实例化Array类。

getSize()方法是为了获取队列中元素的个数，所以直接调用array类的getSize()方法即可。isEmpty()方法是为了判断队列中是否为空，所以也就是直接调用Array类中的方法即可。

getCapacity()方法是为了获取队列中的容量，那么是同样的调用Array类的getCapacity方法即可。

第一个方法是入队方法，因为队列的特性是先入先出的，所以添加元素要向队列的对位添加，所以调用Array类的addLast()方法即可，同样的dequeue()方法是需要从队首删除一个元素的，所以调用Array类的removeFirst()方法即可。第三个方法是获取队首的元素并进行返回，因为这个队列是基于数组进行实现的，所以直接适用get()方法，参数传入0即可。

这个方法主要用于进行函数的测试。

注意：实现的队列的方法中出队操作是比较耗时的，虽然在元素个数较少的时候这种时间的消耗可以忽略不计，但是在元素非常多的情况下对效率的影响是很大的，所以接下来我们要对队列进行改进。这就是下面要介绍的循环队列。

创建一个类LoopQueue实现Queue接口，其中包含三个属性，首先是创建了一个E类型的数组data，然后是设置了队首和队尾，第三个是统计队列元素个数的size属性。定义完属性之后再来编写循环队列的构造方法，首先第一个是一个有参的构造方法，参数是整形的capacity，也就是容量。
在方法中首先是将数组data进行初始化，这里可能有人会想，为什么要把容量加1呢？原因是因为循环队列需要有意的浪费一个空间，所以需要将数组的容量设置为用户传入的容量+1，然后将fornt、tail和size都初始化为0。接着是无参构造方法，这里就直接复用有参构造方法将容量设置为10。

getCapacity()方法是为了获取队列的容量，因为在初始化数组时容量设置的比用户传入的容量多1个，所以在这里应该将数组的长度-1，这样便可以计算出队列可用的容量。isEmpty()方法可以通过第五点循环队列的设想看出当数组为空时，front和tail是相等的。getSize()方法就很简单啦，直接返回size即可。

resize()方法用于进行数组的扩容操作，在这里需要传入扩容需要的容量。在方法中首先需要创建一个E类型的数组newData，并将容量传入，具体为什么需要将容量+1，还是因为循环队列需要对1个空间进行浪费。然后对原数组也就是data进行循环，将newData的第1个元素也就是0的位置，赋值为data的front。这里为什么要这么写，也是因为队列是循环的。循环结束后只需要将data指向newData，front赋值为0，tail与元素个数一致即可。

enqueue方法是向队列中添加元素，首先需要判断数组是否为满，因为队列是循环的，所以需要使用 (tail + 1) % data.length == front 计算数组的容量情况，当数组为满时需要进行扩容，这里我就将新的数组扩容为原来的2倍了。然后将e添加到数组中的最后一个位置，然后对tail和size进行维护。

在进行出队方法编写时首先需要判断当前数组是否为空，如果为空就抛出异常。因为需要将出队的元素进行返回，所以先将队首的元素进行保存。然后将队首的元素置为null。然后对front和size进行维护。因为是出队操作，所以可能需要进行缩容的操作，在这里先进行判断如果条件满足的话就将容量缩小至原来的二分之一。最后将保存的结果返回。

getFront()方法非常简单，首先将数组进行判断，如果为空抛出异常。不为空就将数组中的front位置的元素进行返回。

最后为了方便测试，我们将toString方法进行重写，在这里特别要注意的一点就是循环的时候，需要从front位置开始，到tail位置结束，可是因为是循环队列的缘故tail很有可能小于front。那么就使用 i != tail 进行判断，然后对i进行增加。然后将data[i]进行append。最后将res进行返回即可。