鏈?zhǔn)疥犃屑盎静僮?/h1>

鏈?zhǔn)疥犃?，簡稱"鏈隊列"，即使用鏈表實現(xiàn)的隊列存儲結(jié)構(gòu)。

鏈?zhǔn)疥犃械膶崿F(xiàn)思想同順序隊列類似，只需創(chuàng)建兩個指針(命名為 top 和 rear)分別指向鏈表中隊列的隊頭元素和隊尾元素，如圖 1 所示:

圖 1 鏈?zhǔn)疥犃械某跏紶顟B(tài)

圖 1 所示為鏈?zhǔn)疥犃械某跏紶顟B(tài)，此時隊列中沒有存儲任何數(shù)據(jù)元素，因此 top 和 rear 指針都同時指向頭節(jié)點。

在創(chuàng)建鏈?zhǔn)疥犃袝r，強烈建議初學(xué)者創(chuàng)建一個帶有頭節(jié)點的鏈表，這樣實現(xiàn)鏈?zhǔn)疥犃袝唵巍?/p>

由此，我們可以編寫出創(chuàng)建鏈?zhǔn)疥犃械膶崿F(xiàn)代碼為:

//鏈表中的節(jié)點結(jié)構(gòu)
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥犃械暮瘮?shù)
QNode * initQueue(){
    //創(chuàng)建一個頭節(jié)點
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //對頭節(jié)點進行初始化
    queue->next=NULL;
    return queue;
}

鏈?zhǔn)疥犃袛?shù)據(jù)入隊

鏈隊隊列中，當(dāng)有新的數(shù)據(jù)元素入隊，只需進行以下 3 步操作：

1、將該數(shù)據(jù)元素用節(jié)點包裹，例如新節(jié)點名稱為 elem;

2、與 rear 指針指向的節(jié)點建立邏輯關(guān)系，即執(zhí)行 rear->next=elem;

3、最后移動 rear 指針指向該新節(jié)點，即 rear=elem;

由此，新節(jié)點就入隊成功了。

例如，在圖 1 的基礎(chǔ)上，我們依次將 {1,2,3} 依次入隊，各個數(shù)據(jù)元素入隊的過程如圖 2 所示:

圖 2 {1,2,3} 入鏈?zhǔn)疥犃?/p>

數(shù)據(jù)元素入鏈?zhǔn)疥犃械膶崿F(xiàn)代碼為：

QNode* enQueue(QNode * rear,int data){
    //1、用節(jié)點包裹入隊元素
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //2、新節(jié)點與rear節(jié)點建立邏輯關(guān)系
    rear->next=enElem;
    //3、rear指向新節(jié)點
    rear=enElem;
    //返回新的rear，為后續(xù)新元素入隊做準(zhǔn)備
    return rear;
}

鏈?zhǔn)疥犃袛?shù)據(jù)出隊

當(dāng)鏈?zhǔn)疥犃兄?，有?shù)據(jù)元素需要出隊時，按照 "先進先出" 的原則，只需將存儲該數(shù)據(jù)的節(jié)點以及它之前入隊的元素節(jié)點按照原則依次出隊即可。這里，我們先學(xué)習(xí)如何將隊頭元素出隊。

鏈?zhǔn)疥犃兄嘘狀^元素出隊，需要做以下 3 步操作：

1、通過 top 指針直接找到隊頭節(jié)點，創(chuàng)建一個新指針 p 指向此即將出隊的節(jié)點;

2、將 p 節(jié)點(即要出隊的隊頭節(jié)點)從鏈表中摘除;

3、釋放節(jié)點 p，回收其所占的內(nèi)存空間;

例如，在圖 2b) 的基礎(chǔ)上，我們將元素 1 和 2 出隊，則操作過程如圖 3 所示：

圖 3 鏈?zhǔn)疥犃兄袛?shù)據(jù)元素出隊

鏈?zhǔn)疥犃兄嘘狀^元素出隊的實現(xiàn)代碼為：

void DeQueue(QNode * top,QNode * rear){
    if (top->next==NULL) {
        printf("隊列為空");
        return ;
    }
    // 1、
    QNode * p=top->next;
    printf("%d",p->data);
    top->next=p->next;
    if (rear==p) {
        rear=top;
    }
    free(p);
}

注意，將隊頭元素做出隊操作時，需提前判斷隊列中是否還有元素，如果沒有，要提示用戶無法做出隊操作，保證程序的健壯性。

總結(jié)

通過學(xué)習(xí)鏈?zhǔn)疥犃凶罨镜臄?shù)據(jù)入隊和出隊操作，我們可以就實際問題，對以上代碼做適當(dāng)?shù)男薷摹?/p>

前面在學(xué)習(xí)順序隊列時，由于順序表的局限性，我們在順序隊列中實現(xiàn)數(shù)據(jù)入隊和出隊的基礎(chǔ)上，又對實現(xiàn)代碼做了改進，令其能夠充分利用數(shù)組中的空間。鏈?zhǔn)疥犃芯筒恍枰紤]空間利用的問題，因為鏈?zhǔn)疥犃斜旧砭褪菍崟r申請空間。因此，這可以算作是鏈?zhǔn)疥犃邢啾软樞蜿犃械囊粋€優(yōu)勢。

這里給出鏈?zhǔn)疥犃腥腙牶统鲫牭耐暾a為：

#include <stdio.h>
#include <stdlib.h>
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
QNode * initQueue(){
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    queue->next=NULL;
    return queue;
}
QNode* enQueue(QNode * rear,int data){
    QNode * enElem=(QNode*)malloc(sizeof(QNode));
    enElem->data=data;
    enElem->next=NULL;
    //使用尾插法向鏈隊列中添加數(shù)據(jù)元素
    rear->next=enElem;
    rear=enElem;
    return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
    if (top->next==NULL) {
        printf("\n隊列為空");
        return rear;
    }
    QNode * p=top->next;
    printf("%d ",p->data);
    top->next=p->next;
    if (rear==p) {
        rear=top;
    }
    free(p);
    return rear;
}
int main() {
    QNode * queue,*top,*rear;
    queue=top=rear=initQueue();//創(chuàng)建頭結(jié)點
    //向鏈隊列中添加結(jié)點，使用尾插法添加的同時，隊尾指針需要指向鏈表的最后一個元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入隊完成，所有數(shù)據(jù)元素開始出隊列
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    return 0;
}

程序運行結(jié)果為：

1 2 3 4
隊列為空