數(shù)據(jù)結(jié)構(gòu)與算法學(xué)習(xí)2---隊(duì)列

不詩(shī)意的女程序猿不是好廚師~
【轉(zhuǎn)載請(qǐng)注明出處，F(xiàn)rom李詩(shī)雨---https://blog.csdn.net/cjm2484836553/article/details/93889029】

源碼地址見(jiàn)github：https://github.com/junmei520/DataStructureStudy/tree/master/src/datastructure/queue

文章看似很長(zhǎng)，其實(shí)非常容易理解。

1.隊(duì)列介紹

隊(duì)列是一個(gè)有序列表，可以用數(shù)組或鏈表來(lái)實(shí)現(xiàn)。
隊(duì)列遵循先入先出原則。先存入隊(duì)列的數(shù)據(jù)先取出，后存入隊(duì)列的數(shù)據(jù)后取出。
如圖，可以把它理解為一個(gè)單向通道：


在這里插入圖片描述

2.用數(shù)組模擬隊(duì)列

2.1思路分析

數(shù)組模擬隊(duì)列示意圖

首先我們需要一個(gè)數(shù)組arr[]來(lái)存儲(chǔ)隊(duì)列中的數(shù)據(jù)，用maxSize來(lái)代表隊(duì)列的最大容量。為了體現(xiàn)先入先出的原則，我們規(guī)定只能在數(shù)組的尾部（rear）添加數(shù)據(jù)，只能在數(shù)組的頭部(front)取出數(shù)據(jù)，所以我們還需要定義兩個(gè)變量front, rear分別來(lái)記錄隊(duì)列前后端的下標(biāo)。

2.2 擼代碼進(jìn)行實(shí)踐

①定義相關(guān)變量和構(gòu)造函數(shù)。

首先我們定義一個(gè)ArrayQueue類，聲明一些變量，以及一個(gè)有參構(gòu)造器：

public class ArrayQueue {
    private int maxSize;//表示數(shù)組的最大容量
    private int front;//隊(duì)列頭
    private int rear;//隊(duì)列尾
    private int[] arr;//用于存放隊(duì)列數(shù)據(jù)的數(shù)組

    public ArrayQueue(int arrMaxSise){
        maxSize=arrMaxSise;
        arr=new int[maxSize];
        front=-1;// 指向隊(duì)列頭部，注意front是指向隊(duì)列頭的前一個(gè)位置.
        rear=-1;// 指向隊(duì)列尾，指向隊(duì)列尾的數(shù)據(jù)(即就是隊(duì)列最后一個(gè)數(shù)據(jù))
    }

}

②添加數(shù)據(jù)到隊(duì)列中。

需要注意的是，在數(shù)據(jù)添加之前需要先進(jìn)行判斷，如果隊(duì)列沒(méi)有滿，那rear就后移并賦相應(yīng)的值；如果隊(duì)列已滿，則數(shù)據(jù)是加入失敗的。

 /**
     * 添加數(shù)據(jù)到隊(duì)列中
     */
    public void addQueue(int data) {
        //先判斷隊(duì)列是否滿
        if (isFull()) {
            System.out.println("隊(duì)列已滿，無(wú)法添加數(shù)據(jù)");
            return;
        }
        rear++;//讓rear后移
        arr[rear] = data;
    }

    /**
     * 判斷隊(duì)列是否滿
     */
    private boolean isFull() {
        return rear == maxSize - 1;
    }

③從隊(duì)列中取數(shù)據(jù)。

需要注意的是，在從隊(duì)列中取數(shù)據(jù)之前，需要先判斷隊(duì)列是否為空，如果隊(duì)列不為空，front后移取出對(duì)應(yīng)數(shù)據(jù)；如果隊(duì)列為空，則無(wú)法取出數(shù)據(jù)。

 /**
     * 從隊(duì)列中取數(shù)據(jù)
     * @return 返回取出的數(shù)據(jù)
     */
    public int getQueue() {
        //先判斷隊(duì)列是否為空
        if (isEmpty()) {
            //拋個(gè)異常
            throw new RuntimeException("隊(duì)列為空，無(wú)法取出數(shù)據(jù)");
        }
        front++;//front后移
        return arr[front];
    }

    /**
     * 判斷隊(duì)列是否為空
     */
    private boolean isEmpty() {
        return front == rear;
    }

④顯示隊(duì)列的現(xiàn)有數(shù)據(jù)。

注意：是從現(xiàn)有的頭數(shù)據(jù)開(kāi)始顯示，即從【front+1】開(kāi)始顯示，而非【0】開(kāi)始。

