鏈隊(duì)：隊(duì)列的鏈?zhǔn)奖硎竞蛯?shí)現(xiàn)

相應(yīng)函數(shù)定義

InitQueue(&Q);                  構(gòu)造空隊(duì)列
DestroyQueue(&Q);               銷(xiāo)毀隊(duì)列
ClearQueue(&S);                 清空隊(duì)列
QueueEmpty(S);                  判空.空-TRUE
QueueLength(Q);                 取隊(duì)列長(zhǎng)度
GetHead(Q, &e);                 取隊(duì)頭元素
EnQueue(&Q, e);                 入隊(duì)列
DeQueue(&Q, &e);                出隊(duì)列
QueueTraverse(Q, visit());      遍歷

頭文件寝杖、宏定義

#include<stdlib.h>      // 使用exit(0)時(shí)需要引用頭文件
#define MAXSIZE 100
#define ElemType int
// 以下為使用Status的配套操作
#define Status int
#define OK 1
#define Error 1

定義結(jié)構(gòu)體

#define ElemType int 
typedef struct QNode        // 當(dāng)定義鏈?zhǔn)浇Y(jié)構(gòu)(需要定義指針時(shí)),記得需要再struct后面加類(lèi)名
{
    ElemType data;
    struct QNode* next;     // 這個(gè)記得要寫(xiě)對(duì),就算定義鏈?zhǔn)浇Y(jié)構(gòu)中next指針時(shí)記得加struct
}QNode, *QueuePtr;

typedef struct
{
    QueuePtr front;
    QueuePtr rear;
}LinkQueue;

鏈隊(duì)初始化

• step 1 ： 生成新節(jié)點(diǎn)作為頭結(jié)點(diǎn)宛渐，隊(duì)頭和隊(duì)尾指針都指向此結(jié)點(diǎn)展氓。
• step 2 : 頭結(jié)點(diǎn)的指針域取為NULL

Status InitQueue(LinkQueue& Q)
{
    // 生成新節(jié)點(diǎn)作為頭結(jié)點(diǎn)申钩，對(duì)頭和隊(duì)尾指針指向該結(jié)點(diǎn)
    Q.front = Q.rear = new QNode;
    Q.front->next = NULL;   //頭結(jié)點(diǎn)的指針與置空
    return OK;
}

判斷鏈隊(duì)是否為空

bool EmptyQueue(LinkQueue Q)
{
    return Q.front == Q.rear;
}

求鏈隊(duì)的隊(duì)頭元素

• 記得判斷隊(duì)列是否非空

Status GetHeadQueue(LinkQueue Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;  // 判斷隊(duì)列是否非空
    e = Q.front->data;
    return OK;
}

鏈隊(duì)入隊(duì)

• step 1：為入隊(duì)元素分配結(jié)點(diǎn)空間颂碧，用指針p指向
• step 2：將新結(jié)點(diǎn)數(shù)據(jù)域置為e塑煎，指針域置為空
• step 3：將新結(jié)點(diǎn)插入到隊(duì)尾
• step 4：修改隊(duì)尾指針為p

Status EnQueue(LinkQueue& Q, ElemType e)
{
    // 鏈隊(duì)不需要判斷是否隊(duì)滿(mǎn)
    QNode* p = new QNode;   // 為入隊(duì)元素分配結(jié)點(diǎn)空間沫换，用指針p指向
    p->data = e;            // 將新結(jié)點(diǎn)數(shù)據(jù)域置為e
    p->next = NULL;
    Q.rear->next = p;       // 將新結(jié)點(diǎn)插入到隊(duì)尾
    Q.rear = p;             // 修改隊(duì)尾指針
    return OK;
}

思考：鏈隊(duì)**需要頭結(jié)點(diǎn)**，因?yàn)楫?dāng)沒(méi)有頭結(jié)點(diǎn)時(shí)最铁，我們需要判斷是否為第一個(gè)結(jié)點(diǎn)讯赏，如果為第一個(gè)結(jié)點(diǎn)，那么就將`front`以及`rear`指針指向第一個(gè)結(jié)點(diǎn)冷尉，

鏈隊(duì)出隊(duì)

• step 1：判斷隊(duì)列是否為空漱挎，若空著返回Error
• step 2：臨時(shí)保存隊(duì)頭元素的空間，已備釋放
• step 3：修改頭結(jié)點(diǎn)的指針域雀哨，使其指向下一個(gè)結(jié)點(diǎn)
• step 4：判斷出隊(duì)元素是否為最后一個(gè)元素磕谅，若是，則將隊(duì)尾指針重新賦值雾棺，指向頭結(jié)點(diǎn)膊夹。
• step 5：釋放原始隊(duì)頭元素的空間

Status DeQueue(LinkQueue& Q, ElemType& e)
{
    if (Q.front == Q.rear) return Error;
    QNode* p = new QNode;
    p = Q.front->next;                  // p 指向首元結(jié)點(diǎn)
    e = Q.front->data;                  // e保存隊(duì)頭結(jié)點(diǎn)的數(shù)據(jù)域
    Q.front = Q.front->next;            // 修改頭結(jié)點(diǎn)的指針域
    if (Q.rear == p) Q.rear = Q.front;  // 若刪的是最后一個(gè)元素，則修改隊(duì)尾指針指向頭結(jié)點(diǎn)
    delete p;                           // 釋放原隊(duì)頭元素的空間
    return OK;
}

思考：鏈隊(duì)**需要頭結(jié)點(diǎn)**捌浩，因?yàn)楫?dāng)沒(méi)有頭結(jié)點(diǎn)時(shí)放刨，如果鏈隊(duì)出完后為空，那么我需要將`front`和`rear`指針置空尸饺，又會(huì)多一步判斷进统。

銷(xiāo)毀鏈表

• 將rear指針當(dāng)做第三方指針，用于記錄front->next指針浪听，然后刪除前一個(gè)指針螟碎，直到front指針為空，那么就刪除完了馋辈。

Status DestroyQueue(LinkQueue& Q)
{
    while (Q.front)
    {
        Q.rear = Q.front->next;
        delete Q.front;
        Q.front = Q.rear;
    }
    return OK;
}