一.队列 Queue
队列也是一种线性结构
相比数组，队列对应的操作是数组的子集
只能从一端（队尾）添加元素，只能从另一端（队首）取出元素。
（排队）
队列是一种先进先出的数据结构（先到先得）FIFO(First In First Out)
二.数组队列的实现（基于动态数组）
Interface Queue<E> 接口设置5个方法
void enqueue(E e) 入队 O(1) 均摊
E dequeue() 出队 O(n) （出队后会将后续的元素向前挪一个单位，所以在出队操作上性能比较差）
E getFront() 查看队首元素（只对队首的元素感兴趣） O(1)
int getSize() 队列中的元素个数 O(1)
boolean isEmpty() 队列是否为空 O(1)
public interface Queue<E> {
int getSize();
boolean isEmpty();
void enqueue(E e);
E dequeue();
E getFront();
}ArrayQueue<E>实现接口Interface Queue<E>
public class ArrayQueue<E> implements Queue<E>
1.基本的构造方法
private Array<E> 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();
}
2.入队
@Override
public void enqueue(E e) {
array.addLast(e);
}
3.出队
@Override
public E dequeue() {
return array.removeFirst();
}
4.查看队首元素
@Override
public E getFront() {
return array.getFirst();
}
5.重写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("]");
return res.toString();
}
数组队列的问题：出队时间复杂度为O(n)级别（底层实现过程：取出队首元素，后续的元素要依次向前挪一位）
三.循环队列
初始时，front=tail=0，front指向队列第一个元素，tail指向队尾最后一个元素的下一位。只有队列中没有元素的情况，front才会与tail相等。
Eg:
1.基本情况
入队操作（对tail进行维护，即tail++，front不动）
a入队，front=0 tail++即tail=1
front [a]
b入队，front=0 tail++即tail=2
front [a, b]
c入队，front=0 tail++即tail=3
front [a, b, c]
出队操作（对front进行维护，即front++，tail不动）
a出队，tail=3 front++即front=1
front [b, c]
b出队，tail=3 front++即front=2
front[c]
c出队，tail=3 front++即front=3
数组为空，此时front == tail
2.循环（数组看为一个环）
假设capacity=8，0 1 2 3 4 5 位置均有元素 front=0，tail=6
先进行两次出队操作，2 3 4 5 位置有元素 front=2，tail=6
在进行两次入队操作，2 3 4 5 6 7位置有元素，此时size=capacity=8，即已将队列的空间加满，但队首前面部分有进行出队操作后空出来的2个单位的空间
再进行入队操作时，进行循环，该元素就加到0位置的元素，此时 front=2，tail=1，此时0 2 3 4 5 6 7位置有元素，1位置无元素。
若再进行入队操作，front=tail=2，与上边front==tail对列为空的定义冲突，所以再进行入队操作就需要扩容，1位置上始终无元素，即capacity中有意识地浪费一个空间。
所以，有当（tail+1）% capacity = front表示队列已满，需要扩容，但实际capacity浪费了一个空间无元素。
所以总结如下：
当front == tail时队列为空。
当（tail+1）% capacity == front时表示队列已满，需要扩容，但实际capacity浪费了一个空间。
四.循环队列的实现
LoopQueue<E>
void enqueue(E e) O(1) 均摊
E dequeue() O(1) 均摊
E getFront() O(1)
int getSize() O(1)
boolean isEmpty() O(1)
创建一个LoopQueue类实现Queue接口
public class LoopQueue<E> implements Queue<E>
1.基本的构造方法
需要注意的几点：
a.除了初始化数组以外，还要初始化front和tail作为首元素和末尾元素的下一位的指向，size实际可以由front与size得到。
b.当用户初始化输入capacity时，需要在构造函数中对capacity进行+1的操作，因为实际capacity中浪费了一个空间。
c.同理，getCapacity()方法就需要得到的data.length进行-1的操作。
d.对于判断队列是否为空的方法判断标准则为 front == tail。
private E[] data;
private int front, tail;
private int size; public LoopQueue(int capacity){
data = (E[])new Object[capacity + 1]; //浪费了一个单位 需要+1
front = 0;
tail = 0;
size = 0;
} public LoopQueue(){
this(10);
} public int getCapavity(){
return data.length - 1; //浪费了一个单位的空间，实际空间需要-1
} @Override
public boolean isEmpty() {
return front == tail;
} @Override
public int getSize() {
return size;
}
2.resize()方法
在进行入队和出队时，有时候需要进行必要的resize()操作来改变循环队列的capacity
需要注意：
a.初始化newData时，容量为newCapacity+1
b.两种遍历方式
c.front =0；
tail = size；
private void resize(int newCapacity){
E[] newData = (E[])new Object[newCapacity + 1];
for(int i = 0 ; i < size ; i ++){
newData[i] = data[ (i + front) % data.length ];
}
// for(int i = front ; i != tail ; i = (i+1) % data.length){
// newData[i] = data[i];
// }
data = newData;
front = 0;
tail = size;
}3.入队
需要注意：
a.首先判断队列是否满，满的话进行扩容，扩容时不可使用data.length，因为data.length比getCapacity()方法多1
b.tail = (tail + 1) % data.length 而不是 tail ++；
c.维护size，进行size++
@Override
public void enqueue(E e) {
if((tail + 1) % data.length == front) {
resize(2 * getCapacity()); //没有使用data.length，是因为data.length比getCapacity多1
} data[tail] = e;
tail = (tail + 1) % data.length;
size ++;
}
4.出队
需要注意:
a.首先判断队列是否为空
b.先取出data[front]给res，再使data[front] = null，避免浪费空间
c.移动front front = (front + 1) % data.length，而不是front ++
d.维护size，进行 size --
e.进行判断缩容
@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; }
5.查看队首元素
@Override
public E getFront() {
if(isEmpty()){
throw new IllegalArgumentException("Queue is empty");
}
return data[front];
}
6.重写toString()方法，使输出更具有可读性
需要注意：
a.输出capacity为getCapacity()，而不是data.length
b.两种遍历方式
public String toString() {
StringBuilder res = new StringBuilder();
res.append(String.format("Queue: size = %d , capacity = %d%n", size, getCapacity())); //使用getCapacity()而不是data.length
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(", ");
}
// for(int i = 0 ; i < size ; i ++){
// res.append(data[( i + front ) % data.length]);
// if((i + front) % data.length != tail - 1 )
// res.append(", ");
// }
res.append("] tail");
return res.toString();
}总结：
循环队列复杂主要复杂在三点：
a.getCapacity()方法得到的为data.length-1
b.将队列看为环进行循环，front和tail的变化，尤其是tail的变化
c.在方法中对整个队列的遍历需要考虑循环因素的影响
但是出队的复杂度为O(1)使循环队列在出队时有很好的性能。
对于循环队列的逻辑和代码还需要好好理解，尤其是遍历部分。