真香！20張圖揭開(kāi)「隊(duì)列」的迷霧，一目了然

隊(duì)列的概念

首先我們聯(lián)想一下鏈表，在單鏈表中，我們只能對(duì)他的鏈表表尾進(jìn)行插入，對(duì)鏈表的表頭進(jìn)行結(jié)點(diǎn)的刪除，這樣強(qiáng)限制性的鏈表，就是我們所說(shuō)的隊(duì)列。

也就是說(shuō)，隊(duì)列（queue）是限定在表的一端進(jìn)行插入，表的另一端進(jìn)行刪除的數(shù)據(jù)結(jié)構(gòu)。

如下圖所示，假如你去買(mǎi)票排隊(duì)，每一列隊(duì)伍都有一個(gè)隊(duì)尾和對(duì)頭，先來(lái)的先買(mǎi)票，后來(lái)的后買(mǎi)，買(mǎi)好的就從對(duì)頭出去，新來(lái)買(mǎi)票的就需要從隊(duì)尾繼續(xù)排隊(duì)。

通常，稱(chēng)進(jìn)數(shù)據(jù)的一端為 隊(duì)尾，出數(shù)據(jù)的一端為 隊(duì)頭，數(shù)據(jù)元素進(jìn)隊(duì)列的過(guò)程稱(chēng)為 入隊(duì)，出隊(duì)列的過(guò)程稱(chēng)為 出隊(duì)。

我們可以總結(jié)如下

隊(duì)列是一個(gè)線性的數(shù)據(jù)結(jié)構(gòu)，并且這個(gè)數(shù)據(jù)結(jié)構(gòu)只允許在一端進(jìn)行插入，另一端進(jìn)行刪除，禁止直接訪問(wèn)除這兩端以外的一切數(shù)據(jù)，且隊(duì)列是一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。

如上圖，隊(duì)列就像一個(gè)兩端相通的水管，只允許一端插入，另一端取出，取出的球就不在水管里面了，而先放入管中的球就會(huì)先從管中拿出。

隊(duì)列存儲(chǔ)結(jié)構(gòu)的實(shí)現(xiàn)有以下兩種方式

• 順序隊(duì)列：在順序表的基礎(chǔ)上實(shí)現(xiàn)的隊(duì)列結(jié)構(gòu)

• 鏈隊(duì)列：在鏈表的基礎(chǔ)上實(shí)現(xiàn)的隊(duì)列結(jié)構(gòu)

兩者的區(qū)別僅是順序表和鏈表的區(qū)別，即在實(shí)際的物理空間中，數(shù)據(jù)集中存儲(chǔ)的隊(duì)列是順序隊(duì)列，分散存儲(chǔ)的隊(duì)列是鏈隊(duì)列。

隊(duì)列的結(jié)點(diǎn)設(shè)計(jì)與初始化

隊(duì)列只有鏈?zhǔn)降脑O(shè)計(jì)方法，其本身分為多種隊(duì)列，如順序隊(duì)列和循環(huán)隊(duì)列，還有衍生的優(yōu)先隊(duì)列等等，我們以順序隊(duì)列的設(shè)計(jì)為例。

首先是隊(duì)列的結(jié)點(diǎn)設(shè)計(jì)，我們可以設(shè)計(jì)出兩個(gè)結(jié)構(gòu)體，一個(gè)結(jié)構(gòu)體Node表示結(jié)點(diǎn)，其中包含有一個(gè)data域和next指針，如圖所示：

其中data表示數(shù)據(jù)，其可以是簡(jiǎn)單的類(lèi)型，也可以是復(fù)雜的結(jié)構(gòu)體。

next指針表示，下一個(gè)的指針，其指向下一個(gè)結(jié)點(diǎn)，通過(guò)next指針將各個(gè)結(jié)點(diǎn)鏈接。

