数组队列存在的问题是，当队首元素出队之后，所有剩余元素都需要向前移动，这样时间复杂度是O(n)

这里引入循环队列，依靠移动front和tail的位置保持队列的首尾位置，这样减小了时间复杂度。



那么与数组队列不同的地方还在于，当tail已经移动到索引为7的位置后，下一次再有元素入队，tail实际上会移动到索引为0的位置，所谓循环队列，应该把队列看作是一个圆环。



最后，对于capacity为8的情况，当tail在索引1，此时再有元素入队，tail++则会等于front，但队列并不为空，因此这里需要再添加一个判断，如果（tail + 1）% c == front则表示队列满。



循环队列的特点就在于循环移动，更具体一些理解，可以以钟表为例，当时间来到1点之后，下一个小时可以叫做12点同样也可以叫做0点，这就是一个循环，循环队列的索引就像钟表一样形成了一个环。

具体实现：

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);
     }

     public int getCapacity(){
         return data.length - 1;
     }

     @Override
    public boolean isEmpty(){
         return front ==tail;
     }

     @Override
    public int getSize(){
         return size;
     }
     @Override
    public void enqueue(E e){
         if ((tail + 1) % data.length == front)
             resize(getCapacity() * 2);
         data[tail] = e;
         tail = (tail + 1) % data.length;
         size ++;
     }

     @Override
     public E dequeue(){
         if(isEmpty())
             throw new IllegalArgumentException("Cannot dequeueu 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;
     }

     @Override
     public E getFront(){
         if (isEmpty())
             throw new IllegalArgumentException("Queue is empty");
         return data[front];
     }

     public void resize(int newCapacity){
         E[] newData = (E[]) new Object[newCapacity + 1];
         for(int i = 0; i < size; i ++)
             newData = data[(i + front) % data.length];
         data = newData;
         front = 0;
         tail = size;
     }

    @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);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

————————————————

原文链接：「Forizon」 https://blog.csdn.net/hesongzefairy/article/details/104480440

数组队列存在的问题是，当队首元素出队之后，所有剩余元素都需要向前移动，这样时间复杂度是O(n)

这里引入循环队列，依靠移动front和tail的位置保持队列的首尾位置，这样减小了时间复杂度。



那么与数组队列不同的地方还在于，当tail已经移动到索引为7的位置后，下一次再有元素入队，tail实际上会移动到索引为0的位置，所谓循环队列，应该把队列看作是一个圆环。



最后，对于capacity为8的情况，当tail在索引1，此时再有元素入队，tail++则会等于front，但队列并不为空，因此这里需要再添加一个判断，如果（tail + 1）% c == front则表示队列满。



循环队列的特点就在于循环移动，更具体一些理解，可以以钟表为例，当时间来到1点之后，下一个小时可以叫做12点同样也可以叫做0点，这就是一个循环，循环队列的索引就像钟表一样形成了一个环。

具体实现：

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);
     }

     public int getCapacity(){
         return data.length - 1;
     }

     @Override
    public boolean isEmpty(){
         return front ==tail;
     }

     @Override
    public int getSize(){
         return size;
     }
     @Override
    public void enqueue(E e){
         if ((tail + 1) % data.length == front)
             resize(getCapacity() * 2);
         data[tail] = e;
         tail = (tail + 1) % data.length;
         size ++;
     }

     @Override
     public E dequeue(){
         if(isEmpty())
             throw new IllegalArgumentException("Cannot dequeueu 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;
     }

     @Override
     public E getFront(){
         if (isEmpty())
             throw new IllegalArgumentException("Queue is empty");
         return data[front];
     }

     public void resize(int newCapacity){
         E[] newData = (E[]) new Object[newCapacity + 1];
         for(int i = 0; i < size; i ++)
             newData = data[(i + front) % data.length];
         data = newData;
         front = 0;
         tail = size;
     }

    @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);
            if((i + 1) % data.length != tail)
                res.append(", ");
        }
        res.append("] tail");
        return res.toString();
    }
}

————————————————

原文链接：「Forizon」 https://blog.csdn.net/hesongzefairy/article/details/104480440