java----循環隊列

文章目錄

• 一、什麼是循環隊列
• 二、循環隊列的簡單實作
• • 1、簡單圖示
  • 2.數組下标循環的小技巧：
• 總結

一、什麼是循環隊列

循環隊列（Circular Queue） 是把順序隊列首尾相連，把存儲隊列元素的表從邏輯上看成一個環，成為循環隊列。循環隊列可以更簡單防止僞溢出的發生，但隊列大小是固定的。

二、循環隊列的簡單實作

環形隊列通常使用數組實作

1、簡單圖示

2.數組下标循環的小技巧：

1. 隊尾元素的下标rear的移動： rear = ( rear + 1) % elem.length;

   頭元素的下标：front = (front + 1) % elem.length

2. 如何區分空與滿

   a、判空：front=rear

   b、判滿：front=（rear+1)%MaxSize（MaxSize 代表數組的長度）

   

   3.代碼實作

要求：
*    設計你的循環隊列實作。 循環隊列是一種線性資料結構，其操作表現基于 FIFO（先進先出）
*    原則并且隊尾被連接配接在隊首之後以形成一個循環。它也被稱為“環形緩沖器”。
*
*    循環隊列的一個好處是我們可以利用這個隊列之前用過的空間。在一個普通隊列裡，一旦一個
*    隊列滿了，我們就不能插入下一個元素，即使在隊列前面仍有空間。但是使用循環隊列，我們能
*    使用這些空間去存儲新的值。
*
*    你的實作應該支援如下操作：
*    MyCircularQueue(k): 構造器，設定隊列長度為 k 。
*    Front: 從隊首擷取元素。如果隊列為空，傳回 -1 。
*    Rear: 擷取隊尾元素。如果隊列為空，傳回 -1 。
*    enQueue(value): 向循環隊列插入一個元素。如果成功插入則傳回真。
*    deQueue(): 從循環隊列中删除一個元素。如果成功删除則傳回真。
*    isEmpty(): 檢查循環隊列是否為空。
*    isFull(): 檢查循環隊列是否已滿。
*/
class CircularQueue {
    private int[] elem;//數組
    private int front;//頭元素的下标
    private int rear;//尾元素的下标

    public CircularQueue(int k) {
        //這裡為什麼是k+1，題目要求是放k個元素
        this.elem = new int[k + 1];
        this.front = 0;
        this.rear = 0;
    }

    //檢查循環隊列是否已滿
    public boolean isFull() {
        if((this.rear + 1) % this.elem.length == this.front){
            return true;
        }
        return false;
    }

    //向循環隊列插入一個元素。如果成功插入則傳回真。
    public boolean enQueue(int value) {
        if(isFull()) return false;
        this.elem [this.rear] = value;
        this.rear = ( this.rear + 1) % this.elem.length;
        return true;
    }

    // 從循環隊列中删除一個元素。如果成功删除則傳回真。
    public boolean deQueue() {
        if(isEmpty()){
            return false;
        }
        this.front = (this.front + 1) % this.elem.length;
        return true;
    }

    public int Front() {
        if(isEmpty()){
            return -1;
        }
        return this.elem[this.front];

    }

    public int Rear() {
        if(isEmpty()){
            return -1;
        }
        //當rear == 0時，下标是this.elem.length-1
        //當rear != 0時, 下标是this.rear-1
        int index = (this.rear == 0)? this.elem.length-1:this.rear -1;
        return this.elem[index];
    }

    public boolean isEmpty() {
        //當front和rear相遇時，就是空的隊列
        if(this.front == this.rear){
            return true;
        }
        return false;
    }
}
public class CircularQueueTest {
    public static void main(String[] args) {
        CircularQueue  queue = new CircularQueue(3);
        System.out.println(queue.enQueue(1));//true
        System.out.println(queue.enQueue(2));//true
        System.out.println(queue.Rear());//2
        System.out.println(queue.isEmpty());//false
        System.out.println(queue.isFull());//false
        System.out.println(queue.Front());//1
        System.out.println(queue.deQueue());//true
        System.out.println(queue.Rear());//2
    }
}
           

總結

以上内容就是個人對循環隊列的學習和簡單實作，後續有深刻的學習之後會繼續改進。