鏈?zhǔn)疥犃校喎Q"鏈隊列"，即使用鏈表實現(xiàn)的隊列存儲結(jié)構(gòu)。
鏈?zhǔn)疥犃械膶崿F(xiàn)思想同順序隊列類似，只需創(chuàng)建兩個指針（命名為 top 和 rear）分別指向鏈表中隊列的隊頭元素和隊尾元素，如下圖所示:
所示為鏈?zhǔn)疥犃械某跏紶顟B(tài)，此時隊列中沒有存儲任何數(shù)據(jù)元素，因此 top 和 rear 指針都同時指向頭節(jié)點。
在創(chuàng)建鏈?zhǔn)疥犃袝r，強烈建議初學(xué)者創(chuàng)建一個帶有頭節(jié)點的鏈表，這樣實現(xiàn)鏈?zhǔn)疥犃袝唵巍?/p>
由此，我們可以編寫出創(chuàng)建鏈?zhǔn)疥犃械?C 語言實現(xiàn)代碼為:
//鏈表中的節(jié)點結(jié)構(gòu)
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥犃械暮瘮?shù)
QNode * initQueue(){
//創(chuàng)建一個頭節(jié)點
QNode * queue=(QNode*)malloc(sizeof(QNode));
//對頭節(jié)點進行初始化
queue->next=NULL;
return queue;
}
鏈?zhǔn)疥犃袛?shù)據(jù)入隊
鏈隊隊列中，當(dāng)有新的數(shù)據(jù)元素入隊，只需進行以下 3 步操作：
- 將該數(shù)據(jù)元素用節(jié)點包裹，例如新節(jié)點名稱為 elem；
- 與 rear 指針指向的節(jié)點建立邏輯關(guān)系，即執(zhí)行 rear->next=elem；
- 最后移動 rear 指針指向該新節(jié)點，即 rear=elem；
由此，新節(jié)點就入隊成功了。
例如，在上圖的基礎(chǔ)上，我們依次將{1,2,3}依次入隊，各個數(shù)據(jù)元素入隊的過程如下圖所示:
數(shù)據(jù)元素入鏈?zhǔn)疥犃械?C 語言實現(xiàn)代碼為：
QNode* enQueue(QNode * rear,int data){
//1、用節(jié)點包裹入隊元素
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//2、新節(jié)點與rear節(jié)點建立邏輯關(guān)系
rear->next=enElem;
//3、rear指向新節(jié)點
rear=enElem;
//返回新的rear，為后續(xù)新元素入隊做準(zhǔn)備
return rear;
}
鏈?zhǔn)疥犃袛?shù)據(jù)出隊
當(dāng)鏈?zhǔn)疥犃兄?，有?shù)據(jù)元素需要出隊時，按照 "先進先出" 的原則，只需將存儲該數(shù)據(jù)的節(jié)點以及它之前入隊的元素節(jié)點按照原則依次出隊即可。這里，我們先學(xué)習(xí)如何將隊頭元素出隊。
鏈?zhǔn)疥犃兄嘘狀^元素出隊，需要做以下 3 步操作：
- 通過 top 指針直接找到隊頭節(jié)點，創(chuàng)建一個新指針 p 指向此即將出隊的節(jié)點；
- 將 p 節(jié)點（即要出隊的隊頭節(jié)點）從鏈表中摘除；
- 釋放節(jié)點 p，回收其所占的內(nèi)存空間；
例如，在上圖2b) 的基礎(chǔ)上，我們將元素 1 和 2 出隊，則操作過程如下圖所示：
鏈?zhǔn)疥犃兄嘘狀^元素出隊的 C 語言實現(xiàn)代碼為：
void DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("隊列為空");
return ;
}
// 1、
QNode * p=top->next;
printf("%d",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
}
注意，將隊頭元素做出隊操作時，需提前判斷隊列中是否還有元素，如果沒有，要提示用戶無法做出隊操作，保證程序的健壯性。
鏈?zhǔn)疥犃械拈L度
鏈?zhǔn)疥犃械拈L度，只需要設(shè)置一個移動指針，由隊列頭部移動直至到隊列尾部，來達到計數(shù)的效果。
//隊列的長度
int QueueLength(QNode * top)
{
int length=0;
QNode * pMove = top;
if(pMove->next==NULL){//頭指針指向空，長度為0
return length;
}
while (pMove->next !=NULL) {//頭指針不為空，移動指針計算長度
pMove = pMove->next;
length++;
}
return length;
}
鏈?zhǔn)疥犃械拇蛴?/h3>
鏈?zhǔn)疥犃械拇蛴?，實際上也就是一個鏈表的遍歷過程。
void printQueue(QNode * top)
{
QNode * pMove = top->next;
if(pMove->next==NULL){
printf("該隊列為空！\n");
}
while (pMove!=NULL) {
printf("%d ",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
總結(jié)
通過學(xué)習(xí)鏈?zhǔn)疥犃凶罨镜臄?shù)據(jù)入隊和出隊操作，我們可以就實際問題，對以上代碼做適當(dāng)?shù)男薷摹?/p>
前面在學(xué)習(xí)順序隊列時，由于順序表的局限性，我們在順序隊列中實現(xiàn)數(shù)據(jù)入隊和出隊的基礎(chǔ)上，又對實現(xiàn)代碼做了改進，令其能夠充分利用數(shù)組中的空間。鏈?zhǔn)疥犃芯筒恍枰紤]空間利用的問題，因為鏈?zhǔn)疥犃斜旧砭褪菍崟r申請空間。因此，這可以算作是鏈?zhǔn)疥犃邢啾软樞蜿犃械囊粋€優(yōu)勢。
這里給出鏈?zhǔn)疥犃腥腙牶统鲫牭耐暾?C 語言代碼為：
#include <stdio.h>
#include <stdlib.h>
//鏈表中的節(jié)點結(jié)構(gòu)
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥犃械暮瘮?shù)
QNode * initQueue(){
//創(chuàng)建一個頭節(jié)點
QNode * queue=(QNode*)malloc(sizeof(QNode));
//對頭節(jié)點進行初始化
queue->next=NULL;
return queue;
}
QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//使用尾插法向鏈隊列中添加數(shù)據(jù)元素
rear->next=enElem;
rear=enElem;
return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("\n隊列為空");
return rear;
}
QNode * p=top->next;
printf("出隊的元素是：%d \n",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
return rear;
}
//隊列的長度
int QueueLength(QNode * top)
{
int length=0;
QNode * pMove = top;
if(pMove->next==NULL){//頭指針指向空，長度為0
return length;
}
while (pMove->next !=NULL) {//頭指針不為空，移動指針計算長度
pMove = pMove->next;
length++;
}
return length;
}
void printQueue(QNode * top)
{
QNode * pMove = top->next;
if(pMove->next==NULL){
printf("該隊列為空！\n");
}
while (pMove!=NULL) {
printf("%d ",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
int main() {
QNode * queue,*top,*rear;
queue=top=rear=initQueue();//創(chuàng)建頭結(jié)點
//向鏈隊列中添加結(jié)點，使用尾插法添加的同時，隊尾指針需要指向鏈表的最后一個元素
for(int i=0;i<10;i++)
{
rear = enQueue(rear, i+1);
}
printQueue(top);
printf("隊列的長度為：%d\n",QueueLength(top));
//入隊完成，所有數(shù)據(jù)元素開始出隊列
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
return 0;
}
程序運行結(jié)果為：
1 2 3 4 5 6 7 8 9 10
隊列的長度為：10
出隊的元素是：1
出隊的元素是：2
以上就是本次給大家分享的C語言實現(xiàn)鏈?zhǔn)疥犃校缃褡鳛榇髮W(xué)生的我，也開始受網(wǎng)課的折磨了，在家上網(wǎng)課的感覺比在學(xué)校還要累。每天都在上課，寫作業(yè)，所以一直更新文章也比較少。需要了解其他的數(shù)據(jù)結(jié)構(gòu)的知識的，可以訪問個人博客,我們一起交流分享??！