然后我們?cè)偬砑右粋€(gè)結(jié)構(gòu)體，其包括了兩個(gè)分別永遠(yuǎn)指向隊(duì)列的隊(duì)尾和隊(duì)頭的指針，看到這里是不是覺(jué)得和棧很像？

我們主要的操作只對(duì)這兩個(gè)指針進(jìn)行操作，如圖所示：

其結(jié)構(gòu)體設(shè)計(jì)的代碼可以表示為：

//結(jié)點(diǎn)定義
typedef?struct?node{
????int?data;
????struct?node?*next;
}node;
//隊(duì)列定義，隊(duì)首指針和隊(duì)尾指針
typedef?struct?queue{
????node?*front;????//頭指針
????node?*rear;?????//尾指針
}queue;

對(duì)于初始化需要初始化兩個(gè)類(lèi)型，一個(gè)是初始化結(jié)點(diǎn)，一個(gè)是初始化隊(duì)列。

我們看到代碼中的描述，初始化隊(duì)列有些不同，當(dāng)初始化隊(duì)列的時(shí)候，需要將頭尾兩個(gè)結(jié)點(diǎn)指向的內(nèi)容統(tǒng)統(tǒng)置為空，表示是一個(gè)空隊(duì)列，兩個(gè)創(chuàng)建的函數(shù)代碼可以表示為：

//初始化結(jié)點(diǎn)
node?*init_node(){
????node?*n=(node*)malloc(sizeof(node)); if(n==NULL){????//建立失敗，退出 exit(0);
????} return n;
}

//初始化隊(duì)列
queue?*init_queue(){
????queue?*q=(queue*)malloc(sizeof(queue)); if(q==NULL){????//建立失敗，退出 exit(0);
????}
????//頭尾結(jié)點(diǎn)均賦值NULL
????q->front=NULL;??
????q->rear=NULL; return q;
}

判斷隊(duì)列是否為空

這是一個(gè)既簡(jiǎn)單也很要緊的操作，判斷隊(duì)列是否為空直接就是判斷隊(duì)列頭指針是否是空值即可，判斷隊(duì)列是否為空是比較常用的操作，切勿忘記。

其代碼可以表示為：

//隊(duì)列判空
int?empty(queue?*q){ if(q->front==NULL){ return 1;???//1--表示真，說(shuō)明隊(duì)列非空
????}else{ return 0;???//0--表示假，說(shuō)明隊(duì)列為空
????}
}

或者直接利用返回值進(jìn)行更簡(jiǎn)單的判斷也可以，代碼如下：

int?empty(queue?*q){ return q->front==NULL;
}

入隊(duì)操作

入隊(duì)操作變化如下圖:

進(jìn)行入隊(duì)（push）操作的時(shí)候，同樣的，我們首先需要特判隊(duì)列是否為空，如果隊(duì)列為空的話，需要將頭指針和尾指針一同指向第一個(gè)結(jié)點(diǎn)，代碼如下

front=n;
rear=n;

如圖所示：

當(dāng)如果隊(duì)列不為空的時(shí)候，這時(shí)我們只需要將尾結(jié)點(diǎn)向后移動(dòng)，通過(guò)不斷移動(dòng)next指針指向新的結(jié)點(diǎn)構(gòu)成隊(duì)列即可。如圖所示：

其代碼可以表示為：

//入隊(duì)操作
void?push(queue?*q,int?data){
????node?*n?=init_node();
????n->data=data;
????n->next=NULL;???//采用尾插入法
????//if(q->rear==NULL){?????//使用此方法也可以 if(empty(q)){
????????q->front=n;
????????q->rear=n;
????}else{
????????q->rear->next=n;????//n成為當(dāng)前尾結(jié)點(diǎn)的下一結(jié)點(diǎn)
????????q->rear=n;??//讓尾指針指向n
????}
}

出隊(duì)操作

出隊(duì)操作變化如下圖:

出隊(duì)（pop）操作，是指在隊(duì)列不為空的情況下進(jìn)行的一個(gè)判斷，當(dāng)然我們?cè)诖艘惨欢ㄒM(jìn)行隊(duì)列判空的操作，你懂的。

