Java實作數組模拟（環形）隊列

了解隊列

通俗的說，隊列就跟你在超市排隊結賬一樣。結賬的人排了一隊，那先來的人在隊首，會先結賬，後來的人隻能從隊伍後面排隊，不能插隊，後結賬。結賬隻能從第一個人開始結賬，收銀員不可能放着第一個人不管，先去給後面的人結賬，第一個人結賬完，就走了，後面的人依次向前。還有一點是隊伍中每個人都是在挨着的，是以隊列有記憶體中的存儲是連續的。

用百度百科的話講：隊列是一種特殊的線性表，特殊之處在于它隻允許在表的前端（front）進行删除操作，而在表的後端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。

用數組實作隊列

1. 建立隊列

經過思考，隊列應該有隊首、隊尾、隊列長度、數組這幾部分組成，應該有添加資料、取出資料、周遊隊列的功能。我們先把隊列的架構搭好，稍後分析每一塊應該怎麼寫。

package chengquan.dataStru;
/*
chengquan 20200925 用數組實作隊列
*/
public class MyQueue {
    private int front;  // 隊首
    private int rear;   // 隊尾
    private int queueSize; // 隊列長度
    private int[] array; // 隊列資料存儲到數組裡

    public MyQueue(int queueSize){
        // 剛執行個體化一個隊列的時候，隊裡沒有元素，
        this.front = -1;
        this.rear = -1;
        this.queueSize = queueSize;
        this.array = new int[queueSize+1];
    }
    /*
    判斷隊列是否為空
    */
	public Boolean isEmpty(){
	}
    /*
   判斷隊列是滿了
    */
    public Boolean isFull(){
    }
    /*
    實作功能：向隊列中添加一個元素
     */
    public void addData(int data){
    }

    /*
    實作功能：從隊列中取出一個元素
     */
    public void getData(){
    }

    /*
    周遊
     */
    public void list(){
    }
}

2. 判斷隊列是否滿了

當隊列資料存滿的時候，rear 應該指向數組的最後一個元素，最後一個元素的下标是 size -1。

public Boolean isFull(){
	return rear == queueSize - 1;
}

3. 判斷隊列是否為空

隊列為空的時候就是隊列頭等于隊列尾的下标

public Boolean isEmpty(){
	return front == rear;
}

4. 實作隊列的添加資料到末尾

每添加一個資料，rear就要往後移一位，将資料放到rear裡。

public void addData(int data){
    if(!isFull()){
        rear = rear + 1;
        array[rear] =data;
    }else {
        System.out.println("隊列已經爆滿了！！");
    }
}

5. 實作隊列的取出資料

public void getData(){
    if(!isEmpty()){
        front = front + 1;
        System.out.println("取出的資料為：" +  array[front]);
        array[front] = 0;
    }else {
        System.out.println("隊列為空");
    }
}

6. 周遊數列

public void list(){
    if (isEmpty()){
        System.out.println("隊列是空的");
    }
    for (int i = front + 1; i <= rear; i++) {
        System.out.print(array[i] + " ");
    }
    System.out.println();
}

7. 整合

package chengquan.dataStru;

public class MyQueue {
    private int front;  // 隊首
    private int rear;   // 隊尾
    private int queueSize; // 隊列長度
    private int[] array;
    public MyQueue(){

    }

    public MyQueue(int queueSize){
        // 剛執行個體化一個隊列的時候，隊裡沒有元素，
        this.front = -1;
        this.rear = -1;
        this.queueSize = queueSize;
        this.array = new int[queueSize+1];
    }
    /*
    判斷隊列是否為空
     */
    public Boolean isEmpty(){
        return front == rear;
    }

    /*
   判斷隊列是滿了
    */
    public Boolean isFull(){
        return rear == queueSize -1;
    }
    /*
    實作功能：向隊列中添加一個元素
     */
    public void addData(int data){
        if(!isFull()){
            rear = rear + 1;
            array[rear] =data;
        }else {
            System.out.println("隊列已經爆滿了！！");
        }
    }

    /*
    實作功能：從隊列中取出一個元素
     */
    public void getData(){
        if(!isEmpty()){
            front = front + 1;
            System.out.println("取出的資料為：" +  array[front]);
            array[front] = 0;
        }else {
            System.out.println("隊列為空");
        }
    }

    /*
    周遊
     */
    public void list(){
        if (isEmpty()){
            System.out.println("隊列是空的");
        }
        for (int i = front + 1; i <= rear; i++) {
            System.out.print(array[i] + " ");
        }
        System.out.println();
    }
}

8. 測試

MyQueue myQueue = new MyQueue(5);

myQueue.list();

myQueue.addData(666);
myQueue.addData(999);

myQueue.list();

myQueue.getData();

myQueue.list();
/*
輸出結果為：

隊列是空的

666 999 
取出的資料為：666
999 
*/

9.發現問題

當進行多次資料插入取出之後，我發現了一個問題：建立了一個長度為5的隊列，往隊列裡插入了1、2、3、4、5五個資料，接着又取出了隊列的第一個資料1，隊列裡還剩下資料2、3、4、5，到這裡為止都還是正常的。接下來又往隊列裡再添加資料的時候卻提示隊列已經滿了。

經過研究發現是了原因：取出元素的時候，隊首往後移動一位，

– 插入圖檔

這個時候，我們要考慮實作一個循環隊列，将數組首尾相接，類似于左輪槍一樣，實作空間的再次利用。

MyQueue myQueue = new MyQueue(5);

myQueue.list();

myQueue.addData(1);
myQueue.addData(2);
myQueue.addData(3);
myQueue.addData(4);
myQueue.addData(5);

myQueue.list();

myQueue.getData();

myQueue.list();

myQueue.addData(6);
/* 輸出結果為：
隊列是空的

1 2 3 4 5 
取出的資料為：1
2 3 4 5 
隊列已經爆滿了！！
*/

用數組實作環形隊列

既然是環形隊列，我們需要對是否空，是否滿，添加、取出資料進行從新整理

1. 判斷隊列是否滿了

當隊列資料存滿的時候，front與rear的正序查距離應該是queueSize - 1；此處不了解% queueSize，可以用筆将數組頭尾相連畫出來，用幾個數試試就知道了。

public Boolean isFull(){
	return front == (rear + 1) % queueSize;
}