這篇文章帶給大家的內容是關於Java循環佇列的介紹(程式碼範例),有一定的參考價值,有需要的朋友可以參考一下,希望對你有幫助。
為了解決陣列佇列帶來的問題,這篇文章為大家介紹一下循環隊列。
想法分析圖解
囉嗦一下,由於筆者不太會弄貼出來的圖片帶有動畫效果,例如元素的移動或刪除(畢竟這樣看大家比較直覺),筆者在這裡只能透過靜態圖片的方式,幫助大家理解實現原理,希望大家不要見怪,如果有朋友知道如何搞的話,歡迎在評論區慧言。
在這裡,我們宣告了一個容量大小為8的數組,並標示了索引0-7,然後使用front
#和##tail#分別來表示隊列的,隊首和隊尾;在下圖中,
front和
tail#的位置一開始都指向是了索引0的位置,這意味著當
front == tai的時候
隊列為空
大家務必牢記這一點,以便區分後面介紹隊列快滿時的臨界條件
為了大家更能理解下面的內容,在這裡,我簡單做幾點說明
#front:表示隊列隊首,總是指向隊列中的第一個元素(當隊列空時,front指向索引為0的位置)
tail:表示隊列隊尾,總是指向隊列中的最後一個元素的下一個位置
tail的位置,進行
tail 操作
front的位置,進行
front 操作上面所說的,元素進行入隊和出隊操作,都簡單的進行操作,來維護
tail和
front的位置,其實是不嚴謹的,正確的維護tail的位置應該是(tail 1) % capacity,同理front的位置應該是(front 1 ) % capacity,這也是為什麼叫做循環隊列的原因,大家先在這裡知道下,暫時不懂也沒關係,後面相信大家會知曉。
現在,我們再來幾個元素b、c、d、e進行入隊操作,看一下此時的示意圖:
想必大家都能知曉示意圖是這樣,好像沒什麼太多的變化(還請大家別著急,筆者這也是方便大家理解到底是什麼循環隊列,還請大家原諒我O(∩_∩)O哈!)#看完了元素的入隊的操作情況,那現在我們看一下,元素的出隊操作是什麼樣的?
元素a出隊,示意圖如下:
我們再次進行元素b出隊,示意圖如下:
到這裡,可能有的小夥伴會問,為什麼叫做,循環隊列?那現在我們試試看,我們讓元素f、g分別進行入隊操作,此時的示意圖如下:根據我們之前所說的,元素入隊:維護tail的位置,進行tail 操作,而此時我們的tail已經指向了索引為7的位置,如果我們此時對tail進行操作,顯然不可能(數組越界)
細心的小夥伴,會發現此時我們的隊列並沒有滿,還剩兩個位置(這是因為我們元素出隊後,當前的空間,沒有被後面的元素擠掉),大家可以把我們的陣列想像成一個環狀,那麼索引7之後的位置就是索引0
如何才能從索引7的位置計算到索引0的位置,之前我們一直說進行tail 操作,筆者也在開頭指出了,這是不嚴謹的,應該的是(tail 1) % capacity這樣就變成了(7 1) % 8等於0
所以此時如果讓元素h入隊,那麼我們的tail就指向了索引為0的位置,示意圖如下:
假設現在又有新的元素k入隊了,那麼tail的位置等於(tail 1) % capacity 也就是(0 1)% 8 等於1就指向了索引為1的位置
#那麼問題來了,我們的循環隊列還能不能在進行元素入隊呢?讓我們來分析一下,從圖中顯示,我們還有一個索引為0的空的空間位置,也就是此時tail指向的位置
依照先前的邏輯,假設現在能放入一個新元素,我們的tail進行(tail 1) % capacity計算結果為2(如果元素成功入隊,此時隊列已經滿了),此時我們會發現表示隊首的front也指向了索引為2的位置
如果新元素成功入隊的話,我們的tail也等於2,那麼此時就成了 tail == front ,一開始我們提到過,當隊列為空的tail == front,現在呢,如果隊列為滿時tail也等於front,那麼我們就無法區分,隊列為滿時和隊列為空時收的情況了
所以,在循環隊列中,我們總是浪費一個空間,來區分隊列為滿時和隊列為空時的情況,也就是當 ( tail 1 ) % capacity == front的時候,表示隊列已經滿了,當front == tail的時候,表示隊列為空。
了解了循環佇列的實作原理之後,下面我們用程式碼實作一下。
程式碼實作
介面定義 :Queue
public interface Queue<e> { /** * 入队 * * @param e */ void enqueue(E e); /** * 出队 * * @return */ E dequeue(); /** * 获取队首元素 * * @return */ E getFront(); /** * 获取队列中元素的个数 * * @return */ int getSize(); /** * 判断队列是否为空 * * @return */ boolean isEmpty(); }</e>
介面實作:LoopQueue
public class LoopQueue<e> implements Queue<e> { /** * 承载队列元素的数组 */ private E[] data; /** * 队首的位置 */ private int front; /** * 队尾的位置 */ private int tail; /** * 队列中元素的个数 */ private int size; /** * 指定容量,初始化队列大小 * (由于循环队列需要浪费一个空间,所以我们初始化队列的时候,要将用户传入的容量加1) * * @param capacity */ public LoopQueue(int capacity) { data = (E[]) new Object[capacity + 1]; } /** * 模式容量,初始化队列大小 */ public LoopQueue() { this(10); } @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("队列为空"); } // 出队元素 E element = data[front]; // 元素出队后,将空间置为null data[front] = null; // 维护front的索引位置(循环队列) front = (front + 1) % data.length; // 维护size大小 size--; // 元素出队后,可以指定条件,进行缩容 if (size == getCapacity() / 2 && getCapacity() / 2 != 0) { resize(getCapacity() / 2); } return element; } @Override public E getFront() { if (isEmpty()) { throw new IllegalArgumentException("队列为空"); } return data[front]; } @Override public int getSize() { return size; } @Override public boolean isEmpty() { return front == tail; } // 队列快满时,队列扩容;元素出队操作,指定条件可以进行缩容 private void resize(int newCapacity) { // 这里的加1还是因为循环队列我们在实际使用的过程中要浪费一个空间 E[] newData = (E[]) new Object[newCapacity + 1]; for (int i = 0; i <p>測試類別:LoopQueueTest</p> <pre class="brush:php;toolbar:false">public class LoopQueueTest { @Test public void testLoopQueue() { LoopQueue<integer> loopQueue = new LoopQueue(); for (int i = 0; i <h5>測試結果:</h5> <pre class="brush:php;toolbar:false">原始队列: LoopQueue{【队首】data=[0, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=0, tail=10, size=10, capacity=10} 元素0出队: LoopQueue{【队首】data=[null, 1, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=1, tail=10, size=9, capacity=10} 元素1出队: LoopQueue{【队首】data=[null, null, 2, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=2, tail=10, size=8, capacity=10} 元素2出队: LoopQueue{【队首】data=[null, null, null, 3, 4, 5, 6, 7, 8, 9, null]【队尾】, front=3, tail=10, size=7, capacity=10} 元素3出队: LoopQueue{【队首】data=[null, null, null, null, 4, 5, 6, 7, 8, 9, null]【队尾】, front=4, tail=10, size=6, capacity=10} 元素4出队,发生缩容: LoopQueue{【队首】data=[5, 6, 7, 8, 9, null]【队尾】, front=0, tail=5, size=5, capacity=5} 队首元素:5
完整版程式碼GitHub倉庫位址:Java版資料結構-佇列(循環佇列)
本篇文章到這裡就已經全部結束了,更多其他精彩內容可以關注PHP中文網的Java影片教學專欄!
以上是Java循環佇列的介紹(程式碼範例)的詳細內容。更多資訊請關注PHP中文網其他相關文章!