一、隊列是什么？

先舉一個日常例子，排隊買飯。

排隊買飯

大家按先來后到的順序，在窗口前排隊買飯，先到先得，買完之后走開，輪到下一位買，新來的人排在隊尾，不能插隊。

可見，上面的“隊”的特點是只允許從一端進入，從另一端離開。

這樣的一個隊，放在數據結構中就是“隊列”。

首先，隊列是一個線性表，所以它具有線性表的基本特點。

其次，隊列是一個受限的線性表，受限之處為：只允許從一端進入隊列，從另一端離開。

由此可得：?

? ? ? ? 隊列Queue，是一種操作受限的線性表，只允許在表的一端進行插入，而在表的另一端進行刪除（只允許在隊尾添加元素，在隊頭刪除元素，不支持隨機訪問），向隊列中插入元素稱為入隊或進隊；刪除元素稱為出隊或離隊,FIFO

相關名詞解釋：

• 入隊：進入隊列，即向隊列中插入元素
• 出隊：離開隊列，即從隊列中刪除元素
• 隊頭：允許出隊(刪除)的一端
• 隊尾：允許入隊(插入)的一端
• 隊頭元素：隊列中最先入棧的元素
• 隊尾元素：隊列中最后入棧的元素

二、隊列的實現思路

和棧一樣，隊列也可以有兩種實現方式：數組實現的順序隊列和鏈表實現的鏈隊列。

2.1 隊列的鏈式存儲

2.1.1 原理

? ? ? ? 隊列的鏈式表示稱為鏈隊列，實際是一個同時帶有隊頭指針和隊尾指針的單鏈表。

頭指針指向隊頭結點，尾指針指向隊尾結點，即單鏈表的最后一個結點

以看到，要實現一個鏈隊列，需要以下結構：

1.單鏈表的基本單元結點 —— QueueNode

• 存儲數據的數據域 —— data
• 指向下一個結點的指針域 —— next

2.指向鏈表的頭指針 —— head

3.標識隊頭端的隊頭指針 —— front

4.標識隊尾端的隊尾指針 —— rear

其中，頭指針 head 和隊頭指針 front 都指向了單鏈表的第一個結點，所以這個指針可以合二為一，隊頭指針即頭指針。

如此一來，我們可以借助鏈表的尾插法實現隊列的入隊操作，借助鏈表的頭刪法實現隊列的出隊操作。

?可參考動畫版：Linked List Queue Visualization

2.1.2 隊列的狀態

【空隊列】：空隊列中沒有元素，此時，隊頭下標和隊尾下標均為 0，即front = rear = 0：?

【非空非滿隊列】：隊列不是空隊列且有剩余空間：

【滿隊列】：順序隊列分配的固定空間用盡，沒有多余空間，不能再插入元素，此時 front = 0，rear = MAXSIZE：

2.1.3?代碼實現

typedef int Elemtype;
typedef struct LinkNode {Elemtype data;struct LinkNode *next;
}LinkNode;//先進先出
typedef struct {LinkNode *front, *rear;
}LinkQueue;

2.1.3.1 初始化隊列

//隊列的初始化，使用的是帶頭節點的鏈表
void init_queue(LinkQueue &Q) {Q.front = Q.rear=(LinkNode*)malloc(sizeof(LinkNode));Q.front->next =NULL;}

2.1.3.2 入隊

