當(dāng)前位置：首頁(yè) > 科技 > 軟件

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

來(lái)源：責(zé)編：時(shí)間：2023-10-18 17:58:16 287觀看

導(dǎo)讀一、前言隊(duì)列是一種重要的數(shù)據(jù)結(jié)構(gòu)，它按照“先入先出”（FIFO）的原則管理數(shù)據(jù)。本文將介紹隊(duì)列的概念、應(yīng)用場(chǎng)景，以及如何使用數(shù)組實(shí)現(xiàn)普通隊(duì)列和環(huán)形隊(duì)列。二、內(nèi)容2.1 概述2.1.1什么是隊(duì)列？隊(duì)列（Queue）是一種常見(jiàn)的數(shù)據(jù)結(jié)構(gòu)

一、前言

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

二、內(nèi)容

2.1 概述

2.1.1什么是隊(duì)列？

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

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

隊(duì)列可以使用數(shù)組或鏈表來(lái)實(shí)現(xiàn)，具體實(shí)現(xiàn)方式因應(yīng)用需求而異。

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

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

（2）應(yīng)用場(chǎng)景

隊(duì)列的應(yīng)用場(chǎng)景有很多，比如：

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

隊(duì)列在計(jì)算機(jī)科學(xué)和實(shí)際應(yīng)用中非常有用，因?yàn)樗鼈兲峁┝艘环N有效的方法來(lái)管理和調(diào)度數(shù)據(jù)或任務(wù)，以確保按照特定的順序進(jìn)行處理。

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

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

2.2.1 隊(duì)列類定義

首先給出類的定義：

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

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

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

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

因此，初始隊(duì)列的結(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

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

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

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

2.2.5 deQueue

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

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

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

2.2.6 headQueue

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

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

2.2.7 showQueue

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

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

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

（1）存在的問(wèn)題

我們?cè)賮?lái)思考一個(gè)問(wèn)題，雖然上述的隊(duì)列類實(shí)現(xiàn)了一個(gè)簡(jiǎn)單的隊(duì)列數(shù)據(jù)結(jié)構(gòu)，但仍然存在弊端。那就是數(shù)組使用一次后不能復(fù)用。

什么意思？

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

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

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

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

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

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

我們通過(guò)取模運(yùn)算 % 來(lái)實(shí)現(xiàn)環(huán)形隊(duì)列。

（2）思路分析

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

具體如下：

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

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

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

判斷環(huán)形隊(duì)列空時(shí)，條件為：(rear == front)。因?yàn)楫?dāng) rear 指針等于 front 指針時(shí)，表示隊(duì)列沒(méi)有有效的元素，即隊(duì)列為空。

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

這該怎么理解？

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

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

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

舉一個(gè)例子，假設(shè) maxSize 為 3，初始時(shí) front 和 rear 都是0：

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

示意圖如下：

3）優(yōu)化后的隊(duì)列類

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

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

本文詳細(xì)介紹了隊(duì)列數(shù)據(jù)結(jié)構(gòu)的概念和應(yīng)用，包括普通隊(duì)列和環(huán)形隊(duì)列的實(shí)現(xiàn)。隊(duì)列是一種有序的數(shù)據(jù)結(jié)構(gòu)，它在計(jì)算機(jī)科學(xué)中被廣泛應(yīng)用，用于管理數(shù)據(jù)和任務(wù)的順序執(zhí)行。普通隊(duì)列使用數(shù)組實(shí)現(xiàn)，但存在內(nèi)存資源浪費(fèi)的問(wèn)題。為了解決這個(gè)問(wèn)題，我們引入了環(huán)形隊(duì)列的概念，它允許隊(duì)列數(shù)據(jù)的循環(huán)復(fù)用，更加高效地利用內(nèi)存。

本文鏈接：http://www.www897cc.com/showinfo-26-13986-0.htmlJava代碼手撕【數(shù)據(jù)結(jié)構(gòu)】| 隊(duì)列的實(shí)現(xiàn)與優(yōu)化指南

聲明：本網(wǎng)頁(yè)內(nèi)容旨在傳播知識(shí)，若有侵權(quán)等問(wèn)題請(qǐng)及時(shí)與本網(wǎng)聯(lián)系，我們將在第一時(shí)間刪除處理。郵件：2376512515@qq.com

上一篇：十個(gè)2023年最流行的數(shù)據(jù)科學(xué)開(kāi)源工具

下一篇： Dig 簡(jiǎn)明教程，你看明白了嗎?

標(biāo)簽：

熱門焦點(diǎn)

鴻蒙OS 4.0公測(cè)機(jī)型公布：甚至連nova6都支持

華為全新的HarmonyOS 4.0操作系統(tǒng)將于今天下午正式登場(chǎng)，官方在發(fā)布會(huì)之前也已經(jīng)正式給出了可升級(jí)的機(jī)型產(chǎn)品，這意味著這些機(jī)型會(huì)率先支持升級(jí)享用。這次的HarmonyOS 4.0支持
6月iOS設(shè)備性能榜：M2穩(wěn)居榜首 A系列只能等一手3nm來(lái)救

沒(méi)有新品發(fā)布，自然iOS設(shè)備性能榜的上榜設(shè)備就沒(méi)有什么更替，僅僅只有跑分變化而產(chǎn)生的排名變動(dòng)，畢竟蘋果新品的發(fā)布節(jié)奏就是這樣的，一年下來(lái)也就幾個(gè)移動(dòng)端新品，不會(huì)像安卓廠商，一
把LangChain跑起來(lái)的三個(gè)方法

