鏈?zhǔn)疥?duì)列，簡(jiǎn)稱"鏈隊(duì)列"，即使用鏈表實(shí)現(xiàn)的隊(duì)列存儲(chǔ)結(jié)構(gòu)。
鏈?zhǔn)疥?duì)列的實(shí)現(xiàn)思想同順序隊(duì)列類似，只需創(chuàng)建兩個(gè)指針（命名為 top 和 rear）分別指向鏈表中隊(duì)列的隊(duì)頭元素和隊(duì)尾元素夹供，如下圖所示:
所示為鏈?zhǔn)疥?duì)列的初始狀態(tài)，此時(shí)隊(duì)列中沒有存儲(chǔ)任何數(shù)據(jù)元素仁堪，因此 top 和 rear 指針都同時(shí)指向頭節(jié)點(diǎn)哮洽。
在創(chuàng)建鏈?zhǔn)疥?duì)列時(shí)，強(qiáng)烈建議初學(xué)者創(chuàng)建一個(gè)帶有頭節(jié)點(diǎn)的鏈表弦聂，這樣實(shí)現(xiàn)鏈?zhǔn)疥?duì)列會(huì)更簡(jiǎn)單鸟辅。
由此，我們可以編寫出創(chuàng)建鏈?zhǔn)疥?duì)列的 C 語言實(shí)現(xiàn)代碼為:
//鏈表中的節(jié)點(diǎn)結(jié)構(gòu)
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥?duì)列的函數(shù)
QNode * initQueue(){
//創(chuàng)建一個(gè)頭節(jié)點(diǎn)
QNode * queue=(QNode*)malloc(sizeof(QNode));
//對(duì)頭節(jié)點(diǎn)進(jìn)行初始化
queue->next=NULL;
return queue;
}
鏈?zhǔn)疥?duì)列數(shù)據(jù)入隊(duì)
鏈隊(duì)隊(duì)列中莺葫，當(dāng)有新的數(shù)據(jù)元素入隊(duì)匪凉，只需進(jìn)行以下 3 步操作：
- 將該數(shù)據(jù)元素用節(jié)點(diǎn)包裹，例如新節(jié)點(diǎn)名稱為 elem捺檬；
- 與 rear 指針指向的節(jié)點(diǎn)建立邏輯關(guān)系再层，即執(zhí)行 rear->next=elem；
- 最后移動(dòng) rear 指針指向該新節(jié)點(diǎn)堡纬，即 rear=elem聂受；
由此，新節(jié)點(diǎn)就入隊(duì)成功了烤镐。
例如蛋济，在上圖的基礎(chǔ)上，我們依次將{1,2,3}依次入隊(duì)炮叶，各個(gè)數(shù)據(jù)元素入隊(duì)的過程如下圖所示:
數(shù)據(jù)元素入鏈?zhǔn)疥?duì)列的 C 語言實(shí)現(xiàn)代碼為：
QNode* enQueue(QNode * rear,int data){
//1碗旅、用節(jié)點(diǎn)包裹入隊(duì)元素
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//2渡处、新節(jié)點(diǎn)與rear節(jié)點(diǎn)建立邏輯關(guān)系
rear->next=enElem;
//3、rear指向新節(jié)點(diǎn)
rear=enElem;
//返回新的rear祟辟，為后續(xù)新元素入隊(duì)做準(zhǔn)備
return rear;
}
鏈?zhǔn)疥?duì)列數(shù)據(jù)出隊(duì)
當(dāng)鏈?zhǔn)疥?duì)列中医瘫，有數(shù)據(jù)元素需要出隊(duì)時(shí)，按照 "先進(jìn)先出" 的原則川尖，只需將存儲(chǔ)該數(shù)據(jù)的節(jié)點(diǎn)以及它之前入隊(duì)的元素節(jié)點(diǎn)按照原則依次出隊(duì)即可登下。這里，我們先學(xué)習(xí)如何將隊(duì)頭元素出隊(duì)叮喳。
鏈?zhǔn)疥?duì)列中隊(duì)頭元素出隊(duì)，需要做以下 3 步操作：
- 通過 top 指針直接找到隊(duì)頭節(jié)點(diǎn)缰贝，創(chuàng)建一個(gè)新指針 p 指向此即將出隊(duì)的節(jié)點(diǎn)馍悟；
- 將 p 節(jié)點(diǎn)（即要出隊(duì)的隊(duì)頭節(jié)點(diǎn)）從鏈表中摘除；
- 釋放節(jié)點(diǎn) p剩晴，回收其所占的內(nèi)存空間锣咒；
例如，在上圖2b) 的基礎(chǔ)上赞弥，我們將元素 1 和 2 出隊(duì)毅整，則操作過程如下圖所示：
鏈?zhǔn)疥?duì)列中隊(duì)頭元素出隊(duì)的 C 語言實(shí)現(xiàn)代碼為：
void DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("隊(duì)列為空");
return ;
}
// 1、
QNode * p=top->next;
printf("%d",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
}
注意绽左，將隊(duì)頭元素做出隊(duì)操作時(shí)悼嫉，需提前判斷隊(duì)列中是否還有元素，如果沒有拼窥，要提示用戶無法做出隊(duì)操作戏蔑，保證程序的健壯性。
鏈?zhǔn)疥?duì)列的長(zhǎng)度
鏈?zhǔn)疥?duì)列的長(zhǎng)度鲁纠，只需要設(shè)置一個(gè)移動(dòng)指針总棵，由隊(duì)列頭部移動(dòng)直至到隊(duì)列尾部，來達(dá)到計(jì)數(shù)的效果改含。
//隊(duì)列的長(zhǎng)度
int QueueLength(QNode * top)
{
int length=0;
QNode * pMove = top;
if(pMove->next==NULL){//頭指針指向空情龄，長(zhǎng)度為0
return length;
}
while (pMove->next !=NULL) {//頭指針不為空，移動(dòng)指針計(jì)算長(zhǎng)度
pMove = pMove->next;
length++;
}
return length;
}
鏈?zhǔn)疥?duì)列的打印
鏈?zhǔn)疥?duì)列的打印捍壤，實(shí)際上也就是一個(gè)鏈表的遍歷過程骤视。
void printQueue(QNode * top)
{
QNode * pMove = top->next;
if(pMove->next==NULL){
printf("該隊(duì)列為空！\n");
}
while (pMove!=NULL) {
printf("%d ",pMove->data);
pMove = pMove->next;
}
printf("\n");
}
總結(jié)
通過學(xué)習(xí)鏈?zhǔn)疥?duì)列最基本的數(shù)據(jù)入隊(duì)和出隊(duì)操作白群，我們可以就實(shí)際問題尚胞，對(duì)以上代碼做適當(dāng)?shù)男薷摹?/p>
前面在學(xué)習(xí)順序隊(duì)列時(shí)，由于順序表的局限性帜慢，我們?cè)陧樞蜿?duì)列中實(shí)現(xiàn)數(shù)據(jù)入隊(duì)和出隊(duì)的基礎(chǔ)上笼裳，又對(duì)實(shí)現(xiàn)代碼做了改進(jìn)唯卖，令其能夠充分利用數(shù)組中的空間。鏈?zhǔn)疥?duì)列就不需要考慮空間利用的問題躬柬，因?yàn)殒準(zhǔn)疥?duì)列本身就是實(shí)時(shí)申請(qǐng)空間拜轨。因此，這可以算作是鏈?zhǔn)疥?duì)列相比順序隊(duì)列的一個(gè)優(yōu)勢(shì)允青。
這里給出鏈?zhǔn)疥?duì)列入隊(duì)和出隊(duì)的完整 C 語言代碼為：
#include <stdio.h>
#include <stdlib.h>
//鏈表中的節(jié)點(diǎn)結(jié)構(gòu)
typedef struct QNode{
int data;
struct QNode * next;
}QNode;
//創(chuàng)建鏈?zhǔn)疥?duì)列的函數(shù)
QNode * initQueue(){
//創(chuàng)建一個(gè)頭節(jié)點(diǎn)
QNode * queue=(QNode*)malloc(sizeof(QNode));
//對(duì)頭節(jié)點(diǎn)進(jìn)行初始化
queue->next=NULL;
return queue;
}
QNode* enQueue(QNode * rear,int data){
QNode * enElem=(QNode*)malloc(sizeof(QNode));
enElem->data=data;
enElem->next=NULL;
//使用尾插法向鏈隊(duì)列中添加數(shù)據(jù)元素
rear->next=enElem;
rear=enElem;
return rear;
}
QNode* DeQueue(QNode * top,QNode * rear){
if (top->next==NULL) {
printf("\n隊(duì)列為空");
return rear;
}
QNode * p=top->next;
printf("出隊(duì)的元素是：%d \n",p->data);
top->next=p->next;
if (rear==p) {
rear=top;
}
free(p);
return rear;
}
//隊(duì)列的長(zhǎng)度
int QueueLength(QNode * top)
{
int length=0;
QNode * pMove = top;
if(pMove->next==NULL){//頭指針指向空橄碾，長(zhǎng)度為0
return length;
}
while (pMove->next !=NULL) {//頭指針不為空，移動(dòng)指針計(jì)算長(zhǎng)度
pMove = pMove->next;
length++;
}
return length;
}
void printQueue(QNode * top)
{
QNode * pMove = top->next;
if(pMove->next==NULL){
printf("該隊(duì)列為空颠锉！\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é)點(diǎn)
//向鏈隊(duì)列中添加結(jié)點(diǎn)法牲，使用尾插法添加的同時(shí)，隊(duì)尾指針需要指向鏈表的最后一個(gè)元素
for(int i=0;i<10;i++)
{
rear = enQueue(rear, i+1);
}
printQueue(top);
printf("隊(duì)列的長(zhǎng)度為：%d\n",QueueLength(top));
//入隊(duì)完成琼掠，所有數(shù)據(jù)元素開始出隊(duì)列
rear=DeQueue(top, rear);
rear=DeQueue(top, rear);
return 0;
}
程序運(yùn)行結(jié)果為：
1 2 3 4 5 6 7 8 9 10
隊(duì)列的長(zhǎng)度為：10
出隊(duì)的元素是：1
出隊(duì)的元素是：2
以上就是本次給大家分享的C語言實(shí)現(xiàn)鏈?zhǔn)疥?duì)列拒垃，如今作為大學(xué)生的我，也開始受網(wǎng)課的折磨了瓷蛙，在家上網(wǎng)課的感覺比在學(xué)校還要累悼瓮。每天都在上課，寫作業(yè)艰猬，所以一直更新文章也比較少横堡。需要了解其他的數(shù)據(jù)結(jié)構(gòu)的知識(shí)的，可以訪問個(gè)人博客,我們一起交流分享肮谔摇命贴！
