隊列的概念

隊列的概念

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

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

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

通常，稱進數(shù)據(jù)的一端為隊尾，出數(shù)據(jù)的一端為隊頭，數(shù)據(jù)元素進隊列的過程稱為入隊，出隊列的過程稱為出隊。

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

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

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

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

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

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

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

隊列的結(jié)點設(shè)計與初始化

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

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

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

next指針表示，下一個的指針，其指向下一個結(jié)點，通過next指針將各個結(jié)點鏈接。

然后我們再添加一個結(jié)構(gòu)體，其包括了兩個分別永遠指向隊列的隊尾和隊頭的指針，看到這里是不是覺得和棧很像？

我們主要的操作只對這兩個指針進行操作，如圖所示：

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

//結(jié)點定義 typedefstructnode{ intdata; structnode*next; }node; //隊列定義，隊首指針和隊尾指針 typedefstructqueue{ node*front;//頭指針 node*rear;//尾指針 }queue;

對于初始化需要初始化兩個類型，一個是初始化結(jié)點，一個是初始化隊列。

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

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

判斷隊列是否為空

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

其代碼可以表示為：

//隊列判空 intempty(queue*q){ if(q->front==NULL){ return1;//1--表示真，說明隊列非空 }else{ return0;//0--表示假，說明隊列為空 } }

或者直接利用返回值進行更簡單的判斷也可以，代碼如下：

intempty(queue*q){ returnq->front==NULL; }

入隊操作

入隊操作變化如下圖:

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

front=n; rear=n;

如圖所示：

唯一結(jié)點n

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

其代碼可以表示為：

//入隊操作 voidpush(queue*q,intdata){ 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é)點的下一結(jié)點 q->rear=n;//讓尾指針指向n } }

出隊操作

出隊操作變化如下圖:

出隊（pop）操作，是指在隊列不為空的情況下進行的一個判斷，當(dāng)然我們在此也一定要進行隊列判空的操作，你懂的。

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

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

其代碼可以表示為：

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

打印隊列元素（遍歷）

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

其代碼可以表示為

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

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

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

順序隊列的假溢出

什么是假溢出？我們可能會有疑問，溢出還有假的！

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

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

我們來打打一個比方，先看看下面的圖：

示例順序隊列

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

接著，我們對這個隊列進行出隊操作，出隊2個元素，隊列就變成了這個樣子，如下圖所示：

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

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

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

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

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

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

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

沒有空間的時候會開辟空間，這難道還會產(chǎn)生假溢出么？

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

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

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

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

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

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

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

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

因為如果使用鏈式存儲，會無法確定何時再回到隊頭進行插入操作，所以我們采用模擬的方法，如圖所示：

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

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

rear代表尾指針，入隊時移動。

front代表頭指針，出隊時移動。

其代碼可以表示為：

#definemaxsize10//表示循環(huán)隊列的最大容量 //循環(huán)隊列的結(jié)構(gòu)設(shè)計 typedefstructcir_queue{ intdata[maxsize]; intrear; intfront; }cir_queue;

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

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

其代碼可以表示為：

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

入隊操作

入隊操作同順序隊列的方法，直接將rear向后移動即可。

但是要注意判斷，如果rear達到了隊列的空間上線，將要從頭繼續(xù)開始移動。

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

入隊操作

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

此外這里還需要進行一次是否隊列已滿的判斷，當(dāng)我們rear指針的下一個位置就是front的位置的時候，即改循環(huán)隊列已滿。

如圖：

隊列已滿

其代碼可以表示為：

//入隊操作push voidpush(cir_queue*q,intdata){ if((q->rear+1)%maxsize==q->front){ printf("溢出，無法入隊 "); return; }else{ q->rear=(q->rear+1)%maxsize; q->data[q->rear]=data; } }

出隊操作

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

這里上面很多地方都提過了，有一個需要留意的地方，即隊列是否為空，當(dāng)隊列為空的時候是無法進行出隊操作的。

出隊操作

其代碼可以表示為：

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

遍歷操作

遍歷操作需要借助一個臨時變量儲存位置front的位置信息，利用i逐步向后移動，直到i到達了rear的位置即可宣告遍歷的結(jié)束。

//遍歷隊列 voidprint(cir_queue*q){ inti=q->front; while(i!=q->rear){ i=(i+1)%maxsize; printf("%d ",q->data[i]); } printf(" ");//記得換行 }

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

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

責(zé)任編輯：lq