Java代碼手撕【數(shù)據(jù)結(jié)構(gòu)】| 隊列的實現(xiàn)與優(yōu)化指南

作者：Java小陳 2023-10-18 17:49:58

本文詳細介紹了隊列數(shù)據(jù)結(jié)構(gòu)的概念和應用，包括普通隊列和環(huán)形隊列的實現(xiàn)。隊列是一種有序的數(shù)據(jù)結(jié)構(gòu)，它在計算機科學中被廣泛應用，用于管理數(shù)據(jù)和任務的順序執(zhí)行。普通隊列使用數(shù)組實現(xiàn)，但存在內(nèi)存資源浪費的問題。

一、前言

隊列是一種重要的數(shù)據(jù)結(jié)構(gòu)，它按照“先入先出”（FIFO）的原則管理數(shù)據(jù)。本文將介紹隊列的概念、應用場景，以及如何使用數(shù)組實現(xiàn)普通隊列和環(huán)形隊列。

二、內(nèi)容

2.1 概述

2.1.1什么是隊列？

隊列（Queue）是一種常見的數(shù)據(jù)結(jié)構(gòu)，它是一個線性數(shù)據(jù)結(jié)構(gòu)，按照先入先出（FIFO，F(xiàn)irst-In-First-Out）的原則來管理數(shù)據(jù)。

注意，先入先出的原則就意味著最早進入隊列的元素將最先被取出，而最后進入隊列的元素將最后被取出，類似于排隊等候服務的行為。

隊列可以使用數(shù)組或鏈表來實現(xiàn)，具體實現(xiàn)方式因應用需求而異。

隊列支持兩種主要的操作，即入隊（Enqueue）和出隊（Dequeue）。

入隊：將元素添加到隊列的尾部。
出隊：從隊列的頭部取出元素并刪除它。

應用場景

隊列的應用場景有很多，比如：

任務調(diào)度：操作系統(tǒng)使用隊列來管理待執(zhí)行的任務或進程，確保按照進入隊列的順序分配處理時間。
數(shù)據(jù)緩沖：隊列用于數(shù)據(jù)傳輸和處理中，特別是在異步通信或生產(chǎn)者-消費者模式中，可以緩沖待處理的數(shù)據(jù)。
廣度優(yōu)先搜索：在圖論和搜索算法中，隊列用于實現(xiàn)廣度優(yōu)先搜索，以逐層遍歷圖結(jié)構(gòu)。
打印任務隊列：打印機隊列用于管理待打印的文檔，確保按照順序打印。
網(wǎng)頁請求隊列：Web服務器可以使用隊列來處理收到的請求，以便有序響應客戶端請求。
排隊系統(tǒng)：在銀行、餐館、醫(yī)院等場所，隊列被用來管理等待服務的客戶，確保服務按照先來先服務的原則。
......

隊列在計算機科學和實際應用中非常有用，因為它們提供了一種有效的方法來管理和調(diào)度數(shù)據(jù)或任務，以確保按照特定的順序進行處理。

2.2 數(shù)組模擬隊列

下面，我們用數(shù)組來模擬一個簡單的隊列數(shù)據(jù)結(jié)構(gòu)。

2.2.1 隊列類定義

首先給出類的定義：

class ArrayQueue {
    private int maxSize;
    private int front;
    private int rear;
    private int[] data;
    
    ArrayQueue(int queueMaxSize) {
        maxSize = queueMaxSize;    // 隊列的最大容量
        data = new int[maxSize];    // 存放隊列的數(shù)據(jù)
        front = -1;    // 指向隊列頭的前一個位置
        rear = -1;     // 直接指向隊列尾部
    }
	
    // ... 方法定義
}

在這里，ArrayQueue 是一個隊列類，使用數(shù)組作為內(nèi)部數(shù)據(jù)存儲。它包括最大容量（maxSize）、隊列頭（front）、隊列尾（rear）和一個整數(shù)數(shù)組（data）來存放隊列的數(shù)據(jù)。

構(gòu)造函數(shù) ArrayQueue 接受一個整數(shù)參數(shù) queueMaxSize，表示隊列的最大容量。初始化時，隊列的頭（front）和尾都（rear）被置為-1，表示隊列為空。

需要注意這里的定義，在這里，front 變量指的是指向隊列首元素的前一個位置，而 rear 變量則指向隊列的尾部元素，即最后一個元素。

