一、用鏈表實現(xiàn)隊列，在元素入列和出列時為什么需要判斷鏈表是否為空

結合《算法》這本書之前代碼可知已初始化表尾，元素入列如果為空，則用表尾結點初始化表頭結點；出列時，操作的是表頭結點，當表中元素為空時，first節(jié)點中內(nèi)容正確，last節(jié)點仍存有之前內(nèi)容，需將其置為空。

鏈式隊列

鏈式隊列 ： 用鏈表形式實現(xiàn)的隊列。鏈表結點為隊列數(shù)據(jù)存儲區(qū)，鏈表結點包括兩部分數(shù)據(jù)存儲區(qū)和指針存儲區(qū)。

數(shù)據(jù)存儲區(qū) ：存放真實有效數(shù)據(jù)的區(qū)域。

指針存儲區(qū) ：存放下一個鏈表結點的地址。

注意：

1. 鏈式隊列不存在隊列已滿的情況。在內(nèi)存足夠大的情況下，每次動態(tài)申請鏈表結點內(nèi)存都會成功，即不會出現(xiàn)隊列已滿的情況，除非數(shù)據(jù)量超大內(nèi)存不夠。

2. 鏈式隊列只存在隊列為空的情況，在剛創(chuàng)建隊列成功時隊列為空，或者隊列數(shù)據(jù)已全部出隊，則此時隊列為空。

3.在鏈式隊列中頭結點的數(shù)據(jù)域不存放有效數(shù)據(jù)，指針域存放名列前茅個有效數(shù)據(jù)域的結點地址，頭結點的作用是方便對鏈式隊列的操作。

延伸閱讀：

二、鏈式隊列數(shù)據(jù)出隊

1.只有在鏈式隊列非空時出隊數(shù)據(jù)才有效。

2.若只有一個有效結點時，需將隊尾指針指向頭結點，頭結點指針域為空。

3.頭結點指針指向下下個有效結點。

4.結點數(shù)據(jù)出隊。

5.釋放出隊結點數(shù)據(jù)內(nèi)存。

如下圖所示：

//鏈式隊列數(shù)據(jù)出隊

void OutLinkQueue(pLinkQueue queue, int * value)

{

??? pNode queNode = 0;//隊列結點指針

??? if (IsEmptyLinkQueue(queue))

??? {

?????? printf(“鏈式隊列為空，出隊失敗……\r\n”);

?????? *value = 0;

?????? return;

??? }

??? if (queue->qFront->pNext == queue->qRear)//只有一個有效結點

?????? queue->qRear = queue->qFront;//隊尾指針等于隊首指針

??? queNode = queue->qFront->pNext;//結點指針指向隊首有效結點

??? queue->qFront->pNext = queNode->pNext;//隊首結點指針指向下個結點

??? *value = queNode->dat;//出隊結點值

??? free(queNode);//釋放內(nèi)存

??? printf(“出隊成功！出隊值:%d? —->? “, *value);

??? printf(“隊首結點指針:0x%08X??? 隊尾指針:0x%08X\r\n”, queue->qFront->pNext, queue->qRear);

}