如圖，如果隊(duì)列只有一個(gè)元素了，也就是說(shuō)頭尾指針均指向了同一個(gè)結(jié)點(diǎn)，那么我們直接將頭尾兩指針制空NULL，并釋放這一個(gè)結(jié)點(diǎn)即可，如下圖所示：

當(dāng)隊(duì)列含有以上個(gè)元素時(shí)，我們需要將隊(duì)列的頭指針指向頭指針當(dāng)前指向的下一個(gè)元素，并釋放掉當(dāng)前元素即可，如下圖所示

其代碼可以表示為：

//出隊(duì)操作
void?pop(queue?*q){
????node?*n=q->front; if(empty(q)){ return ;????//此時(shí)隊(duì)列為空，直接返回函數(shù)結(jié)束
????} if(q->front==q->rear){
????????q->front=NULL;??//只有一個(gè)元素時(shí)直接將兩端指向置為空即可
????????q->rear=NULL;
????????free(n);????????//記得歸還內(nèi)存空間
????}else{
????????q->front=q->front->next;
????????free(n);
????}
}

打印隊(duì)列元素（遍歷）

打印隊(duì)列的全部元素可以幫助我們調(diào)試，看到隊(duì)列中具體的數(shù)據(jù)，在隊(duì)列不為空的情況下，通過(guò)結(jié)點(diǎn)的next指向依次遍歷并輸出元素既可。

其代碼可以表示為

//打印隊(duì)列元素
void?print_queue(queue?*q){
????node?*n?=?init_node();
????n=q->front; if(empty(q)){ return ;????//此時(shí)隊(duì)列為空，直接返回函數(shù)結(jié)束
????} while (n!=NULL){ printf("%d\t",n->data);
????????n=n->next;
????} printf("\n");???//記得換行
}

遍歷操作還有很多別的表示方法，比如說(shuō)進(jìn)行計(jì)算隊(duì)列中含有多少元素，代碼如下：

int?calac(queue?*q){
????node?*n?=?init_node();
????n=q->front;
????int?cnt=0;????//計(jì)數(shù)器設(shè)計(jì) if(empty(q)){ return 0;????//此時(shí)隊(duì)列為空，直接返回函數(shù)結(jié)束
????} while (n!=NULL)
????{
????????n=n->next;
????????cnt++;
????} return cnt;
}

順序隊(duì)列的假溢出

什么是假溢出？我們可能會(huì)有疑問(wèn)，溢出還有假的！

這里我們也需要考慮到順序隊(duì)列有什么缺點(diǎn)，對(duì)于順序隊(duì)列而言，其存在已經(jīng)足夠解決大多時(shí)候的設(shè)計(jì)問(wèn)題了，但是其依舊存在一些缺陷和不足。

從上面的解析中我們看到，入隊(duì)和出隊(duì)操作均是直接在其后面進(jìn)行結(jié)點(diǎn)的鏈接和刪除，這種操作會(huì)造成其使用空間不斷向出隊(duì)的那一邊偏移，產(chǎn)生假溢出。

我們來(lái)打打一個(gè)比方，先看看下面的圖：

示例順序隊(duì)列

上圖所示，有一個(gè)順序隊(duì)列，這個(gè)隊(duì)列的大小為5，其已經(jīng)包含了四個(gè)元素data1,data2,data3,data4。

接著，我們對(duì)這個(gè)隊(duì)列進(jìn)行出隊(duì)操作，出隊(duì)2個(gè)元素，隊(duì)列就變成了這個(gè)樣子，如下圖所示：

從圖上看到似乎沒(méi)有什么問(wèn)題，但是當(dāng)我們接著再進(jìn)行入隊(duì)操作，比如我們?nèi)腙?duì)2個(gè)元素，分別是data5和data6。

