一、用鏈表實現隊列,在元素入列和出列時為什么需要判斷鏈表是否為空
結合《算法》這本書之前代碼可知已初始化表尾,元素入列如果為空,則用表尾結點初始化表頭結點;出列時,操作的是表頭結點,當表中元素為空時,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);
}