初階數據結構	相關知識點	可以通過點擊	以下鏈接進行學習	一起加油！
時間與空間復雜度的深度剖析	深入解析順序表:探索底層邏輯	深入解析單鏈表:探索底層邏輯	深入解析帶頭雙向循環鏈表:探索底層邏輯	深入解析棧:探索底層邏輯
深入解析隊列:探索底層邏輯	深入解析循環隊列:探索底層邏輯

🔥引言

本篇將深入解析隊列:探索底層邏輯，理解底層是如何實現并了解該接口實現的優缺點，以便于我們在編寫程序靈活地使用該數據結構。

🌈個人主頁：是店小二呀
🌈C語言筆記專欄：C語言筆記
🌈C++筆記專欄： C++筆記
🌈初階數據結構筆記專欄： 初階數據結構筆記

🌈喜歡的詩句:無人扶我青云志 我自踏雪至山巔

一、隊列的概念及結構

隊列是指只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表。隊列具有先進先出 FIFO(First In First Out) 這一點跟棧的先進后出是相反的

• 入隊列:進行插入操作的一端并且稱為隊尾

• 出隊列：進行刪除操作的一端并且稱為隊頭

隊列可用通過數組或鏈表結構實現，一般推薦使用鏈表實現更優一點。如果使用數組實現在出隊列時，需要挪移大量數據，效率較低

這里采用鏈表結構實現隊列

![外鏈圖片轉存失敗,源站可能有防盜鏈機制,建議將圖片保存下來直接上傳](https://img-home.csdnimg.cn/images/

在設計隊列結構中，需要設計兩個指針去控制隊列各節點的情況。head(隊頭指針)指向實際對頭元素，taill(隊尾指針)，指向實際隊尾元素，增加一個變量size用于統計元素個數，由于存在多種信息，可以使用結構體統一管理

二、實現隊列的相關接口(Stack.h)

2.1 隊列初始化

void QueueInit(Queue *pq)//所以導致了需要初始化
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

這里需要注意的是:這里不需要對于節點進行初始化，在創建節點時會完成對應的初始化工作。

2.2 隊尾入隊列

void QueuePush(Queue* pq, QDataType x)
{assert(pq);Qnode* newnode = (Qnode*)malloc(sizeof(Qnode));if (newnode == NULL){perror("malloc fail!!!");return ;}//創建為需要初始化下newnode->next = NULL;newnode->val = x;if (pq->phead == NULL)pq->phead = pq->ptail = newnode;else{(pq->ptail)->next = newnode;pq->ptail = newnode;}pq->size++;
}

這里需要注意的是:首先就是空間開辟失敗，然后需要搞清楚我們申請空間是給誰使用的，這里是為節點開辟空間。而不是為Queue結構體對象開辟空間，這里節點之間連接是通過節點指針進行連接

2.3 隊頭出隊列

void QueuePop(Queue* pq)
{assert(pq && pq->phead);Qnode *del = pq->phead;pq->phead = pq->phead->next;free(del);del == NULL;if (pq->phead == NULL){pq->ptail = NULL;}pq->size--;
}

這里需要注意的是:當隊列為空時，意味著頭指針為空，那么尾指針也需要置成空

2.4 獲得隊列頭部元素

QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}

2.5 獲得隊列尾部元素

QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->phead);return pq->ptail->val;
}

2.6 獲取隊列中有效元素個數

int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

2.7 檢測隊列是否為空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->phead == NULL;
}

2.8 打印隊列數據

void QueuePrint(Queue* pq)
{assert(pq);while (!QueueEmpty(pq)){printf("%d->", QueueFront(pq));QueuePop(pq);}
}

這里需要注意的是:這里不能用cur，因為cur是不會動的，phead在pop的時候一直移動

2.9 隊列的銷毀

void QueueDestroy(Queue* pq)
{assert(pq);Qnode* cur = pq->phead;while (cur)//刪除的作用{Qnode* next = cur->next;free(cur);cur = next;}pq->ptail = NULL; pq->phead = NULL;pq->size = 0;
}

這里需要注意的是:這里cur不要手動置空，會跳出循環，需等待cur自動指向空。

三、循環隊列

實際中我們有時還會使用一種隊列叫循環隊列。如操作系統課程講解生產者消費者模型 時可以就會使用循環隊列。環形隊列可以使用數組實現，也可以使用循環鏈表實現。(會單獨一篇來講述)

---

以上就是本篇文章的所有內容，在此感謝大家的觀看！這里是店小二初階數據結構筆記，希望對你在學習初階數據結構中有所幫助！