鏈式隊列及基本操作

鏈式隊列，簡稱"鏈隊列"，即使用鏈表實現的隊列存儲結構。

鏈式隊列的實現思想同順序隊列類似，只需創建兩個指針(命名為 top 和 rear)分別指向鏈表中隊列的隊頭元素和隊尾元素，如圖 1 所示:

圖 1 鏈式隊列的初始狀態

圖 1 所示為鏈式隊列的初始狀態，此時隊列中沒有存儲任何數據元素，因此 top 和 rear 指針都同時指向頭節點。

在創建鏈式隊列時，強烈建議初學者創建一個帶有頭節點的鏈表，這樣實現鏈式隊列會更簡單。

由此，我們可以編寫出創建鏈式隊列的實現代碼為:

//鏈表中的節點結構
typedef struct QNode{
    int data;
    struct QNode * next;
}QNode;
//創建鏈式隊列的函數
QNode * initQueue(){
    //創建一個頭節點
    QNode * queue=(QNode*)malloc(sizeof(QNode));
    //對頭節點進行初始化
    queue->next=NULL;
    return queue;
}

鏈式隊列數據入隊

鏈隊隊列中，當有新的數據元素入隊，只需進行以下 3 步操作：

1、將該數據元素用節點包裹，例如新節點名稱為 elem;

2、與 rear 指針指向的節點建立邏輯關系，即執行 rear->next=elem;

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

由此，新節點就入隊成功了。

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

圖 2 {1,2,3} 入鏈式隊列

數據元素入鏈式隊列的實現代碼為：

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

鏈式隊列數據出隊

當鏈式隊列中，有數據元素需要出隊時，按照 "先進先出" 的原則，只需將存儲該數據的節點以及它之前入隊的元素節點按照原則依次出隊即可。這里，我們先學習如何將隊頭元素出隊。

鏈式隊列中隊頭元素出隊，需要做以下 3 步操作：

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

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

3、釋放節點 p，回收其所占的內存空間;

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

圖 3 鏈式隊列中數據元素出隊

鏈式隊列中隊頭元素出隊的實現代碼為：

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);
}

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

總結

通過學習鏈式隊列最基本的數據入隊和出隊操作，我們可以就實際問題，對以上代碼做適當的修改。

前面在學習順序隊列時，由于順序表的局限性，我們在順序隊列中實現數據入隊和出隊的基礎上，又對實現代碼做了改進，令其能夠充分利用數組中的空間。鏈式隊列就不需要考慮空間利用的問題，因為鏈式隊列本身就是實時申請空間。因此，這可以算作是鏈式隊列相比順序隊列的一個優勢。

這里給出鏈式隊列入隊和出隊的完整代碼為：

#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;
    //使用尾插法向鏈隊列中添加數據元素
    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();//創建頭結點
    //向鏈隊列中添加結點，使用尾插法添加的同時，隊尾指針需要指向鏈表的最后一個元素
    rear=enQueue(rear, 1);
    rear=enQueue(rear, 2);
    rear=enQueue(rear, 3);
    rear=enQueue(rear, 4);
    //入隊完成，所有數據元素開始出隊列
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    rear=DeQueue(top, rear);
    return 0;
}

程序運行結果為：

1 2 3 4
隊列為空