一、何為佇列？
佇列 （Queue） ：是一種先進先出 （First In First Out ，簡稱 FIFO） 的線性表，也是運算受限的線性表。只允許在表的一端進行插入，而在另一端進行刪除。
隊首 （front） ：允許進行刪除的一端稱為隊首。
隊尾 （rear） ：允許進行插入的一端稱為隊尾。
佇列中沒有元素時稱為空佇列。在空佇列中依次加入元素 a 1 ， a 2 ， …， a n 之後， a 1 是隊首元素， a n 是隊尾元素。顯然退出佇列的次序也只能是 a 1 ， a 2 ， …， a n ，即佇列的修改是依先進先出的原則進行的，如圖 3-5 所示。
二、基本操作
建立新佇列
判空
進隊
出隊
清空隊
獲得隊頭元素
遍歷隊
銷燬隊
隊長
三、佇列的儲存實現及運算實現
與線性表、棧類似，佇列也有順序儲存和鏈式儲存兩種儲存方法。
1．順序佇列
迴圈佇列的型別定義如下：
#define MAXQSIZE 100 //最大佇列長度
typedef struct {
QElemType *base； //動態分配儲存空間
int front； //頭指標，若佇列不空，指向佇列頭元素
int rear； //尾指標，若佇列不空，指向佇列尾元素的下一個位置
} SqQueue；
下面是迴圈佇列上基本操作的實現。
（1）入隊：
int EnQueue （SqQueue &Q， QElemType e） {
if（（Q。rear+1）%MAXQSIZE == Q。front） return ERROR；
Q。base［Q。rear］ = e；
Q。rear = （Q。rear+1） % MAXQSIZE；
return OK；
}
（2）出隊：
int DeQueue （SqQueue &Q， QElemType &e） {
if （Q。front = = Q。rear） return ERROR；
e = Q。base［Q。front］；
Q。front = （Q。front+1） % MAXQSIZE；
return OK；
}
（3）求迴圈佇列元素個數：
int QueueLength（SqQueue Q）{
return （Q。rear-Q。front+MAXQSIZE） %MAXQSIZE；
}
2．鏈佇列
鏈式儲存的隊稱為鏈佇列。和鏈棧類似，用單鏈表來實現鏈佇列，根據隊的先進先出原
則，為了操作上的方便，分別需要一個頭指標和尾指標。
鏈佇列的形式描述如下：
typedef struct QNode { // 結點型別
QElemType data；
struct QNode *next；
} QNode， *QueuePtr；
typedef struct { //鏈佇列型別
QueuePtr front； //隊頭指標
QueuePtr rear； //隊尾指標
} LinkQueue；
定義一個指向鏈佇列的指標：LinkQueue Q；
下面是鏈佇列的基本運算的實現。
（1）入隊
int EnQueue （LinkQueue &Q， QElemType e） {
QNode *p；
p = （QNode *）malloc（sizeof（QNode））；
p->data = e；
p->next = NULL；
Q。rear->next = p；
Q。rear = p；
return OK；
}
（2）出隊
int DeQueue （LinkQueue &Q， QElemType &e） {
if （Q。front == Q。rear） return ERROR； //隊空，出隊失敗
p = Q。front->next；
e = p->data； //隊頭元素放 e 中
Q。front->next = p->next；
if（Q。rear==p） Q。rear= Q。front； //只有一個元素時，此時還要修改隊尾指標
free （p）；
return OK；
}
3．除了棧和佇列之外，還有一種限定性資料結構是雙端佇列。
（1）雙端佇列：可以在雙端進行插入和刪除操作的線性表。
（2）輸入受限的雙端佇列：線性表的兩端都可以輸出資料元素，但是隻能在一端輸入數
據元素。
（3）輸出受限的雙端佇列：線性表的兩端都可以輸入資料元素，但是隻能在一端輸出數
據元素。
結束語
好了，今天的知識就分享到這裡，歡迎關注“懷念感覺12”，私信關鍵詞：學習資料，獲取更多學習資源，如果文章對你有有幫助，請收藏關注，在今後與你分享更多學習c/c++的文章。同時歡迎在下面評論區留言如何學習c/c++。
