一. 隊(duì)列的概念

隊(duì)列是一種特殊的線(xiàn)性表，用于存儲(chǔ)元素，并且按照先進(jìn)先出(First In First Out)的順序進(jìn)行管理，這意味著最先加入隊(duì)列的元素將會(huì)是最先從隊(duì)列中被移除的元素

隊(duì)列的原型：只允許在一端進(jìn)行插入數(shù)據(jù)的操作，在另一端進(jìn)行刪除數(shù)據(jù)的操作

隊(duì)列的原則：隊(duì)列中的元素遵循先進(jìn)先出的原則?

隊(duì)列的兩個(gè)經(jīng)典操作：

入隊(duì)列：隊(duì)列的插入操作叫做入隊(duì)列，進(jìn)行操作的一端稱(chēng)為隊(duì)尾

出隊(duì)列：隊(duì)列的刪除操作叫做出隊(duì)列，進(jìn)行操作的一端稱(chēng)為隊(duì)頭

二. 隊(duì)列的結(jié)構(gòu)

現(xiàn)實(shí)中的隊(duì)列

?當(dāng)我們?nèi)ャy行取款機(jī)排隊(duì)取錢(qián)的過(guò)程就是隊(duì)列，我們從隊(duì)尾進(jìn)入，依次取錢(qián)，取完錢(qián)之后從隊(duì)頭離開(kāi)

三. 隊(duì)列的實(shí)現(xiàn)

隊(duì)列的實(shí)現(xiàn)有兩種方式

一. 用數(shù)組實(shí)現(xiàn)

優(yōu)點(diǎn)

• 快速訪(fǎng)問(wèn)：數(shù)組允許隨機(jī)訪(fǎng)問(wèn)，可以快速訪(fǎng)問(wèn)任何一個(gè)元素，特別是在入隊(duì)和出隊(duì)操作時(shí)，可以直接通過(guò)索引來(lái)訪(fǎng)問(wèn)隊(duì)頭和隊(duì)尾。
• 內(nèi)存連續(xù)：數(shù)組是連續(xù)內(nèi)存的數(shù)據(jù)結(jié)構(gòu)，這可能有助于提高緩存效率，因?yàn)檫B續(xù)的內(nèi)存塊更有可能一起被加載到CPU緩存中。

缺點(diǎn)

• 固定大小：數(shù)組的大小在初始化時(shí)固定，這意味著隊(duì)列的容量有一個(gè)上限。如果隊(duì)列滿(mǎn)了，就需要執(zhí)行昂貴的數(shù)組擴(kuò)展操作，通常涉及分配一個(gè)更大的數(shù)組并復(fù)制現(xiàn)有元素。
• 空間浪費(fèi)：在使用數(shù)組實(shí)現(xiàn)循環(huán)隊(duì)列時(shí)，即使數(shù)組中還有空間，隊(duì)列也可能報(bào)告已滿(mǎn)，這是因?yàn)檠h(huán)使用的邏輯問(wèn)題導(dǎo)致的空間利用不充分。

二. 用鏈表實(shí)現(xiàn)

優(yōu)點(diǎn)

1. 動(dòng)態(tài)大小：鏈表提供了動(dòng)態(tài)大小的能力，隊(duì)列可以根據(jù)需要增長(zhǎng)和縮小，不存在固定的容量限制。
2. 內(nèi)存利用率高：鏈表只在需要時(shí)分配內(nèi)存，且只為實(shí)際存儲(chǔ)的元素分配，這減少了內(nèi)存浪費(fèi)。

缺點(diǎn)

1. 內(nèi)存分配開(kāi)銷(xiāo)：鏈表的每個(gè)新元素都可能需要內(nèi)存分配（除非使用內(nèi)存池技術(shù)），這可能比連續(xù)的內(nèi)存分配（如數(shù)組）更昂貴。
2. 訪(fǎng)問(wèn)速度慢：鏈表不支持隨機(jī)訪(fǎng)問(wèn)，訪(fǎng)問(wèn)任何位置的元素都需要從頭開(kāi)始遍歷，這使得某些操作比數(shù)組慢。
3. 額外內(nèi)存需求：每個(gè)鏈表節(jié)點(diǎn)需要額外的內(nèi)存空間來(lái)存儲(chǔ)指向下一個(gè)節(jié)點(diǎn)的指針，這增加了每個(gè)元素的內(nèi)存開(kāi)銷(xiāo)。

總結(jié)：不過(guò)整體上使用鏈表的結(jié)構(gòu)實(shí)現(xiàn)更優(yōu)一些，因?yàn)槿绻褂脭?shù)組的結(jié)構(gòu)，出隊(duì)列在數(shù)組頭上出數(shù)據(jù)，效率會(huì)比較低。下面我將用鏈表的結(jié)構(gòu)來(lái)實(shí)現(xiàn)隊(duì)列