/**
     * 顯示現(xiàn)有隊(duì)列的所有數(shù)據(jù)
     */
    public void showQueue() {
        //先判空
        if (isEmpty()) {
            System.out.println("隊(duì)列為空，沒(méi)有數(shù)據(jù)可以顯示");
            return;
        }

        //遍歷數(shù)組，依次打印數(shù)據(jù)。注意是從現(xiàn)有的頭數(shù)據(jù)開(kāi)始顯示，即從【front+1】開(kāi)始顯示。
        for (int i = front + 1; i < arr.length; i++) {
            System.out.printf("arr[%d]=%d\n", i, arr[i]);
        }
    }

⑤顯示隊(duì)列的頭數(shù)據(jù)。

注意：
此處只是顯示，并沒(méi)有將數(shù)據(jù)取出。所以front的指向并沒(méi)有進(jìn)行移動(dòng)。
由于front是指向隊(duì)列頭的前一個(gè)位置，所以【front+1】的位置才是隊(duì)列的頭。

     /**
     * 顯示隊(duì)列的頭數(shù)據(jù)。
     * 注意:只顯示并沒(méi)有取出數(shù)據(jù)，所以front的指向位置并沒(méi)有變。
     */
    public int showHeadData() {
        if (isEmpty()) {
            throw new RuntimeException("隊(duì)列為空，沒(méi)有數(shù)據(jù)可以顯示");
        }
        //由于front是指向隊(duì)列頭的前一個(gè)位置，所以【front+1】的位置才是隊(duì)列的頭
        return arr[front + 1];
    }

⑥進(jìn)行驗(yàn)證

下面我們新建一個(gè)ArrayQueueTest類，進(jìn)行驗(yàn)證我們用數(shù)組模擬的隊(duì)列是否正確。
思路：
我們創(chuàng)建一個(gè)規(guī)定容量的隊(duì)列，然后通過(guò)鍵盤的輸入，進(jìn)行隊(duì)列的添加，顯示等操作。
具體代碼如下：

/**
 * @author shiyu
 * @create 2019-06-27 16:16
 */
public class ArrayQueueTest {
    public static void main(String[] args) {
        //先創(chuàng)建一個(gè)最大容量為3的隊(duì)列
        ArrayQueue queue = new ArrayQueue(3);
        //用于接收用戶鍵盤輸入的指令
        char order = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //相關(guān)指令提示信息
        System.out.println("s(show): 顯示隊(duì)列");
        System.out.println("e(exit): 退出程序");
        System.out.println("a(add): 添加數(shù)據(jù)到隊(duì)列");
        System.out.println("g(get): 從隊(duì)列取出數(shù)據(jù)");
        System.out.println("h(head): 查看隊(duì)列頭的數(shù)據(jù)");
        while (loop) {
            order = scanner.next().charAt(0);//每次只接收一個(gè)字符
            switch (order) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("請(qǐng)輸入你要加入隊(duì)列的數(shù)據(jù)");
                    int data = scanner.nextInt();
                    queue.addQueue(data);
                    break;
                case 'g':
                    int queueData = queue.getQueue();
                    System.out.println("取出的隊(duì)列數(shù)據(jù)是：" + queueData);
                    break;
                case 'h':
                    int headData = queue.showHeadData();
                    System.out.println("隊(duì)列的頭數(shù)據(jù)為：" + headData);
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
            }
        }
    }
}

我的鍵盤輸入的截圖：


在這里插入圖片描述

在這里插入圖片描述

3.數(shù)組模擬隊(duì)列存在的問(wèn)題

好，到這里，我們已經(jīng)使用數(shù)組實(shí)現(xiàn)了隊(duì)列的功能。

但是還存在一些問(wèn)題：

我們?cè)賮?lái)做一個(gè)測(cè)試，運(yùn)行上面的代碼。我們先添加三個(gè)數(shù)據(jù)進(jìn)“隊(duì)列”，然后全部取出，這個(gè)時(shí)候“隊(duì)列”已經(jīng)為空，此時(shí)再添加新數(shù)據(jù)到“空隊(duì)列”中，是添加不成功的，會(huì)報(bào)“隊(duì)列已滿，無(wú)法添加數(shù)據(jù)”。


在這里插入圖片描述

明明是“空隊(duì)列”了，卻不能再次添加數(shù)據(jù)進(jìn)去，這是怎么回事呢？

這就要再次看看下面這張圖了：


在這里插入圖片描述

