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

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

鏈?zhǔn)疥?duì)列

鏈?zhǔn)疥?duì)列 ： 用鏈表形式實(shí)現(xiàn)的隊(duì)列。鏈表結(jié)點(diǎn)為隊(duì)列數(shù)據(jù)存儲(chǔ)區(qū)，鏈表結(jié)點(diǎn)包括兩部分?jǐn)?shù)據(jù)存儲(chǔ)區(qū)和指針存儲(chǔ)區(qū)。

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

指針存儲(chǔ)區(qū) ：存放下一個(gè)鏈表結(jié)點(diǎn)的地址。

注意：

1. 鏈?zhǔn)疥?duì)列不存在隊(duì)列已滿的情況。在內(nèi)存足夠大的情況下，每次動(dòng)態(tài)申請(qǐng)鏈表結(jié)點(diǎn)內(nèi)存都會(huì)成功，即不會(huì)出現(xiàn)隊(duì)列已滿的情況，除非數(shù)據(jù)量超大內(nèi)存不夠。

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

3.在鏈?zhǔn)疥?duì)列中頭結(jié)點(diǎn)的數(shù)據(jù)域不存放有效數(shù)據(jù)，指針域存放名列前茅個(gè)有效數(shù)據(jù)域的結(jié)點(diǎn)地址，頭結(jié)點(diǎn)的作用是方便對(duì)鏈?zhǔn)疥?duì)列的操作。

延伸閱讀：

二、鏈?zhǔn)疥?duì)列數(shù)據(jù)出隊(duì)

1.只有在鏈?zhǔn)疥?duì)列非空時(shí)出隊(duì)數(shù)據(jù)才有效。

2.若只有一個(gè)有效結(jié)點(diǎn)時(shí)，需將隊(duì)尾指針指向頭結(jié)點(diǎn)，頭結(jié)點(diǎn)指針域?yàn)榭铡?/p>

3.頭結(jié)點(diǎn)指針指向下下個(gè)有效結(jié)點(diǎn)。

4.結(jié)點(diǎn)數(shù)據(jù)出隊(duì)。

5.釋放出隊(duì)結(jié)點(diǎn)數(shù)據(jù)內(nèi)存。

如下圖所示：

//鏈?zhǔn)疥?duì)列數(shù)據(jù)出隊(duì)

void OutLinkQueue(pLinkQueue queue, int * value)

{

??? pNode queNode = 0;//隊(duì)列結(jié)點(diǎn)指針

??? if (IsEmptyLinkQueue(queue))

??? {

?????? printf(“鏈?zhǔn)疥?duì)列為空，出隊(duì)失敗……\r\n”);

?????? *value = 0;

?????? return;

??? }

??? if (queue->qFront->pNext == queue->qRear)//只有一個(gè)有效結(jié)點(diǎn)

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

??? queNode = queue->qFront->pNext;//結(jié)點(diǎn)指針指向隊(duì)首有效結(jié)點(diǎn)

??? queue->qFront->pNext = queNode->pNext;//隊(duì)首結(jié)點(diǎn)指針指向下個(gè)結(jié)點(diǎn)

??? *value = queNode->dat;//出隊(duì)結(jié)點(diǎn)值

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

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

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

}