一、隊(duì)列

1、基本介紹

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

2、示意圖

3、隊(duì)列的特點(diǎn)

先進(jìn)先出：

在隊(duì)列中插入一個(gè)隊(duì)列元素稱(chēng)為入隊(duì)，從隊(duì)列中刪除一個(gè)隊(duì)列元素稱(chēng)為出隊(duì)。因?yàn)殛?duì)列只允許在一端插入，在另一端刪除，所以只有最早進(jìn)入隊(duì)列的元素才能最先從隊(duì)列中刪除，故隊(duì)列又被稱(chēng)為先進(jìn)先出。

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

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

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

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

2、判斷方法

判斷隊(duì)列是否為空

front 是指向隊(duì)列的頭的前一個(gè)位置，rear是指向隊(duì)列的尾，當(dāng)front和rear重合時(shí)，隊(duì)列為空。

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

判斷隊(duì)列是否滿(mǎn)

因?yàn)閿?shù)組有最大容量，所以直接判斷rear（隊(duì)列尾）是否在數(shù)組的最后位置。數(shù)組的下標(biāo)從零開(kāi)始。

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

3、增刪改查的方法

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

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

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

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

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

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

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

? 因?yàn)槭菙?shù)組模擬的隊(duì)列，將數(shù)組進(jìn)行遍歷輸出即可。

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

4、注意

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

只要解決了front 和 rear 能夠返回到數(shù)組的空位置，是不是就能解決這個(gè)局限性的問(wèn)題呢，因?yàn)槌鲫?duì)列和入隊(duì)列都是通過(guò) front 和 rear 操作的。

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

1、初始化

數(shù)組的最大容量實(shí)際要少一個(gè)，因?yàn)槲覀円A(yù)留一個(gè)空位置，也就是任何時(shí)候數(shù)組要多一個(gè)空位置，便于我們循環(huán)。

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

2、判斷方法

判斷隊(duì)列是否為空

start是指向隊(duì)列的頭，end是指向隊(duì)列的尾的下一個(gè)，當(dāng)start和end重合時(shí)，隊(duì)列為空。

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

判斷隊(duì)列是否滿(mǎn)

因?yàn)榇藭r(shí)的數(shù)組隊(duì)列可以循環(huán)，所以判斷是否滿(mǎn)的方法要用算法，讓隊(duì)列尾位置下標(biāo)加一對(duì)總?cè)萘咳∮嗉纯桑缓笈袛嗍欠竦扔趕tart，比如：end = 2 ，start = 3

計(jì)算 （end + 1）% maxSize = （2 + 1）% 4 = 3 ，計(jì)算結(jié)果等于start ，所以是滿(mǎn)狀態(tài)，因?yàn)榍懊嬲f(shuō)了要預(yù)留一個(gè)位置，所以容量為4，實(shí)際存放數(shù)據(jù)為3個(gè)。

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

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

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

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

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

3、增刪改查的方法

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

首先判斷隊(duì)列是否滿(mǎn)，然后因?yàn)槲覀冊(cè)缫杨A(yù)留了一個(gè)位置（end指向的位置是空的），所以加入的數(shù)據(jù)位置可以直接加入到隊(duì)列（arr[end] = n）；環(huán)形隊(duì)列是要無(wú)限循環(huán)下去的，所以在加入數(shù)據(jù)后，end 的指向不能直接加一，而要用算法計(jì)算end的下一個(gè)位置，此算法為：(end + 1) % maxSize

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

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

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

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

首先判斷是否為空，然后將要出隊(duì)列的數(shù)據(jù)用一個(gè)中間變量暫存起來(lái)，然后將start 移動(dòng)，移動(dòng)到的位置和上面end 的移動(dòng)方式相同，也是用取余算法：(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;
    }

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

因?yàn)槭茄h(huán)隊(duì)列，所以位置是無(wú)限變化的，所以每次for循環(huán)的開(kāi)始位置為start 所在的位置，要循環(huán)的次數(shù)取決于數(shù)組中的有效數(shù)據(jù)的個(gè)數(shù)，及前面我們寫(xiě)的有效個(gè)數(shù)的算法拿來(lái)直接用（ start + size() ），取余的方式 ：i % maxSize ，可以時(shí)時(shí)確定數(shù)組數(shù)據(jù)的下標(biāo)。

    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)鍵點(diǎn)在于 start 和 end 指向的下一個(gè)位置的確定，隊(duì)列頭和尾的位置可以回過(guò)頭來(lái)，那么就能實(shí)現(xiàn)循環(huán)，而位置的確定，需要用到取余這個(gè)算法，前面的列子可以看出，指向發(fā)生變化時(shí)都是用的取余算法來(lái)確定位置，這個(gè)是數(shù)組中常見(jiàn)的一種算法，可以記住。

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

最新評(píng)論