一糖驴、隊(duì)列的概念

隊(duì)列是一個先進(jìn)先出的數(shù)據(jù)結(jié)構(gòu)僚祷。
聯(lián)想一下鏈表，在單鏈表中贮缕，只能對表尾進(jìn)行插入久妆，對表頭進(jìn)行結(jié)點(diǎn)的刪除，這樣強(qiáng)限制性的鏈表跷睦，就是所說的隊(duì)列筷弦。也就是說，隊(duì)列是限定在表的一端進(jìn)行插入抑诸，表的另一端進(jìn)行刪除的數(shù)據(jù)結(jié)構(gòu)烂琴。

通常反症，稱進(jìn)數(shù)據(jù)的一端為隊(duì)尾，出數(shù)據(jù)的一端為隊(duì)首畔派，數(shù)據(jù)元素進(jìn)隊(duì)列的過程稱為入隊(duì)铅碍，出隊(duì)列的過程稱為出隊(duì)。

如上圖，隊(duì)列就像一個兩端相通的水管配紫，只允許一端插入径密，另一端取出，取出的球就不在水管里面了躺孝，而先放入管中的球就會先從管中拿出睹晒。

隊(duì)列存儲結(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ù)集中存儲的隊(duì)列是順序隊(duì)列奋单，分散存儲的隊(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ì)為例应又。

其中 data 表示數(shù)據(jù)汇荐，其可以是簡單的類型洞就，也可以是復(fù)雜的結(jié)構(gòu)體。next 指針表示掀淘，下一個的指針旬蟋，其指向下一個結(jié)點(diǎn)，通過 next 指針將各個結(jié)點(diǎn)鏈接革娄。

然后再添加一個結(jié)構(gòu)體倾贰，其包括了兩個分別永遠(yuǎn)指向隊(duì)列的隊(duì)尾和隊(duì)首的指針冕碟，看到這里是不是覺得和棧很像？

其結(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;

對于初始化需要初始化兩個類型，一個是初始化結(jié)點(diǎn)吞彤，一個是初始化隊(duì)列我衬。代碼中的描述叹放，初始化隊(duì)列有些不同饰恕，當(dāng)初始化隊(duì)列的時候，需要將頭尾兩個結(jié)點(diǎn)指向的內(nèi)容統(tǒng)統(tǒng)置為空井仰，表示是一個空隊(duì)列埋嵌，兩個創(chuàng)建的函數(shù)代碼可以表示為：

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

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

三雹嗦、判斷隊(duì)列是否為空

這是一個既簡單也很要緊的操作，判斷隊(duì)列是否為空直接就是判斷隊(duì)列頭指針是否是空值即可合是。其代碼可以表示為：

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

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

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

四泊藕、入隊(duì)操作

進(jìn)行入隊(duì)(push)操作的時候，同樣的难礼，首先需要判斷隊(duì)列是否為空娃圆，如果隊(duì)列為空的話，需要將頭指針和尾指針一同指向第一個結(jié)點(diǎn)蛾茉，代碼如下：

front=n;
rear=n;

如果隊(duì)列不為空的時候讼呢，這時只需要將尾結(jié)點(diǎn)向后移動，通過不斷移動 next指針指向新的結(jié)點(diǎn)構(gòu)成隊(duì)列即可谦炬。如圖：

其代碼可以表示為：

//入隊(duì)操作
void push(queue *q,int data) { 
  node *n =init_node;
  n->data=data;
  n->next=; 
//采用尾插入法 //if(q->rear==){ 
//使用此方法也可以 
  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ì)(pop)操作，是指在隊(duì)列不為空的情況下進(jìn)行的一個判斷键思，當(dāng)然在此也一定要進(jìn)行隊(duì)列判空的操窜管。

如圖，如果隊(duì)列只有一個元素了稚机，也就是說頭尾指針均指向了同一個結(jié)點(diǎn)幕帆，那么直接將頭尾兩指針置空，并釋放這一個結(jié)點(diǎn)即可赖条，如圖：

當(dāng)隊(duì)列含有以上個元素時失乾，需要將隊(duì)列的頭指針指向頭指針當(dāng)前指向的下一個元素常熙，并釋放掉當(dāng)前元素即可，如圖：

其代碼可以表示為：

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

六裸卫、打印隊(duì)列元素(遍歷)

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

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

遍歷操作還有很多別的表示方法聋袋，比如說進(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; 
//此時隊(duì)列為空穴吹，直接返回函數(shù)結(jié)束 
} 
while (n!=) {
 n=n->next; cnt++; 
} 
return cnt;
}