由于我們<向隊(duì)列中添加數(shù)據(jù)>和<從隊(duì)列中取數(shù)據(jù)>都是通過(guò)移動(dòng)<rear>和<front>這兩個(gè)標(biāo)記。那當(dāng)我們?nèi)?shù)據(jù)時(shí)，只是將front不斷地上移，移動(dòng)過(guò)的藍(lán)色區(qū)就被空了出來(lái)，但是卻不能被再次使用了。

所以問(wèn)題就出現(xiàn)了：
使用數(shù)組模擬隊(duì)列，數(shù)組只能被使用一次，不能復(fù)用。

4.使用環(huán)形數(shù)組來(lái)解決問(wèn)題

現(xiàn)在我們要解決，數(shù)組只能被使用一次，不能復(fù)用的問(wèn)題，那我們的思路肯定時(shí)想讓數(shù)組可以被復(fù)用。

其實(shí)解決這個(gè)問(wèn)題，我們的核心是使用 %(取摸)，也就是，我們把數(shù)組想像成是一個(gè)環(huán)形的，只要有新的空間出來(lái)，就可以繼續(xù)放數(shù)據(jù)進(jìn)去。

當(dāng)然對(duì)這個(gè)問(wèn)題的理解，我也是花費(fèi)了很多工夫和心思的，也經(jīng)過(guò)了一些試錯(cuò)后，才比較正切的理解這種做法的正確性和簡(jiǎn)潔性。

4.1擼代碼來(lái)實(shí)現(xiàn) 環(huán)形數(shù)組模擬隊(duì)列

好，現(xiàn)在我們就先一邊擼代碼一邊來(lái)理解吧。如果一遍下來(lái)還是模糊，那不妨你自己再試一遍，這樣慢慢的就可以理解了。

嗯，為了可以更深刻的理解，我自己親自動(dòng)手模擬了一下，請(qǐng)忽略它的丑，以下所有圖請(qǐng)忽略它們的外在~~~

基本思路是這樣的：


在這里插入圖片描述

基本原理是：

  • 用一個(gè)數(shù)組來(lái)盛裝數(shù)據(jù)，但是這個(gè)數(shù)組，有一個(gè)空間是用來(lái)做約定用的，不能裝數(shù)據(jù)，并且它是可以動(dòng)態(tài)變化的，如圖中的陰影部分。（這個(gè)如果你不太理解沒(méi)關(guān)系，繼續(xù)往下看，當(dāng)你把代碼整個(gè)看完，這一點(diǎn)就豁然開(kāi)朗了）
  • 仍需要兩個(gè)指針，但是含義有所變化，front指向隊(duì)列的頭，rear指向隊(duì)列尾的后一個(gè)位置。他們的初始值都是0。

好，上面我們只是說(shuō)了個(gè)大概，現(xiàn)在我們用一個(gè)大小為4的具體數(shù)組為例，來(lái)做詳細(xì)的演示：


在這里插入圖片描述

【笑哭】上圖是我的筆記，請(qǐng)忽略美觀性，畢竟它真的幫助了我的理解?，F(xiàn)在我們看了上圖，基本已經(jīng)知道了 往隊(duì)列中添加數(shù)據(jù)的操作，下面就讓我們用代碼來(lái)實(shí)現(xiàn)吧！

①定義相關(guān)變量和構(gòu)造函數(shù)。

public class CircleArrayQueue {
    private int maxSize;//表示數(shù)組的最大容量
    private int front;//front指向隊(duì)列的頭
    private int rear;//注意：rear是指向隊(duì)列的尾的下一個(gè)位置
    private int[] arr;//用于存放隊(duì)列數(shù)據(jù)的數(shù)組

    public CircleArrayQueue(int arrMaxSise) {
        maxSize = arrMaxSise;
        arr = new int[maxSize];
        //front,rear不用賦值，默認(rèn)值都是0
    }
}

②隊(duì)列空和隊(duì)列滿的判斷

    /**
     * 判斷隊(duì)列是否為空
     */
    private boolean isEmpty() {
        return front==rear;
    }

    /**
     * 判斷隊(duì)列是否滿
     * 當(dāng)  (rear+1)%maxSize==front 時(shí) ，隊(duì)列滿
     */
    private boolean isFull() {
        return (rear+1)%maxSize==front;
    }

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

    /**
     * 添加數(shù)據(jù)到隊(duì)列中
     */
    public void addQueue(int data) {
        //先判斷隊(duì)列是否滿
        if (isFull()) {
            System.out.println("隊(duì)列已滿，無(wú)法添加數(shù)據(jù)");
            return;
        }
        arr[rear] = data;
        //rear需要向后移動(dòng)，為了發(fā)揮它的復(fù)用性并防止它越界，我們這里要取模
        rear=(rear+1)%maxSize;
    }

