Java數組隊列及環形數組隊列怎么實現

這篇文章主要介紹了Java數組隊列及環形數組隊列怎么實現的相關知識，內容詳細易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇Java數組隊列及環形數組隊列怎么實現文章都會有所收獲，下面我們一起來看看吧。

一、隊列

1、基本介紹

隊列是一種特殊的線性表，特殊之處在于它只允許在表的前端（front）進行刪除操作，而在表的后端（rear）進行插入操作，和棧一樣，隊列是一種操作受限制的線性表。進行插入操作的端稱為隊尾，進行刪除操作的端稱為隊頭。

2、示意圖

3、隊列的特點

先進先出：

在隊列中插入一個隊列元素稱為入隊，從隊列中刪除一個隊列元素稱為出隊。因為隊列只允許在一端插入，在另一端刪除，所以只有最早進入隊列的元素才能最先從隊列中刪除，故隊列又被稱為先進先出。

二、數組模擬隊列

1、數組隊列初始化

根據圖示進行初始化：

class ArrayQueue{
    private int maxSize; //表示數組最大容量
    private int front; //隊列頭
    private int rear; //隊列尾
    private int[] arr; //該數組用于存放數據，模擬隊列
    //創建隊列構造器，進行初始化
    public ArrayQueue(int arrMaxSize){
        maxSize = arrMaxSize;
        arr = new int[maxSize];
        front = -1; //front指向隊列頭的前一個位置
        rear = -1; //指向隊列尾
    }
}

2、判斷方法

判斷隊列是否為空

front 是指向隊列的頭的前一個位置，rear是指向隊列的尾，當front和rear重合時，隊列為空。

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

判斷隊列是否滿

因為數組有最大容量，所以直接判斷rear（隊列尾）是否在數組的最后位置。數組的下標從零開始。

public boolean isFull(){
        return rear == maxSize - 1;
    }

3、增刪改查的方法

向隊列中添加數據，入隊列

? 添加數據首先判斷數組是否滿，如果滿，則無法添加數據，數組未滿則只需要動 rear（進行尾部移動），rear先加一，然后在數組中存放數據。

    //添加數據到隊列
    public void addQueue(int n){
        //判斷隊列是否滿
        if(isFull()){
            System.out.println("隊列滿，不能再添加");
            return;
        }
        rear++; //讓rear后移
        arr[rear] = n;
    }

刪除隊列中數據，出隊列

? 因為隊列的特點先進先出，所以我們需要動隊列的頭，當然首先應該判斷隊列是否為空，為空則不能出隊列；然后（front是指向隊列頭的前一個位置）先將front 加一到達隊列的頭的位置，再把這個值返回即可。有人可能會問隊列的頭呢？當front == -1時，數組下標為0 的數據為頭，一旦front進行加一后，數組下標為1的數據就為頭了，也就是當front進行變化后隊列的頭就變了。

    //獲取隊列數據，出隊列
    public int getQueue(){
        //判斷隊列是否為空
        if(isEmpty()){
            //通過拋出異常
            throw new RuntimeException("隊列為空，不能獲取數據");
        }
        front++; //front后移
        return arr[front];
    }

顯示隊列中所有數據

? 因為是數組模擬的隊列，將數組進行遍歷輸出即可。

    //顯示隊列的所有數據
    public void showQueue(){
        //判斷是否為空
        if(isEmpty()){
            System.out.println("隊列為空，沒有數據");
            return;
        }
        //遍歷
        for(int i = 0; i < arr.length ; i++){
            System.out.printf("arr[%d] = %d\n", i , arr[i] );
        }
    }

4、注意

這樣的數組隊列是不可逆的，當front在數組的末尾時，這個數組隊列就不可用了，因為front 和 rear 不能循環到數組的前面去，所以這樣的數組隊列是非常局限的。而鏈表隊列，就是隊列是由單鏈表形成的，就沒有數組大小的限制，可以無限的入隊列和出隊列，單鏈表的操作非常的簡單，后續的文章會介紹。那么數組隊列是否也可以無限入隊列和出隊列呢？當然可以，那么怎么可以實現呢？數組隊列的局限在哪里？不就是front 和 rear 的指向不能回過頭來指向數組的空位置。

只要解決了front 和 rear 能夠返回到數組的空位置，是不是就能解決這個局限性的問題呢，因為出隊列和入隊列都是通過 front 和 rear 操作的。

三、數組模擬環形隊列

1、初始化

