循環(huán)隊(duì)列的優(yōu)點(diǎn)

普通隊(duì)列出隊(duì)操作開銷大：在出隊(duì)操作時，索引為0后面的所有元素，都需要往前移動一位，元素越多，消耗的時間也越多，時間復(fù)雜度為O(N)。

循環(huán)隊(duì)列的邏輯：

1、當(dāng)元素較少時（tail位置在front后面），循環(huán)隊(duì)列與普通隊(duì)列出隊(duì)操作一樣，入隊(duì)的元素將會放在tail的位置上，隨后執(zhí)行tail++操作；出隊(duì)時front位置上的元素將會置null，隨后執(zhí)行front++操作；此時仍能保持著tail位置在front后面的狀態(tài)，如下圖所示：

2、當(dāng)元素繼續(xù)添加，最后一個元素將放到索引為7的位置，此時tail位置將會移動到隊(duì)首前面索引為0的位置上，此時tail在數(shù)組的索引為變?yōu)椋?tail+ 1 )% capacity如下圖所示：

3、當(dāng)元素繼續(xù)添加時，元素將會在tail位置上添加，tail繼續(xù)往后移動，如下圖所示：

4、繼續(xù)添加元素，當(dāng)tail與front還相距一個單位時，即此時數(shù)組還有一個空余存儲空間，但當(dāng)前數(shù)組已經(jīng)不能繼續(xù)實(shí)現(xiàn)循環(huán)隊(duì)列的插入操作了，因?yàn)檠h(huán)隊(duì)列判斷隊(duì)列為空的條件就是front == tail，所以此時需要進(jìn)行擴(kuò)容操作；因此此處有意識的浪費(fèi)了一個空間。

此處可以推出，循環(huán)隊(duì)列元素滿的條件為：tail +1 == front(初步得出，后續(xù)會完善為(tail + 1) % capacity == front )

5、適當(dāng)情況下，此若時持續(xù)進(jìn)行出隊(duì)操作，front的位置也將會從數(shù)組最右端跳轉(zhuǎn)到數(shù)組最左端開始。此時front在數(shù)組的索引為變?yōu)椋?front + 1 )% capacity

代碼實(shí)現(xiàn)：（相關(guān)視頻教程分享：java視頻教程）

package dataStructure.chapter3;  /**  * @Author: zjtMeng  * @Date: 2019/12/28 20:13  * @Version 1.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];     }      public LoopQueue(){         this(10);     }      public int getCapacity(){         return data.length-1;     }      /**      * 循環(huán)隊(duì)列入隊(duì)操作      * @param e      */     @Override     public void enqueue(E e) {         //循環(huán)隊(duì)列元素滿的判斷條件,如果滿了就進(jìn)行擴(kuò)容操作，擴(kuò)大兩倍         if ((tail+1)%data.length == front)             resize(2 * getCapacity());         data[tail] = e;         tail = (tail + 1) % data.length;         size ++;      }      /**      * 循環(huán)隊(duì)列擴(kuò)容      * @param newCapacity      */     private void resize(int newCapacity){         E[] newData = (E[]) new Object[newCapacity+1];         //循環(huán)隊(duì)列第一種遍歷方式         for (int i = 0 ; i < size ; i++ ){ //newData[]中的元素與data[]中的元素，一方面存在著front的偏移量，另一方面，data[]中的元素， //可能在有部分處于front前面，因此此處采用對數(shù)組長度取余，來判斷元素的位置             newData[i] = data[(i+front)%data.length];         }         data = newData;         front =0;         tail = size;      }      @Override     public E dequeue() {         //首先判斷隊(duì)列是否為空，如果為空則拋出異常         if (isEmpty())             throw new IllegalArgumentException("Cannot dequeue from an empty queue.");         E ret = data[front];         //引用地址需要置空，否則JVM不能及時回收空間，從而可能會出現(xiàn)OOM異常         data[front] = null;         front = (front + 1 )% data.length;         size--;         //如果元素?cái)?shù)量達(dá)到隊(duì)列容積的1/4，且隊(duì)列容積/2 不等于0時，進(jìn)行縮容操作         if (size == getCapacity() / 4 && getCapacity() / 2 != 0 )             resize(getCapacity() / 2);         return ret;     }      /**      * 查看隊(duì)首元素      * @return      */     @Override     public E getFront() {         if (isEmpty())             throw new IllegalArgumentException("Queue is empty.");         return data[front];     }      @Override     public int getSize() {         return size;     }      /**      * 判斷循隊(duì)列是否為空      * @return      */     @Override     public boolean isEmpty() {         return front == tail;     }      @Override     public String toString(){         StringBuilder res = new StringBuilder();         res.append(String.format("Queue: size = %d, capacity = %dn",size, getCapacity()));         res.append("front[");         //循環(huán)隊(duì)列遍歷的第二種方法         for (int i = front; i != tail; i = (i + 1) % data.length){             res.append(data[i]);             //循環(huán)隊(duì)列未遍歷到隊(duì)尾的標(biāo)志             if ((i + 1) % data.length != tail)                 res.append(", ");         }         res.append("] tail");         return res.toString();     } }

相關(guān)文章教程推薦：java入門教程