關(guān)于隊(duì)列的介紹,在前面一篇 循環(huán)隊(duì)列 已經(jīng)說過。我們來看看第二種隊(duì)列——鏈隊(duì)列。 物理結(jié)構(gòu)為鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的隊(duì)列，對(duì)內(nèi)存空間的利用率更高。

鏈?zhǔn)疥?duì)列的表示

image

是不是似曾相識(shí)的結(jié)構(gòu)？鏈棧，再看看鏈棧的表示

image

區(qū)別：
棧，新的元素添加在棧頂，而且棧頂先出；
隊(duì)列，隊(duì)尾進(jìn)，隊(duì)首出。
二者相反
所以，我們鏈隊(duì)列的操作簡(jiǎn)單來說就是：

• 進(jìn)入隊(duì)列 ：Q.rear尾節(jié)點(diǎn)后追加新節(jié)點(diǎn)，將Q.rear指向新節(jié)點(diǎn)，新節(jié)點(diǎn)成隊(duì)尾；
• 出隊(duì)列 ：Q.front指向的首元節(jié)點(diǎn)出隊(duì)列，Q.front指向首元節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)

老規(guī)矩先定義數(shù)據(jù)結(jié)構(gòu)

#define ERROR 0
#define TRUE 1
#define FALSE 0
#define OK 1

typedef int Status;/* Status是函數(shù)的類型,其值是函數(shù)結(jié)果狀態(tài)代碼，如OK等 */
typedef int ElemType;/* ElemType類型根據(jù)實(shí)際情況而定，這里假設(shè)為int */

typedef struct QueueNode {
    ElemType data;
    struct QueueNode *next;
} QueueNode, *QueueNodePtr;

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

初始化

先創(chuàng)建一個(gè)頭節(jié)點(diǎn)，讓Q.front和Q.rear指向頭節(jié)點(diǎn)，頭節(jié)點(diǎn)的next為NULL

image

/// 初始化
Status InitQueue(LinkQueue *Q)
{
    // 初始隊(duì)列為空,只有頭節(jié)點(diǎn)，不是有效數(shù)據(jù)的節(jié)點(diǎn)
    *Q->front = *Q->rear = (QueueNodePtr)malloc(sizeof(QueueNode));
    if (*Q->front == NULL) return ERROR;
    
    // 頭節(jié)點(diǎn)的后面為空
    *Q->front->next = NULL;
    
    return OK;
}

判斷隊(duì)列為空

當(dāng)隊(duì)列為空時(shí)，恰入上圖初始化的狀態(tài)，只剩一個(gè)頭節(jié)點(diǎn)，此時(shí) Q.front == Q.rear

/// 判斷是否為空
Status QueueEmpty(LinkQueue Q)
{
    if (Q.front == Q.rear) return TRUE;
    return FALSE;
}

進(jìn)入隊(duì)列

進(jìn)入隊(duì)列的操作，是將新元素，追加到rear指向的隊(duì)尾之后，rear->next = 新元素，再將rear指向新元素，此時(shí)，新元素成為隊(duì)尾。因?yàn)椴皇艽鎯?chǔ)空間限制（內(nèi)存占滿另說），所以不需要一開始就判斷是否隊(duì)滿，也沒有隊(duì)滿的操作。

• 創(chuàng)建新節(jié)點(diǎn)p
• 追加到隊(duì)尾
• 隊(duì)列的rear指向p，標(biāo)記成新隊(duì)尾

image

Status EnQueue(LinkQueue *Q, ElemType e)
{
    QueueNodePtr p = (QueueNodePtr)malloc(sizeof(QueueNode));
    if (p == NULL) return ERROR;
    
    p->data = e;
    p->next = NULL;
    // 追加到隊(duì)尾
    *Q->rear->next = p;
    // 標(biāo)記成隊(duì)尾
    *Q->rear = p;
    
    return OK;
}

出隊(duì)列

出隊(duì)列操作，是將首元節(jié)點(diǎn)從鏈隊(duì)刪除。

• 判斷隊(duì)列是否為空
• 找到隊(duì)首節(jié)點(diǎn)head（此時(shí)已拿到節(jié)點(diǎn)，將該節(jié)點(diǎn)的data回調(diào)出去），等待刪除
• 更改標(biāo)記head后面的節(jié)點(diǎn)s為首元節(jié)點(diǎn)，即head->next
• 判斷是否是最后一個(gè)節(jié)點(diǎn)，是的話，rear也指向頭節(jié)點(diǎn)
• 釋放原首節(jié)點(diǎn)head

image

Status DeQueue(LinkQueue *Q, ElemType *e)
{
    if (QueueEmpty(*Q)) return ERROR;
    
    QueueNodePtr head;
    // 找到要?jiǎng)h除的節(jié)點(diǎn)
    head = *Q->front->next;
    // 回調(diào)到函數(shù)外
    *e = head->data;
    // 更改頭節(jié)點(diǎn)
    *Q->front->next = head->next;
    
    // 如果刪到了隊(duì)尾最后一個(gè)元素
    if (*Q->rear == head)
        *Q->rear = *Q->front;
    
    // 刪除臨時(shí)指針指向的頭節(jié)點(diǎn)
    free(head);
    
    return OK;
}

清空

僅清空頭節(jié)點(diǎn)以外的全部節(jié)點(diǎn)，有頭節(jié)點(diǎn)在，清空完，還能繼續(xù)EnQueue()操作。又回到初始化后的狀態(tài)

image

/// 清空隊(duì)列
Status ClearQueue(LinkQueue *Q)
{
    if (*Q->front->next == NULL) return ERROR;
    
    
    QueueNodePtr temp, p; // 首元節(jié)點(diǎn)
    
    *Q->rear = *Q->front;
    p = *Q->front->next;
    *Q->front->next = NULL;
    
    // 此時(shí)只有temp指向首元節(jié)點(diǎn)
    while (p) {
        temp = p;
        p = p->next;
        free(temp);
    }
    
    return OK;
}

銷毀

銷毀操作，和清空不一樣，清空僅僅刪除除頭節(jié)點(diǎn)以外的所有節(jié)點(diǎn)，清空后還可以再入隊(duì)。但是銷毀已經(jīng)徹底不使用，需要連頭節(jié)點(diǎn)也一并free掉，所以代碼中是從front開始，而非front->next。

已free所有的節(jié)點(diǎn)

image

/// 銷毀隊(duì)列
Status DestoryQueue(LinkQueue *Q)
{
    if (*Q->front->next == NULL) return ERROR;
    
    /*
     說明，頭節(jié)點(diǎn)也是個(gè)malloc開辟的，也需要釋放
     */
    while (*Q->front) {
        *Q->rear = *Q->front->next;
        free(*Q->front);
        *Q->front = *Q->rear;
    }
    
    return OK;
}

獲取隊(duì)首

不更改隊(duì)列，不破壞隊(duì)列現(xiàn)有結(jié)構(gòu)，僅查找。所以首元節(jié)的數(shù)據(jù)直接讀取 Q.front->next->data，

Status GetHead(LinkQueue Q, ElemType *e)
{
    if (QueueEmpty(*Q)) return ERROR;
    
    *e = Q.front->next->data;
    
    return OK;
}