④從隊(duì)列中取出數(shù)據(jù)

這個(gè)其實(shí)比較簡(jiǎn)單，思路是這樣的：
(1). 首先我們要判斷隊(duì)列是否為空；
(2). 不空的情況下，可以取，由于front指向的就是隊(duì)列的頭，所以拿一個(gè)變量來(lái)接受arr[front]就是取出的數(shù)據(jù)；
(3). 緊接著front要后移，指向新的頭，同樣這里要取模，所以front=（front+1）%maxSize.
我們來(lái)看下代碼實(shí)現(xiàn)：

    /**
     * 從隊(duì)列中取數(shù)據(jù)
     *
     * @return 返回取出的數(shù)據(jù)
     */
    public int getQueue() {
        //先判斷隊(duì)列是否為空
        if (isEmpty()) {
            //拋個(gè)異常
            throw new RuntimeException("隊(duì)列為空，無(wú)法取出數(shù)據(jù)");
        }
        int value=arr[front]; //需要臨時(shí)變量來(lái)接收一下
        front=(front+1)%maxSize;//front需要后移，此處同樣需要取模
        return value;
    }

顯示隊(duì)列的頭數(shù)據(jù)就更簡(jiǎn)單了，此處一并給出代碼：

 /**
     * 顯示隊(duì)列的頭數(shù)據(jù)。
     * 注意:只顯示并沒(méi)有取出數(shù)據(jù)，所以front的指向位置并沒(méi)有變。
     */
    public int showHeadData() {
        if (isEmpty()) {
            throw new RuntimeException("隊(duì)列為空，沒(méi)有數(shù)據(jù)可以顯示");
        }
        //front---就是隊(duì)列頭對(duì)應(yīng)的下標(biāo)
        return arr[front];
    }

⑤ 遍歷顯示隊(duì)列的所有數(shù)據(jù)

還有比較關(guān)鍵的一步等著我來(lái)完成了，那就是遍歷顯示隊(duì)列的所有數(shù)據(jù)。
這里我們必須要知道隊(duì)列中的實(shí)際數(shù)據(jù)的個(gè)數(shù)，前面的小結(jié)論中我們提到過(guò)，隊(duì)列中的有效元素個(gè)數(shù)=（rear+maxSize-front）% maxSize.

對(duì)于這個(gè)公式的理解，我又要上圖了：


在這里插入圖片描述

所以遍歷顯示隊(duì)列的代碼我們現(xiàn)在就比較好理解了：

    /**
     * 隊(duì)列中 裝的 實(shí)際數(shù)據(jù)的個(gè)數(shù)
     */
    private int realSize(){
        return (rear+maxSize-front)%maxSize;
    }

    /**
     * 顯示隊(duì)列現(xiàn)有的所有數(shù)據(jù)，注意是從頭數(shù)據(jù)開(kāi)始顯示
     */
    public void showQueue() {
        //先判空
        if (isEmpty()) {
            System.out.println("隊(duì)列為空，沒(méi)有數(shù)據(jù)可以顯示");
            return;
        }

        //遍歷數(shù)組，依次打印數(shù)據(jù)。注意是從現(xiàn)有的頭數(shù)據(jù)開(kāi)始顯示
        for (int i = front; i < front+realSize(); i++) {
            System.out.printf("arr[%d]=%d\n", i%maxSize, arr[i%maxSize]);
        }
    }

⑥進(jìn)行驗(yàn)證

我們?nèi)允褂弥暗腁rrayQueueTest類，進(jìn)行驗(yàn)證我們用數(shù)組模擬的隊(duì)列是否正確。