數組的最大容量實際要少一個，因為我們要預留一個空位置，也就是任何時候數組要多一個空位置，便于我們循環。

class CircleTest{
    private int maxSize;//最大容量
    private int start;//表示隊列的頭
    private int end;//表示隊列的尾的下一個，要預留一個空位
    private int[] arr;//數組用來存放數據
    public CircleTest(int maxSize){
        this.maxSize = maxSize;
        arr = new int[maxSize];
        //start和end默認初始化為0，所以不需要寫
    }
}

2、判斷方法

判斷隊列是否為空

start是指向隊列的頭，end是指向隊列的尾的下一個，當start和end重合時，隊列為空。

public boolean isEmpty(){
        return start == end;
    }

判斷隊列是否滿

因為此時的數組隊列可以循環，所以判斷是否滿的方法要用算法，讓隊列尾位置下標加一對總容量取余即可，然后判斷是否等于start，比如：end = 2 ，start = 3

計算 （end + 1）% maxSize = （2 + 1）% 4 = 3 ，計算結果等于start ，所以是滿狀態，因為前面說了要預留一個位置，所以容量為4，實際存放數據為3個。

public boolean isFull(){
        return (end + 1) % maxSize == start;;
    }

計算數組中的有效數據

計算有效數據我們要用到一種取余的算法，算法式： (end + maxSize - start) % maxSize ，用隊列頭加上總容量減去隊列尾再對總容量取余。比如：end = 0 ，start = 3

時，有效數據為 （1 + 4 - 3）% 4 = 2，所以有效數據為2個。

public int size(){
        return (end + maxSize - start) % maxSize;
    }

3、增刪改查的方法

向隊列中添加數據，入隊列

首先判斷隊列是否滿，然后因為我們早已預留了一個位置（end指向的位置是空的），所以加入的數據位置可以直接加入到隊列（arr[end] = n）；環形隊列是要無限循環下去的，所以在加入數據后，end 的指向不能直接加一，而要用算法計算end的下一個位置，此算法為：(end + 1) % maxSize

比如：start = 2，end = 3 ，此時添加一個數據 end 的位置移動到在哪里？

根據算法(end + 1) % maxSize = （3 + 1) % 4 = 0 ,所以 end 指向數組下標為0 的位置。如此，就形成了循環。

    public void addData(int n){
        //先判斷是否滿
        if (isFull()){
            System.out.println("數據已滿，無法添加");
            return;
        }
        //當前end的位置，加入元素
        arr[end] = n;
        //end指向下一個位置為(end + 1) % maxSize
        end = (end + 1) % maxSize;
    }

刪除隊列中數據，出隊列

首先判斷是否為空，然后將要出隊列的數據用一個中間變量暫存起來，然后將start 移動，移動到的位置和上面end 的移動方式相同，也是用取余算法：(start + 1) % maxSize 即可。

    public int removeData(){
        //判斷是否為空
        if(isEmpty()){
            throw new RuntimeException("數據為空，不能移除");
        }
        //先將數據暫存
        int temp = arr[start];
        //然后將start往后移到(start + 1) % maxSize的位置
        start = (start + 1) % maxSize;
        return temp;
    }

顯示隊列中所有數據

因為是循環隊列，所以位置是無限變化的，所以每次for循環的開始位置為start 所在的位置，要循環的次數取決于數組中的有效數據的個數，及前面我們寫的有效個數的算法拿來直接用（ start + size() ），取余的方式 ：i % maxSize ，可以時時確定數組數據的下標。

    public void showData(){
        //判斷是否為空
        if(isEmpty()){
            System.out.println("數據為空，不能顯示");
            return;
        }
        for (int i = start; i < start + size() ; i++) {
            System.out.printf("arr[%d] = %d\n", i % maxSize,arr[i % maxSize]);
        }
    }

注意：

循環的關鍵點在于 start 和 end 指向的下一個位置的確定，隊列頭和尾的位置可以回過頭來，那么就能實現循環，而位置的確定，需要用到取余這個算法，前面的列子可以看出，指向發生變化時都是用的取余算法來確定位置，這個是數組中常見的一種算法，可以記住。

關于“Java數組隊列及環形數組隊列怎么實現”這篇文章的內容就介紹到這里，感謝各位的閱讀！相信大家對“Java數組隊列及環形數組隊列怎么實現”知識都有一定的了解，大家如果還想學習更多知識，歡迎關注億速云行業資訊頻道。