本文主要講解了隊列的定義和隊列主要功能實現(xiàn)的算法蛙卤。最后會列舉一些隊列在程序設計當中常見的應用實例！相信了解了隊列對你理解數(shù)據(jù)結(jié)構(gòu)和程序設計會更加有益處鸿竖！
1. 隊列的定義
隊列 (Queue)是一種先進先出(first in first out : FIFO)的線性表蒸眠。它只允許在表的一端進行插入前翎，在另一端進行刪除元素。這和我們平時戰(zhàn)隊買票很一樣桑阶。最早進入隊列的元素最先離開柏副，在隊列中，允許插入的一端叫做隊尾(rear),允許刪除的一段則稱為隊頭(front).示意圖如下：
2. 隊列的分類
隊列主要分為兩類：
- 鏈式隊列：鏈式隊列即用鏈表實現(xiàn)的隊列
- 順序隊列：順序隊列是用數(shù)組實現(xiàn)的隊列蚣录，順序隊列通常必須是循環(huán)隊列
本文主要以順序隊列（循環(huán)隊列）為例割择，通過如下幾個問題來分析和介紹順序隊列的相關(guān)知識，(鏈式隊列內(nèi)部以鏈表實現(xiàn)相對更加簡單)
- 順序隊列為什么是循環(huán)隊列萎河？
- 一共需要幾個參數(shù)荔泳，分別是什么含義？
- 入隊偽算法思路
- 出隊偽算法思路
- 如何判斷循環(huán)隊列是否為空
- 如何判斷循環(huán)隊列已滿
- 什么時候該使用順序隊列虐杯？什么時候該使用鏈式隊列
2.0 循環(huán)隊列--隊列的順序表示和實現(xiàn)整體分析
順序隊列本身是一種數(shù)組表示玛歌。在隊列的順序存儲結(jié)構(gòu)中，除了用一組連續(xù)的存儲單元依次存放從隊列頭到隊列尾的元素之外擎椰，尚需附設兩個指針 front 和 rear 分別指示隊列頭元素及隊列尾元素的位置沾鳄。為了在C語言中描述方便，通常有如下約定：初始化創(chuàng)建空隊列時确憨，令 front = rear = 0译荞，每當插入新的隊列尾元素時，“尾指針增 1”休弃；每當刪除隊列頭元素時吞歼，“頭指針增 1”；因此塔猾，在非空隊列下篙骡，頭指針始終指向隊列頭元素，而尾指針始終指向隊列尾元素的下一個位置，如圖所示：
假設當前隊列分配最大空間為6糯俗，則當隊列處于上圖(d)的狀態(tài)時尿褪，不可再繼續(xù)插入新的隊尾元素，否則會因為數(shù)組越界而導致程序代碼被破壞得湘。然而此時又不宜進行存儲再分配擴大數(shù)組空間杖玲，因為隊列的實際可用空間并未占滿。一個巧妙的辦法是將順序隊列臆造為一個環(huán)狀的空間淘正，如圖所示摆马，稱之為循環(huán)隊列：
如圖，指針和隊列之間的關(guān)系不變鸿吆，上圖 (a) 所示循環(huán)隊列中囤采，隊列頭元素是 J3 ，隊列尾元素是 J5,之后J6,J7和J8相繼插入惩淳，則隊列空間均被占滿蕉毯，如圖 (b) 所示，此時 Q.front = Q.rear; 反之思犁，若 J3,J4 和 J5 相繼從圖 (a) 隊列中刪除恕刘，使隊列呈“空”的狀態(tài)，如圖 (c) 所示抒倚，此時存在關(guān)系為 Q.front = Q.rear, 由此可見只憑等式 Q.front = Q.rear無法判斷隊列是“空”還是“滿”褐着。有兩種可處理方式：一種是另外設置一個標志以區(qū)別隊列是 “空” 還是 “滿”；另一種是少用一個元素空間托呕，約定以“隊列頭指針在隊列尾指針的下一位置(指環(huán)狀的下一位置)”作為隊列呈“滿”狀態(tài)的標志含蓉。
從此分析中可見，在C語言中不能用動態(tài)分配的一維數(shù)組來實現(xiàn)循環(huán)隊列项郊，如果用戶的應用程序中設有循環(huán)隊列馅扣，則必須為它設定一個最大隊列長度，若用戶無法預估所用隊列的最大長度着降，則宜采用鏈式隊列差油。
2.1 順序隊列為什么是循環(huán)隊列
循環(huán)隊列是針對順序隊列中最大內(nèi)存空間有限，當隊列處于上圖(d)的狀態(tài)時任洞，不可再繼續(xù)插入新的隊尾元素蓄喇，否則會因為數(shù)組越界而導致程序代碼被破壞。然而此時又不宜進行存儲再分配擴大數(shù)組空間交掏，因為隊列的實際可用空間并未占滿的問題的一種合理的解決方案妆偏。
2.2 一共需要幾個參數(shù)，分別是什么含義
front && rear
不同場合下含義不同盅弛。
- 隊列初始化 -- front 和 rear 的值都是零
- 隊列非空 -- front 代表隊列的第一個元素钱骂，rear 代表隊列的最后一個有效元素的下一個元素
- 隊列為空 -- front 和 rear 相等叔锐，但不一定是零
2.3 入隊偽算法
尾部入隊，分兩步完成
- 將值存入r所代表的位置
- 錯誤寫法 r = r + 1; 正確寫法： r = (r + 1) % 數(shù)組的長度 【n-1對n取余见秽，結(jié)果就是n-1】
2.4 出隊偽算法
頭部出隊愉烙，分兩步完成
- 將f出隊的值保存起來（可以根據(jù)具體需求確定是否要保存）
- f 的指針變動正確寫法： f = (f + 1) % 數(shù)組的長度 【n-1對n取余，結(jié)果就是n-1】
2.5 如何判斷循環(huán)隊列是否為空
如果front == rear 解取，則該隊列一定為空
2.6 如何判斷循環(huán)隊列已滿
預備知識：
front 的值可能比 rear 大
front 的值也可能比 rear 小
當然兩者也完全可能相等
判斷已滿兩種方式：
- 多增加一個標識參數(shù)
- 少用數(shù)組中的一個元素【可以直接用兩個參數(shù)步责，通常使用第二種方式】
如果r 和 f 的值緊挨著，則標識隊列已滿
C語言標識就是：
if ( (r+1)%數(shù)組長度 == f)
隊列已滿
else
隊列未滿
2.7 什么時候該使用順序隊列肮蛹？什么時候該使用鏈式隊列勺择？
如果用戶的應用程序中設有循環(huán)隊列创南，則必須為它設定一個最大隊列長度伦忠，若用戶無法預估所用隊列的最大長度，則宜采用鏈式隊列
3. 隊列的偽算法和實現(xiàn)
此小節(jié)實現(xiàn)的是一個最大隊列長度為 6 的環(huán)形隊列稿辙，下面是本隊列的定義和相關(guān)實現(xiàn)昆码。
隊列類型的定義
#define kQueueMaxLength 6 // 假設最大長度為 6
typedef struct Queue{
int * pBase; // 隊列中操作的數(shù)組
int front; // 隊頭
int rear; // 對尾
}QUEUE;
隊列的初始化
/**
初始化隊列
@param pQueue 要被初始化隊列地址
*/
void init_queue(QUEUE *pQueue){
pQueue->pBase = (int *)malloc(sizeof(int) * kQueueMaxLength); // 初始化，pBase指向長度6的 int* 數(shù)組
pQueue->front = pQueue->rear = 0;
}
元素入隊
/**
入隊
@param pQueue 要入隊的隊列地址
@param val 入隊元素的值
@return 入隊成功/失敗
*/
bool en_queue(QUEUE *pQueue , int val){
if (full_queue(pQueue)) { // 隊列已滿邻储，直接返回入隊失敗
return false;
}else
{ // 隊列未滿赋咽，執(zhí)行入隊操作
// 1.元素插入數(shù)組中
pQueue->pBase[pQueue->rear] = val;
// 2.隊頭隊尾的表示
pQueue->rear = (pQueue->rear + 1) % kQueueMaxLength;
return true;
}
}
元素出隊
/**
出隊
@param pQueue 要出隊隊列地址
@param val 被出隊元素地址
@return 出隊成功/失敗
*/
bool de_queue(QUEUE *pQueue , int *val){
if (empty_queue(pQueue)) { // 如果是空隊列，直接出隊失敗
return false;
}else
{
// 出隊->保存被出隊元素的值
*val = pQueue->pBase[pQueue->front];
// 修改隊頭位置
pQueue->front = (pQueue->front + 1) % kQueueMaxLength;
}
return true;
}
遍歷隊列
/**
遍歷隊列
@param pQueue 要遍歷的隊列的地址
*/
void tranverce_queue(QUEUE *pQueue){
int i = pQueue->front;
int lenght = 0;
while (i != pQueue->rear) {
lenght ++;
i = (i + 1) % kQueueMaxLength;
}
printf("隊列中共有 %d 個元素\n",lenght);
i = pQueue->front;
while (i != pQueue->rear) {
printf("第 %d 個元素為 %d\n",i + 1,pQueue->pBase[i]);
i = (i + 1) % kQueueMaxLength;
}
}
主函數(shù)中使用隊列
int main() {
QUEUE q; // 聲明隊列q
init_queue(&q); // 初始化隊列q
en_queue(&q, 2); // 插入元素
en_queue(&q, 21); // 插入元素
en_queue(&q, 3); // 插入元素
en_queue(&q, 4); // 插入元素
en_queue(&q, 5); // 插入元素
en_queue(&q, 6); // 插入元素
en_queue(&q, 7); // 插入元素
en_queue(&q, 8); // 插入元素
tranverce_queue(&q); //遍歷隊列
int i;
bool b;
b = de_queue(&q, &i); // 出隊
printf("出隊%s,元素為 %d\n",b?"成功":"失敗",i);
b = de_queue(&q, &i); // 出隊
printf("出隊%s,元素為 %d\n",b?"成功":"失敗",i);
b = de_queue(&q, &i); // 出隊
printf("出隊%s,元素為 %d\n",b?"成功":"失敗",i);
tranverce_queue(&q); //遍歷隊列
return 0;
}
4. 小結(jié)
隊列主要應用在和時間有關(guān)的操作吨娜。
常見的例子如現(xiàn)實生活中排隊買票脓匿，銀行排隊處理事情。再如操作系統(tǒng)中執(zhí)行隊列宦赠，等待隊列陪毡。又如我們在編寫程序過程中的多線程編程，也需要通過隊列來管理線程的訪問順序等勾扭。
