Java 循環隊列原理與用法詳解

在正式進行循環隊列學習之前，我們先來看看在順序隊列中刪除隊首元素出現的問題：

（1）設一個容量為capacity=8，size=5(a,b,c,d,e)的數組，左側為隊首、右側為隊尾。

file

（2）出隊一個元素後，需整體往前移動一位

出隊：

file

整體前移一位：

file

關於該種操作方式我們很容易得出時間複雜度為O(n)。

這時我們就想可不可以在出隊元素後，整體元素不往前移，而是在數組中記下隊首front是誰，同時隊尾tail指向在下一次元素入隊時的位置，這樣當再有出隊時只需要維護一下front的指向即可，而不需移動元素。就這樣我們就有了循環隊列的情況。

file

1.循環隊列原理

(1)初始，數組整體為空時，隊首front、隊尾tail指向同一個位置（數組索引為0的地方）也即front==tail 時隊列為空

file

(2)當往數組中添加元素後

file

(3)出隊一個元素，front指向新的位置

file

(4)入隊元素，tail疊加

file

(5)當tail不能再增加時，數組前面還有空餘，此時循環隊列就該出場了。

file

此時數組應該變為這樣：

file

在往數組中添加一個元素：

file

這樣數組就已經滿了（tail+1==front 隊列滿），開始出發擴容操作。capacity中，浪費一個空間。

為了tail能返回到數組的前面位置，將隊列滿的表達式變為 （tail+1）%c==front這樣數組就可以循環移動了。

2.循環隊列代碼實現

新建一個類LoopQueue並實現接口Queue。

2.1、接口Queue代碼如下：

<code>package Queue;

public interface Queue {
    //獲取隊列中元素個數
    int getSize();

    //隊列中元素是否為空
    boolean isEmpty();

    //入隊列
    void enqueue(E e);

    //出隊列
    E dequeue();

    //獲取隊首元素
    E getFront();
}/<code>

<code>package Queue;

//循環隊列
public class LoopQueue implements Queue {
    private E[] data;
    private int front, tail;
    private int size;//隊列中元素個數

    //構造函數，傳入隊列的容量capacity構造函數
    public LoopQueue(int capacity) {
        data = (E[]) new Object[capacity + 1];//浪費與一個空間
        front = 0;
        tail = 0;
        size = 0;
    }

//無參構造函數，默認隊列的容量capacity=10
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("隊列為空");
    }

    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("隊列為空");
    }
    return data[front];
}

//改變容量
private void resize(int newCapacity) {
    E[] newData = (E[]) new Object[newCapacity + 1];
    for (int i = 0; i < size; i++) {
        newData[i] = data[(front + i) % 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[i]);
        if ((i + 1) % data.length != tail) {
        res.append(",");
        }
    }
    res.append("] tail");
    return res.toString();
    }

}/<code>

在關於LoopQueue類中需要注意的：

（1）第11行中的+1是capacity需要浪費一個空間，故在實例化是多加1

<code>data = (E[]) new Object[capacity + 1];//浪費與一個空間/<code>

（2）地24行真正的容量是data.length-1，這是由於有一個空間是浪費的。

<code>data.length - 1;/<code>

（3）關於入隊中第46行tail值的說明

為了保證入隊是循環操作，tail值的變化規律為

<code>tail = (tail + 1) % data.length;/<code>

（4）關於82行的數據遷移操作，取餘操作是為了防止循環數組時越界。

<code>newData[i] = data[(front + i) % data.length];//循環數組防止越界/<code>

2.3、直接在LoopQueue中添加一個main函數進行測試，相關代碼如下：

<code>//測試用例
public static void main(String[] args) {
    LoopQueue<integer> queue = new LoopQueue<integer>();
    for (int i = 0; i < 10; i++) {
        queue.enqueue(i);
        System.out.println(queue);

        if(i%3==2){//每添加3個元素出隊列一個
        queue.dequeue();
        System.out.println(queue);
    }

  }

}/<integer>/<integer>/<code>

結果為：

file

3.循環隊列時間複雜度

file

到此我們就實現了一個循環隊列操作，解決了在順序隊列中出隊時的時間複雜度為O(n)的情況，在循環隊列中出隊的時間複雜度為O(1)。

閱讀更多 JAVA互聯搬磚工人 的文章

關鍵字: 用法 詳解 隊列