隊列的鏈?zhǔn)奖硎痉Q為鏈隊列，它實際上是一個同時帶有隊頭指針和隊尾指針的單鏈表。頭指針指向隊頭節(jié)點，尾指針指向隊尾節(jié)點，即單鏈表的最后一個節(jié)點。
當(dāng)q.front==NULL且q.rear==NULL時，鏈?zhǔn)疥犃袨榭铡?br /> 出隊時，首先判斷隊列是否為空，如果不為空，則取出隊頭元素，將其從鏈表中刪除，并讓q.front指向下一個節(jié)點（若該節(jié)點為最后一個節(jié)點，則置q.front和q.rear都為null）。
入隊時，建立一個新節(jié)點，將新節(jié)點插入到鏈表的尾部，并改讓q.rear指向這個新插入的節(jié)點（若原隊列為空隊，則令q.front也指向該節(jié)點）。
不難看出，不設(shè)頭結(jié)點的鏈?zhǔn)疥犃性诓僮魃贤容^麻煩，因此，通常將鏈?zhǔn)疥犃性O(shè)計成一個帶頭結(jié)點的單鏈表，這樣插入和刪除操作就統(tǒng)一了，如圖所示

用單鏈表表示的鏈?zhǔn)疥犃刑貏e適合于數(shù)據(jù)元素變動比較大的情形，而且不存在隊列滿且產(chǎn)生溢出的問題。另外，加入程序中要使用多個隊列，最好使用鏈?zhǔn)疥犃?#xff0c;這樣就不會出現(xiàn)存儲分配不合理和“溢出”的問題。

//隊列之鏈?zhǔn)疥犃?include "stdafx.h" #include "stdlib.h"#define ElementType int //鏈?zhǔn)疥犃械墓?jié)點 typedef struct {ElementType data;//數(shù)據(jù)域LinkNode *next;//節(jié)點指針域 }LinkNode;//鏈?zhǔn)疥犃?typedef struct {LinkNode *front, *rear;//隊列的頭指針和尾指針 }LinkQueue;/* 鏈?zhǔn)疥犃谐跏蓟?1.建立頭結(jié)點，且隊列的頭指針和尾指針都指向該頭結(jié)點 2.頭指針的指針域為null */ void InitQueue(LinkQueue &q) {q.front = q.rear = (LinkNode *)malloc(sizeof(LinkNode));q.front->next = NULL; } /* 判斷鏈?zhǔn)疥犃惺欠駷榭?1.因為我們采用的是帶頭結(jié)點的鏈?zhǔn)疥犃?#xff0c;所以頭指針始終是指向頭結(jié)點的，當(dāng)隊列為空時，讓尾指針也指向頭結(jié)點 2.所以當(dāng)頭指針和尾指針相等時即隊列為空 */ bool QueueEmpty(LinkQueue q) {if (q.front == q.rear) {return true;}return false; } /* 入隊操作 */ void EnQueue(LinkQueue &q, ElementType e) {//開辟新節(jié)點空間LinkNode *s = (LinkNode *)malloc(sizeof(LinkNode));s->data = e;//數(shù)據(jù)域q.rear->next = s;//尾指針指針域指向新節(jié)點q.rear = s;//尾指針節(jié)點位置移動 } /* 出隊操作 */ ElementType Dequeue(LinkQueue &q) {//是否為空if (QueueEmpty) {return NULL;}LinkNode *s = q.front->next;//獲取需要出隊的節(jié)點int e = s->data;//數(shù)據(jù)域賦值q.front->next = s->next;//將需要出隊節(jié)點的指針域賦值給頭指針的指針域if (s == q.rear) {//判讀是否該鏈?zhǔn)疥犃兄兄挥幸粋€節(jié)點了，如果是則將頭指針和尾指針都指向頭結(jié)點即空隊列//頭指針始終是指向頭結(jié)點的q.rear = q.front;}free(s);return e; } /* 銷毀一個鏈?zhǔn)疥犃?*/ void DestoryQueue(LinkQueue &q) {while (q.front->next){LinkNode *s = q.front->next;q.front->next = s->next;free(s);} }

?

總結(jié)

以上是生活随笔為你收集整理的数据结构-队列之链式队列的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。