上一篇中基于数组实现了一个普通的队列 这个普通队列的出队操作 时间复杂度 是O(n)级别的

我们用一个容量为8的数组data来实现一个队列，此时队列中已经入队a,b,c,d,e五个元素，a处于队首位置，e处于队尾位置。此时我们将a元素进行出队操作，那么剩余的元素则需要向左移动。所以这个普通队列的出队操作时间复杂度是O(n)级别的

对于这种情况我们可能会想，我们能不能不移动剩余元素，实现一个性能更好的队列呢？

接下来我们就实现一个循环队列来解决这个问题。

我们先来分析一下如何实现一个循环队列：

仍旧以上面的图示进行分析，当队首元素a出队以后，剩余元素此时不进行移动。我们定义两个标识 front 和 tail

1. front：标识 队首位置，如下图元素b此时为队首元素
2. tail：标识 下次入队时元素插入的位置，如下图下次入队时元素插入位置为索引5的位置

那么之后进行出队、入队操作后我们只需要维护front、tail就可以了。

1. 出队：front往后移动一个位置
2. 入队：tai往后移动一个位置

接下来我们在分析一下特殊情况：

1. 初始情况下，队列中没有任何元素时，front和tail都指向同一个位置，也就是说如果 front == tail队列为空

2.

如果此时再次入队一个元素h，根据我们前面说的，tail需要往后移动一个位置。而此时tail++就会造成新的tail值超出了data数组的索引范围。既然我们要实现的是循环队列，那么对于此时这种情况我们肯定要让它循环起来。我们就要判断这个数组实现的队列是否已满，如果没有满的话说明front前面有空余的位置，我们需要将tail指向front前面的位置。

tail的值我们总结出计算方式为： tail = (tail + 1) % data.length

比如对于上面的情况tail = 7,此时入队元素h，tail = (7 + 1) % 8; tail = 0

3.

如上这种情况，如果此时再次入队一个元素，tail元素再次往后移动一个位置时那么此时tail == front，而之前我们分析过tail == front时队列为空。而此时tail == front时队列是满的，这就会产生冲突。因此当 (tail + 1)%data.leng == fron t的时候我们可以判定队列是满的，此时我们将tail位置闲置，浪费掉这个空间不再插入元素。此时，队列已满。

下面我们用代码实现一下：

public interface Queue<E> {
 void enqueue(E e);
 E dequeue();
 E getFront();
 int getSize();
 boolean isEmpty();
}
public class LoopQueue<E> implements Queue<E> {
//声明一个数组data用于保存数据
 private E[] data;
//声明队首和队尾指针变量
 private int front,tail;
//size用于表示队列元素个数
 private int size;
//指定容量的 构造函数 
 public LoopQueue(int capacity){
 //加一是因为循环队列会浪费一个空间位置
 data = (E[]) new Object[capacity + 1];
 front = 0;
 tail = 0;
 size = 0;
 }
//无参构造函数，默认容量为10
 public LoopQueue() {
 this(10);
 }
//扩容方法
 private void resize(int newCapacity){
 //新建一个扩容后的数组
 E[] newData = (E[]) new Object[newCapacity+1];
 //将原数组data变量保存到新数组中，这里要注意按照队列的顺序进行保存
 for(int i = 0;i < size; i++){
 newData[i] = data[(i+front) % data.length];
 }
 data = newData;
 front = 0;
 tail = size;

 }
//入队
 @ Override 
 public void enqueue(E e) {
 //首先判断队列是否已满，如果已满我们对其进行扩容
 if((tail + 1) % data.length == front){
 //扩容原来两倍
 resize(getCapacity()*2);
 }
 //将新元素插入到tail的位置
 data[tail] = e;
 //更新tail的值
 tail = (tail + 1) % data.length;
 size++;
 }
//出队
 @Override
 public E dequeue() {
 if( isEmpty ()){
 throw new IllegalArgumentException("empty");
 }
 //获取队首元素
 E ret = data[front];
 //内存回收
 data[front] = null;
 //更新front值
 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("empty");
 }
 return data[front];
 }
//队列长度
 @Override
 public int getSize() {
 return size;
 }
//队列是否为空
 @Override
 public boolean isEmpty() {
 return front == tail;
 }
//队列容量
 public int getCapacity(){
 return data.length - 1;
 }

 

 @Override
 public String toString() {
 StringBuilder sb = new StringBuilder();
 sb.append("loopqueue:");
 sb.append("front[");
 for(int i = front;i != tail;i = (i + 1) % data.length){
 sb.append(data[i]);
 if((i + 1) % data.length != tail){
 sb.append(",");
 }
 }
 sb.append("]end");
 return sb.toString();
 }
}