一、隊列

1、基本介紹

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

2、示意圖

3、隊列的特點

先進先出：

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

二、數(shù)組模擬隊列

1、數(shù)組隊列初始化

根據(jù)圖示進行初始化：

class ArrayQueue{
    private int maxSize; //表示數(shù)組最大容量
    private int front; //隊列頭
    private int rear; //隊列尾
    private int[] arr; //該數(shù)組用于存放數(shù)據(jù)，模擬隊列
    //創(chuàng)建隊列構(gòu)造器，進行初始化
    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;
    }

判斷隊列是否滿

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

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

3、增刪改查的方法

向隊列中添加數(shù)據(jù)，入隊列

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

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

刪除隊列中數(shù)據(jù)，出隊列

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

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

顯示隊列中所有數(shù)據(jù)

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

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

4、注意

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

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

三、數(shù)組模擬環(huán)形隊列

1、初始化

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

class CircleTest{
    private int maxSize;//最大容量
    private int start;//表示隊列的頭
    private int end;//表示隊列的尾的下一個，要預(yù)留一個空位
    private int[] arr;//數(shù)組用來存放數(shù)據(jù)
    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;
    }

判斷隊列是否滿

因為此時的數(shù)組隊列可以循環(huán)，所以判斷是否滿的方法要用算法，讓隊列尾位置下標加一對總?cè)萘咳∮嗉纯?，然后判斷是否等于start，比如：end = 2 ，start = 3

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

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

計算數(shù)組中的有效數(shù)據(jù)

計算有效數(shù)據(jù)我們要用到一種取余的算法，算法式： (end + maxSize - start) % maxSize ，用隊列頭加上總?cè)萘繙p去隊列尾再對總?cè)萘咳∮?。比如：end = 0 ，start = 3

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

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

3、增刪改查的方法

向隊列中添加數(shù)據(jù)，入隊列

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

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

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

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

刪除隊列中數(shù)據(jù)，出隊列

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

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

顯示隊列中所有數(shù)據(jù)

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

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

注意：

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

到此這篇關(guān)于Java數(shù)組隊列及環(huán)形數(shù)組隊列超詳細講解的文章就介紹到這了,更多相關(guān)Java數(shù)組隊列內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評論