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

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

鏈式隊列

鏈式隊列 ： 用鏈表形式實現的隊列。鏈表結點為隊列數據存儲區，鏈表結點包括兩部分數據存儲區和指針存儲區。

數據存儲區 ：存放真實有效數據的區域。

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

注意：

1. 鏈式隊列不存在隊列已滿的情況。在內存足夠大的情況下，每次動態申請鏈表結點內存都會成功，即不會出現隊列已滿的情況，除非數據量超大內存不夠。

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

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

延伸閱讀：

二、鏈式隊列數據出隊

1.只有在鏈式隊列非空時出隊數據才有效。

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

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

4.結點數據出隊。

5.釋放出隊結點數據內存。

如下圖所示：

//鏈式隊列數據出隊

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);//釋放內存

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

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

}

上一篇

大整數類型和一般的整數類型相比各有什么優劣?

下一篇

Java中遍歷數據結構Enumeration和Iterator相比有什么不同?