隊列在編程語言中是如何定義的呢？小編與大家分享自己的經驗。
隊列的定義
隊列是限制結點插入操作固定在一端進行,而結點的刪除操作固定在另一端進行的線性表.
隊列猶如一個兩端開口的管道.允許插入的一端稱為隊頭,允許刪除的一端稱為隊尾.隊頭和隊尾各用一個”指針”指示,稱為隊頭指針和隊尾指針.不含任何結點的隊列稱為”空隊列”.隊列的特點是結點在隊列中的排隊次序和出隊次序按進隊時間先后確定,即先進隊者先出隊.因此,隊列又稱先進先出表.簡稱FIFO(first in first out)表.
步驟
隊列是用來存儲暫未處理但需要按一定順序處理的元素的一種數據結構。
隊列是一種先進先出（First In First Out，FIFO）的線性表，特點是先進隊的元素先出隊。
隊列只允許在表的一端進行插入，而在另一端刪除元素。
隊尾是隊列中允許插入的一端；隊首是隊列中允許刪除的一端。
一般用順序表q[m]存儲隊列中的元素，m是隊列能存儲元素的最大數量。
front隊首指針指向隊首元素存儲的位置；rear隊尾指針指向隊尾元素的下一個位置。
順序隊列及其操作
隊列的順序存儲結構
順序存儲結構存儲的隊列稱為順序隊列.和順序表一樣,用一個一維數組存.對頭在數組的低下標端,隊尾設在高下表端.隊頭,隊尾指針值是數組元素的下標.對頭指針始終指向對頭結點的前一個結點位置,初始值為0.隊尾指針是指向隊尾結點位置,初始值也為0.
隊列初始條件:隊頭指針=隊尾指針=0
隊列滿條件:隊尾指針=m(設隊列當前容量為m)
隊列空條件:隊頭指針=隊尾指針
在QueueCs.c文件中定義了結構
#define DT char#define M 100typedef struct { DT data[M]; int front,rear;}SEQUEUE;data[M]也為數組為隊列,front為隊頭指針,rear為隊尾指針.(注意:front和rear是整數類型,不是指針類型),當front=rear=0時,為初始隊列.因為C語言中數組的第一個元素下標為0,而不是1;所以這里約定數組元素data[0]閑置不用.
順序隊列上的操作
(1)創建隊列
初始化隊列,隊頭指針和隊尾指針=0.
在QueueControl.h寫出方法聲明
/* 創建隊列 */SEQUEUE initQueue();
在QueueControl.c中實現此方法
#include "QueueControl.h"/* 創建隊列 */SEQUEUE initQueue(){ SEQUEUE Q; //1.初始化隊列,隊頭指針=隊尾指針=0 Q.front=Q.rear=0; return Q;}(2)插入
在QueueControl.h寫出方法聲明
/* 插入 */SEQUEUE inQueue(SEQUEUE Q,DT x);
在QueueControl.c中實現此方法
#include "QueueControl.h"SEQUEUE inQueue(SEQUEUE Q,DT x){ //1.判斷隊列是上溢,就是隊尾指針是否等于最大申請的空間 if(Q.rear==M){ printf("Up Overflow/n"); }else{ //2.從隊尾插入結點 Q.rear++; Q.data[Q.rear]=x; printf("in success/n"); } return Q;}(3)刪除
在QueueControl.h寫出方法聲明
/* 刪除 */SEQUEUE outQueue(SEQUEUE Q);/* 打印隊列元素 */void printQueue(SEQUEUE Q);
在QueueControl.c中實現此方法
#include "QueueControl.h"SEQUEUE outQueue(SEQUEUE Q){ //1.首先判斷是否是空隊列 if(Q.front==Q.rear){ printf("queue is empty/n"); }else{ //2.刪除結點是從隊頭刪除 Q.front++; printf("out success/n"); } return Q;}/* 打印隊列元素 */void printQueue(SEQUEUE Q){ //1.從隊頭開始打印數據 SEQUEUE temp=Q; printf("queue={"); while (temp.front<temp.rear) { temp.front++; if(temp.front==Q.front+1){ printf("%c",temp.data[temp.front]); }else{ printf(",%c",temp.data[temp.front]); } } printf("}/n");}在main.c中的main方法(int main(int argc, const char * argv[]) {})調用此方法,并且進行判斷
#include "QueueControl.h"int main(int argc, const char * argv[]) { //初始化順序隊列 SEQUEUE queue=initQueue(); printQueue(queue); //插入 queue=inQueue(queue, 'a'); queue=inQueue(queue, 'b'); queue=inQueue(queue, 'c'); queue=inQueue(queue, 'd'); printQueue(queue); //刪除 queue=outQueue(queue); printQueue(queue); return 0;}打印結果:
queue={}
in success
in success
in success
in success
queue={a,b,c,d}
out success
queue={b,c,d}
Program ended with exit code: 0
從插入隊列和刪除隊列操作的打印結果來看,隊列的特點確實是:先進先出.
循環隊列及其操作
循環隊列的存儲結構
根據順序隊列的操作和敘述可以看出,隊尾指針=m表示隊滿,不能再插入結點了,當隊頭指針等于隊尾指針表示對空.但是當隊尾指針和隊尾指針都等于m的時候,那么此時表示對空,那么也不能插入了其他的結點,但是此時0-m之間的結點已經空閑,這樣許多空閑的結點不能被利用,浪費存儲空間.
循環隊列是把順序隊列的頭尾相接形成一個圓環.邏輯上吧1號結點作為m號結點的后繼結點處理.
循環隊列初始條件:隊頭指針=隊尾指針=0
循環隊列隊滿條件:MOD(隊尾指針+1,m)=隊頭指針
循環隊列空條件:隊頭指針=隊尾指針
隊頭指針推進計算:隊頭指針=MOD(隊頭指針+1,m)
隊尾指針推進計算:隊尾指針=MOD(隊尾指針+1,m)
在QueueCycleCs.c文件中定義了結構
#define CDT char#define CM 5typedef struct { CDT data[CM]; int front,rear;}SECYCLEQUEUE;循環隊列上的操作
(1)創建循環隊列
初始化隊列,隊頭指針和隊尾指針=0.
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c"/* 創建循環隊列 */SECYCLEQUEUE initCycleQueue();
在QueueCycyleControl.c中實現此方法
#include "QueueCycleControl.h"/* 創建循環隊列 */SECYCLEQUEUE initCycleQueue(){ SECYCLEQUEUE Q; //隊頭指針=隊尾指針=0; Q.front=Q.rear=0; return Q;}(2)插入
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c"/* 循環隊列插入 */SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,char x);
在QueueCycyleControl.c中實現此方法
#include "QueueCycleControl.h"SECYCLEQUEUE inCycleQueue(SECYCLEQUEUE Q,CDT x){ //1.判斷循環隊列是否已經滿了,MOD(隊尾指針+1,m)=隊頭指針 if((Q.rear+1)%CM==Q.front){ printf("queue is full!/n"); }else{ //2.在隊尾插入,計算隊尾指針的 Q.rear=(Q.rear+1)%CM; //3.設置插入結點的值數值 Q.data[Q.rear]=x; printf("in Cycle queue Success!/n"); } return Q;}(3)刪除
在QueueCycyleControl.h寫出方法聲明
#include "QueueCycleCs.c"/* 循環隊列刪除 */SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q);/* 打印循環隊列 */void printCycleQueue(SECYCLEQUEUE Q);
在QueueCycyleControl.c中實現此方法
#include "QueueCycleControl.h"SECYCLEQUEUE outCycleQueue(SECYCLEQUEUE Q){ //1.判斷循環隊列是否是空 if(Q.front==Q.rear){ printf("Cycle queue is Empty!/n"); }else{ //2.刪除結點從隊頭刪除,計算隊頭指針:隊頭指針=MOD(隊頭指針+1,m) Q.front=(Q.front+1)%CM; printf("out cycle queue success!/n"); } return Q;}/* 打印循環隊列 */void printCycleQueue(SECYCLEQUEUE Q){ //M=5; //1.從隊頭開始打印數據 SECYCLEQUEUE temp=Q; printf("queue={"); //2.判斷的條件是,隊頭指針!=隊尾指針 while (temp.front!=temp.rear) { temp.front=(temp.front+1)%CM; if(temp.front==((Q.front+1)%CM)){ printf("%c",temp.data[temp.front]); }else{ printf(",%c",temp.data[temp.front]); } } printf("}/n");}在main.c中的main方法(int main(int argc, const char * argv[]) {})調用此方法,并且進行判斷
#include "QueueCycleControl.h"int main(int argc, const char * argv[]) { //創建循環隊列 SECYCLEQUEUE CQ=initCycleQueue(); //插入數據5個結點,但是最大是5,一個空閑,最后一個添加不進去, CQ=inCycleQueue(CQ, 'a'); CQ=inCycleQueue(CQ, 'b'); CQ=inCycleQueue(CQ, 'c'); CQ=inCycleQueue(CQ, 'd'); CQ=inCycleQueue(CQ, 'e'); printCycleQueue(CQ); //刪除節點-三個結點 CQ=outCycleQueue(CQ); CQ=outCycleQueue(CQ); CQ=outCycleQueue(CQ); printCycleQueue(CQ); //插入-兩個結點 CQ=inCycleQueue(CQ, 'e'); CQ=inCycleQueue(CQ, 'f'); printCycleQueue(CQ); //刪除節點--刪除四個結點,現在此時是三個結點,最后一個刪除不了 CQ=outCycleQueue(CQ); CQ=outCycleQueue(CQ); CQ=outCycleQueue(CQ); CQ=outCycleQueue(CQ); printCycleQueue(CQ); return 0;}打印結果:
in Cycle queue Success!
in Cycle queue Success!
in Cycle queue Success!
in Cycle queue Success!
queue is full!
queue={a,b,c,d}
out cycle queue success!
out cycle queue success!
out cycle queue success!
queue=prv9h3b
in Cycle queue Success!
in Cycle queue Success!
queue={d,e,f}
out cycle queue success!
out cycle queue success!
out cycle queue success!
Cycle queue is Empty!
queue={}
Program ended with exit code: 0
鏈隊列及其操作
隊列的鏈存儲結構
鏈存儲結構存儲的隊列稱為鏈隊列.隊頭指針指向鏈隊列的頭結點,頭結點的指針域若為空,則為空隊列;若不為空,則為指向隊首結點的指針.
鏈隊列設有一個隊頭指針,其值指向隊列的頭結點.也是唯一地標示一個鏈隊.設置一個隊尾指針方便插入結點.隊頭指針和隊尾指針都是指針型變量.
鏈隊列沒有容量的限制,所以在可用的存儲空間范圍內,一般不會出現上溢問題,也不存在如順序隊列的假溢出問題.
在QueueLinkCs.c中定義了結構
#define LDT char//結點類型typedef struct llnode{ LDT data; struct llnode *next;}LINKNODE;//鏈隊列結構typedef struct{ LINKNODE *front,*rear;}LINKQUEUE;鏈隊列上的操作
(1)創建鏈隊列
在QueueLinkControl.h寫出方法聲明
#include <stdio.h>#include "QueueLinkCs.c"/* 創建鏈隊 */LINKQUEUE * initLinkQueue(LINKQUEUE *LQ);
在QueueLinkControl.c中實現此方法
#include "QueueLinkControl.h"#include <stdlib.h>/* 創建鏈隊 */LINKQUEUE *initLinkQueue(LINKQUEUE *LQ){ //設置隊頭指針 LQ->front=(LINKNODE *)malloc(sizeof(LINKNODE)); LQ->front->data='#';//設置隊頭指針,也是頭結點的指針域 LQ->front->next=NULL; //初始條件:隊頭指針和隊尾指針一致 LQ->rear=LQ->front; return LQ;}(2)插入
在QueueLinkControl.h寫出方法聲明
/* 鏈隊插入:隊尾 */LINKQUEUE * inLinkQueue(LINKQUEUE *LQ,LDT x);
在QueueLinkControl.c中實現此方法
(3)刪除
在QueueLinkControl.h寫出方法聲明
/* 鏈隊刪除:隊頭 */LINKQUEUE *outLinkQueue(LINKQUEUE *LQ);/* 打印鏈表結點 */void printLinkQueue(LINKQUEUE *LQ);
在QueueLinkControl.c中實現此方法
#include "QueueLinkControl.h"#include <stdlib.h>LINKQUEUE *outLinkQueue(LINKQUEUE *LQ){ if(LQ==NULL || LQ->rear==LQ->front){ printf("LQ is empty!/n"); return LQ; } //1.獲取首結點 LINKNODE *frontNextNode; frontNextNode=LQ->front->next; //2.將首節點的next指針域的值存儲頭結點的next域 LQ->front->next=frontNextNode->next; //3.如果隊尾結點等于首節點的next指針域的值,那么表示是空棧,根據空鏈隊列的結構,還需修改隊尾指針,使指向頭結點. if(LQ->rear==frontNextNode){ LQ->rear=LQ->front; } //4.釋放刪除的結點 free(frontNextNode); printf("out link queue success!/n"); return LQ;}/* 打印鏈表結點 */void printLinkQueue(LINKQUEUE *Q){ //實例化一個LQ,為了不改變原來鏈隊Q LINKQUEUE *LQ; LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE)); LQ->front=Q->front; LQ->rear=Q->rear; printf("queue={"); //1.判斷不是空鏈表 if(LQ!=NULL && LQ->rear!=LQ->front){ int flag=0; do{ //2.輸出數據 if(flag==0){ printf("%c",LQ->front->data); flag=1; }else{ printf(",%c",LQ->front->data); } //3.鏈頭指針向后移動 LQ->front=LQ->front->next; }while (LQ->front!=LQ->rear) ; printf(",%c",LQ->front->data); } printf("}/n");}在main.c中的main方法(int main(int argc, const char * argv[]) {})調用此方法,并且進行判斷
#include "QueueLinkControl.h"int main(int argc, const char * argv[]) { //創建鏈隊列 LINKQUEUE *LQ=(LINKQUEUE *)malloc(sizeof(LINKQUEUE)); LQ=initLinkQueue(LQ); //向鏈隊插入結點 LQ=inLinkQueue(LQ,'a'); LQ=inLinkQueue(LQ,'b'); LQ=inLinkQueue(LQ,'c'); LQ=inLinkQueue(LQ,'d'); printLinkQueue(LQ); //刪除結點--從隊頭 LQ=outLinkQueue(LQ); LQ=outLinkQueue(LQ); printLinkQueue(LQ); return 0;}打印結果:
in link queue success!
in link queue success!
in link queue success!
in link queue success!
queue={#,a,b,c,d}
out link queue success!
out link queue success!
queue={#,c,d}
Program ended with exit code: 0
以上就是本文的全部內容，希望對大家的學習有所幫助，也希望大家多多支持VEVB武林網。
新聞熱點
疑難解答