public class ArrayQueueTest {
    public static void main(String[] args) {
        //測(cè)試數(shù)組模擬隊(duì)列
        //先創(chuàng)建一個(gè)最大容量為3的隊(duì)列
        //ArrayQueue queue = new ArrayQueue(3);

        //測(cè)試環(huán)形數(shù)組來(lái)模擬隊(duì)列
        //創(chuàng)建一個(gè)容量為4的數(shù)組，
        // 但是它實(shí)際最多只能裝3個(gè)數(shù)據(jù)，因?yàn)橛幸粋€(gè)空間需要用來(lái)做約定。
        CircleArrayQueue queue =new CircleArrayQueue(4);

        //用于接收用戶鍵盤輸入的指令
        char order = ' ';
        Scanner scanner = new Scanner(System.in);
        boolean loop = true;
        //相關(guān)指令提示信息
        System.out.println("s(show): 顯示隊(duì)列");
        System.out.println("e(exit): 退出程序");
        System.out.println("a(add): 添加數(shù)據(jù)到隊(duì)列");
        System.out.println("g(get): 從隊(duì)列取出數(shù)據(jù)");
        System.out.println("h(head): 查看隊(duì)列頭的數(shù)據(jù)");
        while (loop) {
            order = scanner.next().charAt(0);//每次只接收一個(gè)字符
            switch (order) {
                case 's':
                    queue.showQueue();
                    break;
                case 'a':
                    System.out.println("請(qǐng)輸入你要加入隊(duì)列的數(shù)據(jù)");
                    int data = scanner.nextInt();
                    queue.addQueue(data);
                    break;
                case 'g':
                    int queueData = queue.getQueue();
                    System.out.println("取出的隊(duì)列數(shù)據(jù)是：" + queueData);
                    break;
                case 'h':
                    int headData = queue.showHeadData();
                    System.out.println("隊(duì)列的頭數(shù)據(jù)為：" + headData);
                    break;
                case 'e':
                    scanner.close();
                    loop = false;
                    break;
            }
        }
    }
}

運(yùn)行結(jié)果截圖：
添加數(shù)據(jù)，只能添加3個(gè)數(shù)據(jù)，加到第四個(gè)時(shí)，提示已滿：


在這里插入圖片描述

顯示添加的數(shù)據(jù)：


在這里插入圖片描述

好，說(shuō)明添加沒(méi)有問(wèn)題。

下面我們來(lái)驗(yàn)證它的復(fù)用性，先取出一個(gè)數(shù)據(jù)，再添加，看是否可以添加成功：


在這里插入圖片描述

取出了一個(gè)數(shù)據(jù)10，又成功加入了一個(gè)數(shù)據(jù)50，通過(guò)顯示確實(shí)可以復(fù)用了。

再次梳理環(huán)形數(shù)組模擬隊(duì)列的思路和要點(diǎn)

不要先我啰嗦，讓我再把前面的東西都串起來(lái)再理理思路：

  • ①我們需要一個(gè)數(shù)組來(lái)盛裝數(shù)據(jù)，但是這個(gè)數(shù)組，有一個(gè)空間是用來(lái)做約定用的，不能裝數(shù)據(jù)，并且它是可以動(dòng)態(tài)變化的，如之前圖中的陰影部分。
  • ②我需要兩個(gè)指針，front和rear。front指向隊(duì)列的頭，rear指向隊(duì)列尾的后一個(gè)位置。他們的初始值都是0。
  • ③我們需要知道一些小結(jié)論：
    隊(duì)列的最大容積=maxSize-1（因?yàn)橛幸粋€(gè)空間不能裝數(shù)據(jù)）；
    隊(duì)列為空時(shí)：front==rear;
    隊(duì)列滿時(shí)： (rear+1)%maxSize ==front;
    隊(duì)列的有效個(gè)數(shù)為：(rear+maxSize-front)%maxSize;
  • ④向隊(duì)列中加數(shù)據(jù)，頭不動(dòng)，rear需要“后移”一位，這里需要注意，由于現(xiàn)在時(shí)環(huán)形可復(fù)用的隊(duì)列，所以不是簡(jiǎn)單的rear++，而是要使用取模的方式 rear=(rear+1)%maxSize;
  • ⑤從隊(duì)列中取出數(shù)據(jù)時(shí)，front需要后移一位，同樣需要注意
    front=(front+1)%maxSize;
  • ⑥遍歷隊(duì)列時(shí)，應(yīng)該從front開(kāi)始，以（front+realSize）結(jié)束，對(duì)應(yīng)的數(shù)組下標(biāo)時(shí) i%maxSize，注意要取模。

好，到這里，我已經(jīng)對(duì)用數(shù)組模擬隊(duì)列，和用環(huán)形數(shù)組模擬隊(duì)列，都掌握了。不知道你理解了沒(méi)有【笑哭】。

這次的感悟就是，動(dòng)手亂畫是個(gè)理解知識(shí)的好方法~

源碼地址見(jiàn)github：https://github.com/junmei520/DataStructureStudy/tree/master/src/datastructure/queue

積累點(diǎn)滴，做好自己~

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容