因此，初始隊列的結(jié)構(gòu)圖如下：

2.2.2 isEmpty

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

2.2.3 isFull

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

2.2.4 enQueue

// 入隊操作，添加數(shù)據(jù)到隊尾
public void enQueue(int num) {
    if(isFull()) {
        System.out.println("隊列已滿，無法入隊");
        return;
    }
    rear++;
    data[rear] = num;
}

enQueue 方法用于將數(shù)據(jù)添加到隊列的尾部。首先，它會檢查隊列是否已滿，如果是，將輸出一條錯誤消息并不執(zhí)行入隊操作。如果隊列未滿，將 rear 后移，然后將數(shù)據(jù)存入隊列尾部。

再次強調(diào)一下，這里的 rear 變量用于指向隊列的最后一個數(shù)據(jù)，即隊列的尾部。

2.2.5 deQueue

// 出隊操作，取出隊頭數(shù)據(jù)
public int deQueue() {
    if(isEmpty()) {
        throw new RuntimeException("隊列為空，無法出隊"); 
    }
    front++;
    return data[front];
}

deQueue 方法用于取出隊列頭部的數(shù)據(jù)。首先，它會檢查隊列是否為空，如果是，將拋出一個運行時異常。如果隊列不為空，將 front 后移，然后返回隊頭的數(shù)據(jù)。

再次強調(diào)一下，這里的 front 變量指向的是隊列頭數(shù)據(jù)的前一個位置。

2.2.6 headQueue

// 查看隊頭數(shù)據(jù)（注意不是取出數(shù)據(jù)）
public int headQueue() {
    if(isEmpty()) {
        throw new RuntimeException("隊列為空，沒有數(shù)據(jù)");
    }
    return data[front+1];
}

headQueue 方法用于獲取隊列頭部的數(shù)據(jù)，但不會將其出隊。它會檢查隊列是否為空，如果是，將拋出一個運行時異常。如果隊列不為空，將返回隊頭的數(shù)據(jù)。

2.2.7 showQueue

// 打印隊列
public void showQueue() {
    if(isEmpty()) {
        System.out.println("隊列為空，沒有數(shù)據(jù)");
        return;
    }
    // 簡單的遍歷隊列
    for(int i = 0; i < data.length; i++) {
        System.out.printf("data[%d] = %d\n", i, data[i]);
    }
}

showQueue 方法用于簡單地打印隊列的所有元素。如果隊列為空，將輸出一條消息表示隊列為空。否則，它會簡單地遍歷隊列，打印每個數(shù)據(jù)元素的索引和值。

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

存在的問題

我們再來思考一個問題，雖然上述的隊列類實現(xiàn)了一個簡單的隊列數(shù)據(jù)結(jié)構(gòu)，但仍然存在弊端。那就是數(shù)組使用一次后不能復用。

什么意思？

具體的，我們可以發(fā)現(xiàn)，每當隊列入隊一個數(shù)據(jù)，rear 變量就會往后移一位。每當有元素出隊，front 變量也會往后移一位。但是！一旦 rear 變量到達隊列的尾部，如果隊列頭部仍有空余的空間，就像這樣：

那么此時根據(jù) isFull() 方法的判斷下，該隊列是滿的。因此無法再入隊。

因此我們說，對于之前的隊列簡單實現(xiàn)來說，一旦隊列中的數(shù)據(jù)元素被取出，對應的數(shù)組位置就不能再次使用。數(shù)據(jù)從頭部添加，從尾部取出。一旦數(shù)組被填滿，我們無法再添加新的數(shù)據(jù)，即使隊列的前面已經(jīng)有一些位置被釋放出來。這就會導致內(nèi)存資源浪費。

為了解決這個問題，我們考慮使用環(huán)形隊列來優(yōu)化。

那什么是環(huán)形隊列？

事實上，環(huán)形隊列是一種更高效的隊列實現(xiàn)方式，它允許隊列在達到最大容量后繼續(xù)添加元素，以覆蓋掉隊列頭部已經(jīng)被取出的數(shù)據(jù)，實現(xiàn)數(shù)據(jù)的循環(huán)復用。

我們通過取模運算 % 來實現(xiàn)環(huán)形隊列。

思路分析