1. 初始化隊(duì)列

1.1 鏈?zhǔn)浇Y(jié)構(gòu)表示隊(duì)列

在使用鏈表實(shí)現(xiàn)隊(duì)列的時(shí)候，定義一個(gè)節(jié)點(diǎn)結(jié)構(gòu)QNode，為隊(duì)列中的每個(gè)元素提供一個(gè)容器，使得元素能連接起來(lái)

typedef int QDataType;

typedef struct QListNode  //定義一個(gè)節(jié)點(diǎn)
{
	struct QListNode* pNext; //指針域
	QDataType data; //數(shù)據(jù)域
}QNode;

1.2 隊(duì)列的結(jié)構(gòu)

普通鏈表通常只需要一個(gè)頭指針來(lái)訪(fǎng)問(wèn)鏈表的起始位置，而隊(duì)列為了支持高效的入隊(duì)和出隊(duì)操作，需要同時(shí)維護(hù)隊(duì)頭和隊(duì)尾兩個(gè)指針，我們通常會(huì)定義一個(gè)額外的結(jié)構(gòu)體，這個(gè)結(jié)構(gòu)體包括了指向隊(duì)頭的指針和指向隊(duì)尾的指針。

typedef struct Queue
{
    QNode* front; // 隊(duì)頭指針
    QNode* rear;  // 隊(duì)尾指針
} Queue;         // 隊(duì)列結(jié)構(gòu)體別名

1.3 隊(duì)列的初始化?

接下來(lái)就是創(chuàng)建一個(gè)初始化函數(shù)，對(duì)隊(duì)列里的元素進(jìn)行初始化

void QueueInit(Queue* q)
{
    assert(q);  // 斷言隊(duì)列指針q不為NULL，確保不對(duì)NULL指針進(jìn)行操作，提高程序的安全性。

    q->front = NULL; // 將隊(duì)列的前端指針設(shè)置為NULL，表示隊(duì)列為空，即隊(duì)列中沒(méi)有元素。
    q->rear = NULL;  // 將隊(duì)列的后端指針也設(shè)置為NULL，與隊(duì)列為空的狀態(tài)一致，因?yàn)闆](méi)有元素可以指向。
}

2. 銷(xiāo)毀隊(duì)列

從對(duì)頭開(kāi)始，進(jìn)行釋放空間，最后讓隊(duì)頭隊(duì)尾指針置為NULL

void QueueDestory(Queue* q)
{
    assert(q);            // 斷言隊(duì)列指針不為空

    QNode* cur = q->front;  // 創(chuàng)建一個(gè)變量，從隊(duì)頭開(kāi)始銷(xiāo)毀隊(duì)列節(jié)點(diǎn)
    while (cur)
    {
        QNode* next = cur->next;  // 保存當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
        free(cur);                 // 釋放當(dāng)前節(jié)點(diǎn)的內(nèi)存
        cur = next;                // 移動(dòng)到下一個(gè)節(jié)點(diǎn)
    }

    q->front = NULL;  // 將隊(duì)列的頭指針置為空，表示隊(duì)列已被銷(xiāo)毀
    q->rear = NULL;   // 將隊(duì)列的尾指針置為空，表示隊(duì)列已被銷(xiāo)毀
}

3. 入隊(duì)列

申請(qǐng)一個(gè)新的節(jié)點(diǎn)鏈接到尾部，然后讓尾指針，指向新節(jié)點(diǎn)? 需要注意的是：若隊(duì)列中無(wú)數(shù)據(jù)，我們需要讓隊(duì)頭和隊(duì)尾都指向這個(gè)新的節(jié)點(diǎn)

void QueuePush(Queue* q, QDataType x)
{
    assert(q);  // 斷言隊(duì)列指針不為空

    QNode* newnode = (QNode*)malloc(sizeof(QNode));  // 分配新節(jié)點(diǎn)的內(nèi)存空間
    if (newnode == NULL)
    {
        printf("malloc fail\n");  // 如果內(nèi)存分配失敗，打印錯(cuò)誤信息
        exit(-1);                  // 退出程序
    }

    newnode->data = x;   // 將數(shù)據(jù)存儲(chǔ)到新節(jié)點(diǎn)中
    newnode->next = NULL;  // 新節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)指針為空

    if (q->front == NULL)  // 如果隊(duì)列為空
    {
        q->front = newnode;  // 將新節(jié)點(diǎn)設(shè)置為隊(duì)列的頭節(jié)點(diǎn)
        q->rear = newnode;   // 將新節(jié)點(diǎn)設(shè)置為隊(duì)列的尾節(jié)點(diǎn)
    }
    else
    {
        q->rear->next = newnode;  // 將新節(jié)點(diǎn)鏈接到隊(duì)列尾部
        q->rear = newnode;        // 更新隊(duì)列的尾節(jié)點(diǎn)為新節(jié)點(diǎn)
    }
}