//入隊
void enqueue(LinkQueue &Q, Elemtype m) {LinkNode *pnew = (LinkNode *)malloc(sizeof(LinkNode));pnew->data = m;pnew->next =NULL;//要讓next 為nullQ.rear->next = pnew;//尾指針next指向pnew,尾插法Q.rear =pnew;//rear指向新的尾部}

2.1.3.3 出隊

bool dequeue(LinkQueue &Q, Elemtype &m) {if (Q.front ==Q.rear) {//隊列為空return false;}LinkNode *q=Q.front->next;//拿到第一個節點，存入qQ.front->next = q->next;讓節點斷鏈m = q->data;if (Q.rear ==q) {Q.rear = Q.front;//鏈表只剩一個節點時，被刪除后要改變rear}free(q);
return true;}

2.1.3.4 主函數

int main() {LinkQueue Q;init_queue(Q);enqueue(Q, 3);enqueue(Q, 4);//   enqueue(Q, 5);Elemtype elem;bool ret;ret = dequeue(Q,elem);if (ret) {printf("dequeue success ele=%d\n",elem);}else {printf("dequeue failed\n");}ret = dequeue(Q,elem);if (ret) {printf("dequeue success ele=%d\n",elem);}else {printf("dequeue failed\n");}ret = dequeue(Q,elem);if (ret) {printf("dequeue success ele=%d\n",elem);}else {printf("dequeue failed\n");}return 0;
}

三、循環隊列

3.1 原理

將這種順序隊列畫成一個圓：

循環隊列的 rear 和 front 能夠在隊列中一圈一圈地轉，像鐘表的時針和分針一樣。?

【空隊列】：隊列中沒有元素，空隊列的條件 ?front = rear?

【滿隊列】：少用一個元素，rear + 1 = front

【歸零法】：就像鐘表的時針滿 12 歸零一樣，front 和 rear 也應該滿某個數后歸零，這個數就是 MAXSIZE。

比如 rear = 6 時，如果按平常做法來 ，下一步應該是 rear = 7，但在這里，我們讓其歸零，所以下一步應該是 rear = 0。

用數學公式來表示上面的歸零過程就是：rear % MAXSIZE

所以滿隊列的判斷條件應該為：(rear + 1) % MAXSIZE = front。

3.2 循環隊列的數組實現

3.2.1 定義

typedef int ElementType;
typedef struct {ElementType data[MaxSize];int front, rear;//隊列頭，隊列尾
}SqQueue;

3.2.2 ?初始化循環隊列

void init_queue(SqQueue &Q) {Q.front =Q.rear = 0;//初始化循環隊列，讓頭尾都指向零號}

3.3.3 判斷空隊

bool is_empty(SqQueue Q) {return Q.front==Q.rear;}

3.3.4 入隊

//入隊
bool enqueue(SqQueue &Q,ElementType m ) {//判斷循環隊列是否滿？if ((Q.rear +1) % MaxSize == Q.front){return  false;}Q.data[Q.rear]=m;Q.rear=(Q.rear + 1)%MaxSize;//rear +1 ,如果大于數組最大下標需要回到開頭return  true;
}

3.3.5 出隊

bool dequeue(SqQueue &Q, ElementType &m) {if (Q.front == Q.rear) {return  false;}m = Q.data[Q.front];Q.front = (Q.front + 1) %MaxSize;return true;}

3.3.6 主函數

int main() {SqQueue Q;init_queue(Q);bool ret;ret= is_empty(Q);if (ret) {printf("SqQueue is empty\n");}else{printf("SqQueue is not empty\n");}enqueue(Q, 3);enqueue(Q, 4);enqueue(Q, 5);enqueue(Q, 6);ret = enqueue(Q, 7);ret =  enqueue(Q, 8);if (ret) {printf("SqQueue success\n");}else{printf("SqQueue failed\n");}ElementType element;ret  =  dequeue(Q, element);if (ret) {printf("dequeue success\n");}else{printf("dequeue failed\n");}ret =  enqueue(Q, 8);if (ret) {printf("SqQueue success\n");}else{printf("SqQueue failed\n");}return 0;
}

?3.3循環隊列的鏈式存儲實現（單向循環鏈表）

隊頭指針為front，隊尾指針為rear；

隊空的判斷條件：front== rear

隊滿的判定條件：front ==?rear->next

3.3.1 代碼實戰

typedef int ElemType;
typedef struct LNode {ElemType data;struct LNode* next;
}LNode, *LinkList;

3.3.1.1 初始化

void CircleQueue(LinkList &front,LinkList &rear) {front=(LinkList)malloc(sizeof(LNode));rear = front;rear->next = front;EnQueue(front,rear,3);EnQueue(front,rear,3);DeQueue(front,rear);DeQueue(front,rear);DeQueue(front,rear);}

3.3.1.2 入隊

void EnQueue(LinkList &front,LinkList &rear, ElemType x) {LinkList pnew;if (rear->next == front) {pnew = (LinkList)malloc(sizeof(LNode));rear->data = x;pnew->next = rear->next;rear->next = pnew;rear = pnew;}else {rear->data =x;rear = rear->next;}
}

3.3.1.2 出隊

void DeQueue(LinkList &front,LinkList &rear) {if (front == rear) {printf("the queue is empty\n");}else {printf("the valude=%d\n",front->data);front = front->next;}}

參考地址：https://www.51cto.com/article/656335.html