此時(shí)我們已經(jīng)發(fā)現(xiàn)問(wèn)題了，尾指針移動(dòng)到我們可以進(jìn)行隊(duì)列操作的范圍之外去了，有沒(méi)有發(fā)現(xiàn)？

這種現(xiàn)象我們稱(chēng)呼作為隊(duì)列用的存儲(chǔ)區(qū)還沒(méi)有滿(mǎn)，但隊(duì)列卻發(fā)生了溢出，我們把這種現(xiàn)象稱(chēng)為假溢出。如下圖所示：

出隊(duì)產(chǎn)生假溢出

那么我們有什么辦法解決這個(gè)問(wèn)題呢？這就要涉及到循環(huán)隊(duì)列的性質(zhì)了！

循環(huán)隊(duì)列的概念

可能這個(gè)時(shí)候會(huì)產(chǎn)生一個(gè)疑問(wèn)，我們學(xué)習(xí)的隊(duì)列不是使用鏈表實(shí)現(xiàn)的動(dòng)態(tài)隊(duì)列么？

沒(méi)有空間的時(shí)候會(huì)開(kāi)辟空間，這難道還會(huì)產(chǎn)生假溢出么？

的確，當(dāng)進(jìn)行動(dòng)態(tài)創(chuàng)建隊(duì)列的時(shí)候，也只不過(guò)是向后繼續(xù)不斷的申請(qǐng)內(nèi)存空間；

即使前面出隊(duì)操作釋放掉了前面的空間，但是指針依舊會(huì)向后進(jìn)行移動(dòng)，直到達(dá)到系統(tǒng)預(yù)留給程序的內(nèi)存上界被強(qiáng)行終止；

這對(duì)于極為頻繁的隊(duì)列操作和程序而言是致命的，這時(shí)候，就需要對(duì)我們的隊(duì)列進(jìn)行優(yōu)化，使用更為優(yōu)秀的結(jié)構(gòu)——循環(huán)隊(duì)列。

循環(huán)隊(duì)列就是將隊(duì)列存儲(chǔ)空間的最后一個(gè)位置轉(zhuǎn)而繞到第一個(gè)位置，形成邏輯上的環(huán)狀空間，以此來(lái)供隊(duì)列循環(huán)使用，如下圖。

循環(huán)隊(duì)列就是給定我們隊(duì)列的大小范圍，在原有隊(duì)列的基礎(chǔ)上，只要隊(duì)列的后方滿(mǎn)了，就從這個(gè)隊(duì)列的前面開(kāi)始進(jìn)行插入，以達(dá)到重復(fù)利用空間的效果；

由于循環(huán)隊(duì)列的設(shè)計(jì)思維更像一個(gè)環(huán)，因此常使用一個(gè)環(huán)圖來(lái)表示，但我們需要注意，實(shí)際上循環(huán)隊(duì)列不是一個(gè)真正的環(huán)，它依舊是單線性的。

循環(huán)隊(duì)列的結(jié)構(gòu)設(shè)計(jì)

由于循環(huán)對(duì)列給定了數(shù)據(jù)范圍的大小，所以不需要使用鏈?zhǔn)降膭?dòng)態(tài)創(chuàng)建方法了。

因?yàn)槿绻褂面準(zhǔn)酱鎯?chǔ)，會(huì)無(wú)法確定何時(shí)再回到隊(duì)頭進(jìn)行插入操作，所以我們采用模擬的方法，如圖所示：

其中，data表示一個(gè)數(shù)據(jù)域，int為類(lèi)型，其可以修改為任意自定義的類(lèi)型，比如說(shuō)簡(jiǎn)單的char,float類(lèi)型等等，也可以是復(fù)雜的結(jié)構(gòu)體類(lèi)型。

• maxsize表示循環(huán)隊(duì)列的最大容納量，其表示隊(duì)列的全部可操作空間。

• rear代表尾指針，入隊(duì)時(shí)移動(dòng)。

• front代表頭指針，出隊(duì)時(shí)移動(dòng)。

其代碼可以表示為：