4. 出隊(duì)列

釋放隊(duì)頭的節(jié)點(diǎn)，并將隊(duì)頭更新到下一個(gè)元素。需要注意的是，如果隊(duì)列中只有一個(gè)數(shù)據(jù)，在釋放了隊(duì)頭的節(jié)點(diǎn)之后，要讓隊(duì)尾和隊(duì)頭的指針置空

void QueuePop(Queue* q)
{
    assert(q);  // 斷言以確保隊(duì)列指針 'q' 不是 NULL，保證這是一個(gè)有效的指針。
    assert(!QueueEmpty(q));  // 斷言以確保隊(duì)列不為空，僅當(dāng)隊(duì)列非空時(shí)才能進(jìn)行出隊(duì)操作。

    // 如果隊(duì)列中只有一個(gè)節(jié)點(diǎn)，即隊(duì)首和隊(duì)尾是同一個(gè)節(jié)點(diǎn)
    if (q->front->next == NULL)
    {
        q->front = NULL;  // 將隊(duì)首指針置為空
        q->rear = NULL;   // 將隊(duì)尾指針置為空，因?yàn)殛?duì)列要變?yōu)榭贞?duì)列
    }
    else
    {
        // 如果隊(duì)列中不止一個(gè)節(jié)點(diǎn)，則將隊(duì)首節(jié)點(diǎn)出隊(duì)
        QNode* head = q->front->next;  // 臨時(shí)保存新的隊(duì)首節(jié)點(diǎn)
        free(q->front);  // 釋放當(dāng)前的隊(duì)首節(jié)點(diǎn)的內(nèi)存
        q->front = head;  // 更新隊(duì)首指針為新的隊(duì)首節(jié)點(diǎn)
    }
}

5. 獲取隊(duì)列的隊(duì)頭元素

返回隊(duì)頭指針指向的數(shù)據(jù)即可

QDataType QueueFront(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//檢測(cè)隊(duì)列是否為空

	return q->front->data;//返回隊(duì)頭指針指向的數(shù)據(jù)
}

6.獲取隊(duì)列的隊(duì)尾元素

返回隊(duì)尾指針指向的數(shù)據(jù)即可

QDataType QueueBack(Queue* q)
{
	assert(q);
	assert(!QueueEmpty(q));//檢測(cè)隊(duì)列是否為空

	return q->rear->data;//返回隊(duì)尾指針指向的數(shù)據(jù)
}

7. 檢測(cè)隊(duì)列是否為空

判斷隊(duì)頭的指針是否指向空

bool QueueEmpty(Queue* q)
{
	assert(q);
	return q->front == NULL;
}

8. 獲取隊(duì)列中有效元素個(gè)數(shù)

隊(duì)列中有效元素個(gè)數(shù)，即隊(duì)列中的結(jié)點(diǎn)個(gè)數(shù)。我們只需遍歷隊(duì)列，統(tǒng)計(jì)隊(duì)列中的節(jié)點(diǎn)數(shù)并返回即可

int QueueSize(Queue* q)
{
    assert(q);  // 斷言以確保隊(duì)列指針 'q' 不是 NULL，保證這是一個(gè)有效的指針。

    QNode* cur = q->front;  // 創(chuàng)建一個(gè)指針 'cur'，用來(lái)遍歷隊(duì)列，從隊(duì)首開(kāi)始
    int count = 0;  // 初始化計(jì)數(shù)器 'count'，用于統(tǒng)計(jì)隊(duì)列中的元素?cái)?shù)量

    // 遍歷隊(duì)列，直到 'cur' 指針為空，即到達(dá)隊(duì)列末尾
    while (cur)
    {
        count++;  // 對(duì)每個(gè)節(jié)點(diǎn)進(jìn)行計(jì)數(shù)
        cur = cur->next;  // 將 'cur' 指針移動(dòng)到下一個(gè)節(jié)點(diǎn)
    }
    
    return count;  // 返回隊(duì)列中的元素總數(shù)
}

"Yesterday is history, tomorrow is a mystery, but today is a gift. That is why it is called the present."

昨日已成歷史，明天充滿(mǎn)未知，而今天是一份禮物，這就是為什么它被稱(chēng)為‘現(xiàn)在’。文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-860377.html

到了這里，關(guān)于數(shù)據(jù)結(jié)構(gòu) - 隊(duì)列 [動(dòng)畫(huà)+代碼注釋超詳解]，萌新輕松上手?。?！的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！