一、何為隊列？
隊列 (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++。
閱讀更多 懷念感覺12 的文章
