快捷導(dǎo)航

Java?循環(huán)隊列/環(huán)形隊列的實現(xiàn)流程

更新時間：2022年02月14日 15:12:59 作者：Word碼鴨

循環(huán)隊列又叫環(huán)形隊列，是一種特殊的隊列。循環(huán)隊列解決了隊列出隊時需要將所有數(shù)據(jù)前移一位的問題。本文將帶大家詳細(xì)了解循環(huán)隊列如何實現(xiàn)，需要的朋友可以參考一下

之前，我們使用鏈表實現(xiàn)了基礎(chǔ)隊列，鏈接放在這里可以去康康喲

Java棧和基礎(chǔ)隊列的實現(xiàn)詳解

之所以沒有選擇數(shù)組來實現(xiàn)，是因為每有一個元素出隊，數(shù)組中所有剩下的元素都需要向前移動一次，因此沒有鏈表高效。

此時，我們就引出了循環(huán)隊列的概念。

循環(huán)隊列，又稱環(huán)形隊列，邏輯上是一個環(huán)，物理上依然是線性表。

head-指向隊列的第一個元素

tail-指向隊列最后一個元素的下一個位置

當(dāng)tail走到數(shù)組末尾時，下一步再次返回數(shù)組頭部（從0開始）

出隊之后的元素就訪問不到了，此時邏輯上已經(jīng)將它刪除了，tail向后走到該位置時覆蓋它即可。此時就解決了數(shù)組隊列需要一直搬運元素的問題。

了解循環(huán)隊列的概念之后，我們就能明白它的幾個基礎(chǔ)知識:

當(dāng)head == tail 時，表示隊列為空

根據(jù)上面 head 和 tail 的定義，隊列已滿時，tail 指向最后一個元素的下一個位置，也就是head ，此時我們就無法區(qū)分環(huán)形隊列到底是已滿還是為空。所以我們在環(huán)形隊列的數(shù)組中浪費一個空間，在區(qū)分?jǐn)?shù)組是否已滿，如下圖，就是一個已滿的隊列

那么如何移動 tail 指針使他返回數(shù)組頭部呢？我們運用取模操作：

tail = ( tail + 1 ) % 數(shù)組.length;

根據(jù)上式我們就能判斷隊列是否已滿的方法：

( tail + 1 ) % 數(shù)組.length == head;

此時 head 和 tail 引用向后移動時，不能簡單的 +1，要 ++ 之后對數(shù)組長度取模，這樣就可以返回數(shù)組頭部繼續(xù)向后移動:

head = ( head +1 ) % 數(shù)組.length;

tail = ( tail +1 ) % 數(shù)組.length;

那么如何獲取當(dāng)前隊列最后一個元素的索引呢?

圖①中最后一個元素的索引就是 tail -1

圖②的tail恰好在數(shù)組第一個位置，這時最后一個元素下標(biāo)就是數(shù)組.length -1

綜上：數(shù)組最后一個元素的索引lastIndex

lastIndex = tail == 0 ? 數(shù)組.length -1 : tail -1;

代碼實現(xiàn)：

public interface Queue<E> {
    void offer(E val);//入隊
    E poll();//出隊，返回出隊的值
    E peek();//返回隊首元素
    boolean isEmpty();//判斷是否為空
}
 
 
import java.util.NoSuchElementException;
 
//基于整型的循環(huán)隊列
public class LoopQueue implements Queue<Integer>{
    private Integer[] data;
    private int head;//隊首元素
    private int tail;//隊尾元素的下一個位置
    private int size;//當(dāng)前元素個數(shù)
    public LoopQueue(int n){
        //n為希望保存的元素個數(shù)
        //在循環(huán)隊列中要浪費一個元素空間，來判斷是否已滿，所以 +1
        data = new Integer[n + 1];
        }
 
    @Override
    //添加元素
    public void offer(Integer val) {
        if(isFull()){
            throw new ArrayIndexOutOfBoundsException("queue is full, cannot offer new val");
        }
        data[tail] = val;
        //tail向后移
        tail = (tail + 1) % data.length;
        size++;
    }
 
    @Override
    //出隊
    public Integer poll() {
        if (isEmpty()){
            throw new NoSuchElementException("queues empty!cannot poll");
        }
        Integer val = data[head];
        //head向后移動
        head = (head + 1) % data.length;
        size--;
        return val;
    }
 
    @Override
    public Integer peek() {
        if (isEmpty()){
            throw new NoSuchElementException("queues empty!cannot poll");
        }
        return data[head];
    }
 
    @Override
    //判斷是否為空
    public boolean isEmpty() {
        return tail == head;
    }
    public String toString(){
        StringBuilder sb = new StringBuilder();
        sb.append("front[");
        //取得最后一個元素的下標(biāo)
        int lastIndex = tail == 0 ? data.length-1 : tail-1;
        for (int i = head; i != tail; ) {
            sb.append(data[i]);
            if (i != lastIndex){
                sb.append(",");
            }
            i = (i+1) % data.length;
 
        }
        sb.append("]tail");
        return sb.toString();
    }
    //判斷隊列是否已滿
    public boolean isFull(){
        return (tail + 1) % data.length == head;
    }
}

//代碼測試
public class LoopQueueTest {
    public static void main(String[] args) {
        Queue<Integer> loopQueue = new LoopQueue(5);
        for (int i = 0; i < 5; i++) {
            loopQueue.offer(i+1);
        }
        System.out.println(loopQueue);
//        loopQueue.offer(1);
        System.out.println(loopQueue.poll());
        System.out.println(loopQueue);
    }
}

運行結(jié)果：