使用LangChain開(kāi)發(fā)LLM應(yīng)用時(shí)，需要機(jī)器進(jìn)行GLM部署，好多同學(xué)第一步就被勸退了，那么如何繞過(guò)這個(gè)步驟先學(xué)習(xí)LLM模型的應(yīng)用，對(duì)Langchain進(jìn)行快速上手？本片講解3個(gè)把LangChain跑起來(lái)
谷歌KDD'23工作：如何提升推薦系統(tǒng)Ranking模型訓(xùn)練穩(wěn)定性

谷歌在KDD 2023發(fā)表了一篇工作，探索了推薦系統(tǒng)ranking模型的訓(xùn)練穩(wěn)定性問(wèn)題，分析了造成訓(xùn)練穩(wěn)定性存在問(wèn)題的潛在原因，以及現(xiàn)有的一些提升模型穩(wěn)定性方法的不足，并提出了一種新
小米公益基金會(huì)捐贈(zèng)2500萬(wàn)元馳援北京、河北暴雨救災(zāi)

8月2日消息，今日小米科技創(chuàng)始人雷軍在其微博上發(fā)布消息稱，小米公益基金會(huì)宣布捐贈(zèng)2500萬(wàn)元馳援北京、河北暴雨救災(zāi)。攜手抗災(zāi)，京冀安康！以下為公告原文
四年持續(xù)更迭堅(jiān)持探索行業(yè)無(wú)人之境，HarmonyOS 4帶來(lái)五大升級(jí)多項(xiàng)創(chuàng)新

除了華為每年新發(fā)布的旗艦手機(jī)系列，上億花粉更加期待鴻蒙系統(tǒng)每次的跨版本大更新。8月4日，HarmonyOS 4于HDC 2023正式發(fā)布，這也是該系統(tǒng)歷經(jīng)四年的再
華為Mate 60保護(hù)殼曝光：碩大后置相機(jī)模組凸起程度有驚喜

這段時(shí)間以來(lái)，關(guān)于華為新旗艦的爆料日漸密集。據(jù)此前多方爆料，今年華為將開(kāi)始恢復(fù)一年雙旗艦戰(zhàn)略，除上半年推出的P60系列外，往年下半年的Mate系列也將
3699元！iQOO Neo8 Pro頂配版今日首銷：1TB UFS 4.0同價(jià)位唯一

5月23日，iQOO推出了全新的iQOO Neo8系列，包含iQOO Neo8和iQOO Neo8 Pro兩個(gè)版本，其中標(biāo)準(zhǔn)版搭載高通驍龍8+，而Pro版更是首發(fā)搭載了聯(lián)發(fā)科天璣9200+旗艦
iQOO Neo8 Pro真機(jī)諜照曝光：天璣9200+和V1+旗艦雙芯加持

去年10月，iQOO推出了iQOO Neo7系列機(jī)型，不僅搭載了天璣9000+，而且是同價(jià)位唯一一款天璣9000+直屏旗艦，一經(jīng)上市便受到了用戶的廣泛關(guān)注。在時(shí)隔半年后，

日韩成人免费在线_国产成人一二_精品国产免费人成电影在线观..._日本一区二区三区久久久久久久久不

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

一、前言

二、內(nèi)容

2.1 概述

2.1.1什么是隊(duì)列？

（2）應(yīng)用場(chǎng)景

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

2.2.1 隊(duì)列類定義

2.2.2 isEmpty

2.2.3 isFull

2.2.4 enQueue

2.2.5 deQueue

2.2.6 headQueue

2.2.7 showQueue

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

（1）存在的問(wèn)題

（2）思路分析

3）優(yōu)化后的隊(duì)列類

三、總結(jié)

鴻蒙OS 4.0公測(cè)機(jī)型公布：甚至連nova6都支持

6月iOS設(shè)備性能榜：M2穩(wěn)居榜首 A系列只能等一手3nm來(lái)救

把LangChain跑起來(lái)的三個(gè)方法

谷歌KDD'23工作：如何提升推薦系統(tǒng)Ranking模型訓(xùn)練穩(wěn)定性

小米公益基金會(huì)捐贈(zèng)2500萬(wàn)元馳援北京、河北暴雨救災(zāi)

四年持續(xù)更迭堅(jiān)持探索行業(yè)無(wú)人之境，HarmonyOS 4帶來(lái)五大升級(jí)多項(xiàng)創(chuàng)新

華為Mate 60保護(hù)殼曝光：碩大后置相機(jī)模組凸起程度有驚喜

3699元！iQOO Neo8 Pro頂配版今日首銷：1TB UFS 4.0同價(jià)位唯一

iQOO Neo8 Pro真機(jī)諜照曝光：天璣9200+和V1+旗艦雙芯加持

最新推薦

猜你喜歡

熱門推薦

相關(guān)資訊

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

一、前言

二、內(nèi)容

2.1 概述

2.1.1什么是隊(duì)列？

（2）應(yīng)用場(chǎng)景

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

2.2.1 隊(duì)列類定義

2.2.2 isEmpty

2.2.3 isFull

2.2.4 enQueue

2.2.5 deQueue

2.2.6 headQueue

2.2.7 showQueue

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

（1）存在的問(wèn)題

（2）思路分析

3）優(yōu)化后的隊(duì)列類

三、總結(jié)

最新推薦

猜你喜歡

熱門推薦

相關(guān)資訊

二、內(nèi)容

2.1.1什么是隊(duì)列？