一.队列的概念
（1）队列也是一种线性结构
（2）相比数组，队列对应的操作是数组的子集
（3）只允许在一端插入数据操作，在另一端进行删除数据操作，进行插入操作的一端称为队尾（入队列），进行删除操作的一端称为队头（出队列）
（4）队列是一种先进先出的数据结构（FIFO）
此处我们先来学习一下顺序队列 ，顺序队列 就是用数组实现：比如有一个ｎ个元素的队列，数组下标0的一端是队头，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素，后面的元素就要往前移动，对应的时间复杂度就是O(n)。
image.png
对于队列，我们关注的相关实现如下：
image.png
二、代码实现
对于该节的相关代码，我们新建一个
package（Queue）,同时为了理解方便，此时把动态数组相关代码拷贝到该包中。1.先创建一个
Queue接口，里面定义上面所述的方法
package Queue;
public interface Queue<E> {
//获取队列中元素个数
int getSize();
//队列中元素是否为空
boolean isEmpty();
//入队列
void enqueue(E e);
//出队列
E dequeue();
//获取队首元素
E getFront();
}
2.创建一个类ArrayQueue实现Queue接口并重写Object类的toString()方法
package Queue;
public class ArrayQueue<E> implements Queue<E> {
private DynamicArray<E> array;
//构造函数，传入队列的容量capacity构造函数
public ArrayQueue(int capacity) {
array = new DynamicArray<E>(capacity);
}
//无参构造函数，默认队列的容量capacity=10
public ArrayQueue() {
array = new DynamicArray<E>();
}
//获取队列中元素数据是否为空
@Override
public boolean isEmpty() {
return array.isEmpty();
}
//获取队列中元素个数
@Override
public int getSize() {
return array.getSize();
}
//获取队列的容量
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();
}
//重写object类的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("] rear");//体现右侧为队尾
return res.toString();
}
}
3.测试
新建一个TestMain类，添加一个main函数来测试我们编写好的ArrayQueue类
相关代码如下：
package Queue;
public class TestMain {
public static void main(String[] args) {
ArrayQueue<Integer> queue = new ArrayQueue<Integer>();
for (int i = 0; i < 10; i++) {
queue.enqueue(i);
System.out.println(queue);
if(i%3==2){//每添加3个元素出队列一个
queue.dequeue();
System.out.println(queue);
}
}
}
}
image.png
三、数组队列的复杂度分析
image.png
对于出队的时间复杂度为O(n)的解释：
由于实现数组队列的底层是动态数组，入队操作就是通过数组下标一个个顺序追加，不需要移动元素，但是如果删除队头元素（removeFirst()方法），后面的元素就要往前移动，对应的时间复杂度就是O(n)。这样当有数组中有大量数据时性能肯定是不好的，下一节我们将进行改进，使得出队的时间复杂度为O(1)。
源码地址 https://github.com/FelixBin/dataStructure/tree/master/src/Queue