當我們考慮了隊列內(nèi)部數(shù)據(jù)存儲資源的復用后，我們就需要對 front 和 rear 變量的含義進行一個的調(diào)整（當然不調(diào)整也行，看個人習慣）。

具體如下：

front 變量：表示指向隊列的第一個元素，即首元素。 data[front] 是隊列的第一個元素。 front的初始值為 0。
rear 變量：表示指向隊列最后一個元素的下一個位置。這是為了表示隊列中哪些位置是可用的，以便繼續(xù)添加新的元素。 rear 的初始值同樣為 0。

當我們這樣約定好了后，就可以開始著手編寫代碼，得到一個環(huán)形隊列。

此時判斷隊列已滿或空時，邏輯需要略微調(diào)整。

判斷環(huán)形隊列空時，條件為：(rear == front)。因為當 rear 指針等于 front 指針時，表示隊列沒有有效的元素，即隊列為空。

判斷環(huán)形隊列滿時，條件為：(rear + 1) % maxSize == front

這該怎么理解？

事實上，在含義調(diào)整后，環(huán)形隊列中的 rear 變量指向的位置實際上就是預留給下次入隊的數(shù)據(jù)存放的位置。

當有一個新的數(shù)據(jù)入隊時，rear 指向的位置就可以存儲本次入隊的數(shù)據(jù)的值，然后，rear 就會加一并取余 maxSize ，用于尋找下一個可以存儲入隊數(shù)據(jù)的位置。

因此，當(rear + 1) % maxSize 的值剛好等于 front，那么證明該環(huán)形隊列已經(jīng)滿了，沒有地方可以存儲下一次入隊的值。

舉一個例子，假設 maxSize 為 3，初始時 front 和 rear 都是0：

隊列為空：front = 0, rear = 0
插入一個元素：front = 0, rear = 1
插入第二個元素：front = 0, rear = 2
插入第三個元素：front = 0, rear = 0（此時隊列滿，因為 (rear + 1) % maxSize 等于 front）
取出第一個元素：front = 1, rear = 0（此時隊列有效元素個數(shù)為 2，因為 (0+3-1) % 3 == 2）

示意圖如下：

優(yōu)化后的隊列類

優(yōu)化后的代碼實現(xiàn)如下：

class CircleArrayQueue {
    private int maxSize;
    private int front;    // 初始值為 0，指向隊頭數(shù)據(jù)，即首元素
    private int rear;     // 初始值為 0，指向隊尾數(shù)據(jù)的下一個位置
    private int[] data;
	
    ArrayQueue(int queueMaxSize) {
        maxSize = queueMaxSize;	
        data = new int[maxSize];
    }
	
    // 判斷隊列是否為空
    public boolean isEmpty() {
        return rear == front;
    }
	
    // 判斷隊列是否滿
    public boolean isFull() {
        return (rear + 1) % maxSize == front;
    }
	
    // 入隊：添加數(shù)據(jù)到隊尾
    public void enQueue(int num) {
        if(isFull()) {
            System.out.println("隊列已滿，無法入隊");
            return;
        }
        data[rear] = num;
        rear = (rear + 1) % maxSize;
    }
	
    // 出隊，取出隊頭數(shù)據(jù)
    public int deQueue() {
        if(isEmpty()) {
            throw new RuntimeException("隊列為空，無法出隊"); 
        }
        int value = data[front];
        front = (front + 1) % maxSize;
        return value;
    }
	
    // 顯示隊列的頭數(shù)據(jù)（不是取出數(shù)據(jù)）
    public int headQueue() {
        if(isEmpty()) {
            throw new RuntimeException("隊列為空，沒有數(shù)據(jù)");
        }
        return data[front];
    }
	
    // 返回環(huán)形隊列當前的元素個數(shù)
    public int size() {
        return (rear + maxSize - front) % maxSize;
    }
	
    // 打印隊列
    public void showQueue() {
        if(isEmpty()) {
            System.out.println("隊列為空，沒有數(shù)據(jù)");
            return;
        }
        // 遍歷思路，從 data[front] 遍歷到 data[front + size]
        for(int i = front; i < front + size(); i++) {
            System.out.printf("data[%d] = %d\n", i%maxSize, data[i%maxSize]);
        }
    }
}

三、總結(jié)

責任編輯：武曉燕來源：今日頭條

數(shù)據(jù)結(jié)構(gòu)隊列結(jié)構(gòu)