#define?maxsize?10??????//表示循環(huán)隊(duì)列的最大容量 //循環(huán)隊(duì)列的結(jié)構(gòu)設(shè)計(jì)
typedef?struct?cir_queue{
????int?data[maxsize];
????int?rear;
????int?front;
}cir_queue;

循環(huán)隊(duì)列的初始化

循環(huán)隊(duì)列的初始化核心就在于申請(qǐng)空間，并且將front指針和rear指針內(nèi)容賦值為0，即指向第0個(gè)元素即可，這里要注意第 0個(gè)元素內(nèi)容為空，如下圖所示：

其代碼可以表示為：

//初始化
cir_queue?*init(){
????cir_queue?*q?=?(cir_queue*)malloc(sizeof(cir_queue)); if(q==NULL){ exit(0);???//申請(qǐng)內(nèi)存失敗，退出程序
????}
????q->front=0;
????q->rear=0; return q;
}

入隊(duì)操作

入隊(duì)操作同順序隊(duì)列的方法，直接將rear向后移動(dòng)即可。

但是要注意判斷，如果rear達(dá)到了隊(duì)列的空間上線，將要從頭繼續(xù)開(kāi)始移動(dòng)。

這里推薦使用余數(shù)法，即無(wú)論如何求余都是在這片空間內(nèi)進(jìn)行操作，防止一次錯(cuò)誤執(zhí)行就直接整體崩潰，而且也相對(duì)而言更為簡(jiǎn)潔，不推薦使用if語(yǔ)句，這樣顯得比較累贅。

入隊(duì)操作

注意進(jìn)行加一移動(dòng)位置操作的時(shí)候，不能直接q->rear++這樣的操作，這樣計(jì)算機(jī)判斷優(yōu)先級(jí)會(huì)產(chǎn)生讓自己意想不到的后果。

此外這里還需要進(jìn)行一次是否隊(duì)列已滿(mǎn)的判斷，當(dāng)我們r(jià)ear指針的下一個(gè)位置就是front的位置的時(shí)候，即改循環(huán)隊(duì)列已滿(mǎn)。

如圖：

隊(duì)列已滿(mǎn)

其代碼可以表示為：

//入隊(duì)操作push
void?push(cir_queue?*q,int?data){ if((q->rear+1)%maxsize==q->front){ printf("溢出，無(wú)法入隊(duì)\n"); return;
????}else{
????????q->rear=(q->rear+1)%maxsize;
????????q->data[q->rear]=data;
????}
}

出隊(duì)操作

如果順序隊(duì)列的出隊(duì)操作，直接將front進(jìn)行后移一位即可。

這里上面很多地方都提過(guò)了，有一個(gè)需要留意的地方，即隊(duì)列是否為空，當(dāng)隊(duì)列為空的時(shí)候是無(wú)法進(jìn)行出隊(duì)操作的。

出隊(duì)操作

其代碼可以表示為：

//出隊(duì)操作pop
void?pop(cir_queue?*q){ if(q->rear==q->front){ printf("隊(duì)列為空，無(wú)法出隊(duì)\n"); return;
????}else{
????????q->data[q->front]=0;
????????q->front=(q->front+1)%maxsize;
????}
}

遍歷操作

遍歷操作需要借助一個(gè)臨時(shí)變量?jī)?chǔ)存位置front的位置信息，利用i逐步向后移動(dòng)，直到i到達(dá)了rear的位置即可宣告遍歷的結(jié)束。

//遍歷隊(duì)列
void print(cir_queue?*q){
????int?i=q->front; while(i!=q->rear){
????????i=(i+1)%maxsize; printf("%d\t",q->data[i]);???
????} printf("\n");???????//記得換行
}

關(guān)于隊(duì)列的總結(jié)

請(qǐng)牢記這句話：隊(duì)列是一個(gè)先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)。

今天隊(duì)列基礎(chǔ)就講到這里，下一期，我們?cè)僖?jiàn)！