七幽勒、順序隊(duì)列的假溢出

什么是假溢出？這里需要考慮到順序隊(duì)列有什么缺點(diǎn)港令，對于順序隊(duì)列而言啥容，其存在已經(jīng)足夠解決大多時候的設(shè)計(jì)問題了顷霹，但是其依舊存在一些缺陷和不足咪惠。

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

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

從圖上看到似乎沒有什么問題似芝，但是當(dāng)接著再進(jìn)行入隊(duì)操作，比如入隊(duì)2個元素党瓮，分別是 data5和** data6**详炬。

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

這種現(xiàn)象稱呼作為隊(duì)列用的存儲區(qū)還沒有滿在跳，但隊(duì)列卻發(fā)生了溢出，把這種現(xiàn)象稱為假溢出隐岛。如圖：

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

八聚凹、循環(huán)隊(duì)列的概念

可能這個時候會產(chǎn)生一個疑問割坠，學(xué)習(xí)的隊(duì)列不是使用鏈表實(shí)現(xiàn)的動態(tài)隊(duì)列么？沒有空間的時候會開辟空間妒牙，這難道還會產(chǎn)生假溢出么彼哼？的確，當(dāng)進(jìn)行動態(tài)創(chuàng)建隊(duì)列的時候单旁，也只不過是向后繼續(xù)不斷的申請內(nèi)存空間沪羔；即使前面出隊(duì)操作釋放掉了前面的空間饥伊，但是指針依舊會向后進(jìn)行移動象浑，直到達(dá)到系統(tǒng)預(yù)留給程序的內(nèi)存上界被強(qiáng)行終止；這對于極為頻繁的隊(duì)列操作和程序而言是致命的琅豆，這時候愉豺，就需要對我們的隊(duì)列進(jìn)行優(yōu)化，使用更為優(yōu)秀的結(jié)構(gòu)——循環(huán)隊(duì)列茫因。

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

循環(huán)隊(duì)列就是給定隊(duì)列的大小范圍驰贷，在原有隊(duì)列的基礎(chǔ)上，只要隊(duì)列的后方滿了洛巢，就從這個隊(duì)列的前面開始進(jìn)行插入括袒，以達(dá)到重復(fù)利用空間的效果；由于循環(huán)隊(duì)列的設(shè)計(jì)思維更像一個環(huán)稿茉，因此常使用一個環(huán)圖來表示锹锰，但我們需要注意，實(shí)際上循環(huán)隊(duì)列不是一個真正的環(huán)漓库，它依舊是單線性的恃慧。

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

由于循環(huán)對列給定了數(shù)據(jù)范圍的大小渺蒿，所以不需要使用鏈?zhǔn)降膭討B(tài)創(chuàng)建方法了痢士。因?yàn)槿绻褂面準(zhǔn)酱鎯Γ瑫o法確定何時再回到隊(duì)頭進(jìn)行插入操作茂装，所以采用模擬的方法怠蹂，如圖：

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

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

• rear代表尾指針澜薄，入隊(duì)時移動。

• front代表頭指針摊册，出隊(duì)時移動肤京。

其代碼可以表示為：

#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ì)列的初始化

其代碼可以表示為：

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

十一、循環(huán)隊(duì)列的入隊(duì)操作

其代碼可以表示為：

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

十二、循環(huán)隊(duì)列的出隊(duì)操作

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

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

其代碼可以表示為：

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

十三奥吩、循環(huán)隊(duì)列的遍歷操作

遍歷操作需要借助一個臨時變量儲存位置 front 的位置信息，利用i逐步向后移動蕊梧，直到 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"); 
//記得換行
}