目錄

隊列的基本概念

隊列的實現

頭文件queue.h

實現函數接口

1.初始化和銷毀

2.出隊列和入隊列

3.獲取隊頭元素和隊尾元素

4.隊列長度+判空

后記

---

前言

歡迎大家來到小鷗的博客~

個人主頁：海盜貓鷗

本篇專題：數據結構

多謝大家的支持啦！

上一篇關于數據結構的博客中我們講解了棧，本篇我們就來講講隊列吧！

隊列的基本概念

1. 隊列：只允許在一端進行插入數據操作，在另一端進行刪除數據操作的特殊線性表，隊列具有先進先出 FIFO(First In First Out)
2. 入隊列：進行插入操作的一端稱為隊尾
3. 出隊列：進行刪除操作的一端稱為隊頭

隊列也可以數組和鏈表的結構實現，使用鏈表的結構實現更優一些，因為如果使用數組的結構，出隊列在數組頭上出數據，效率會比較低。

如果使用數組，每次出隊列之后，都需要移動數據，消耗較大。

所以本篇使用單鏈表實現隊列，因為頭刪和尾插剛好可以滿足隊列的需要，單鏈表消耗最大的就是尾刪后遍歷查找新尾節點，但隊列不需要尾刪，所以不存在這個問題。

隊列的入隊列順序和出隊列順序一定是相同的。

隊列的實現

隊列的C語言實現，我們要實現的函數和實現棧是差不多的：
只是其存放數據的數據結構變為了一個鏈表

頭文件queue.h

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int QueueDataType;typedef struct QueueNode
{QueueDataType data;struct QueueNode* next;
}QNode;typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化和銷毀
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入隊列和出隊列
void QueuePush(Queue* pq, QueueDataType x);
void QueuePop(Queue* pq);//隊頭元素和隊尾元素
QueueDataType QueueFront(Queue* pq);
QueueDataType QueueBack(Queue* pq);//隊列長度函數
int QueueSize(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);

這里我們除了定義了鏈表節點的結構體QueueNode之外，我們還額外創建了一個Queue的結構體，這個結構體是用來存放隊列的一些信息的，phead指向隊頭，ptail則指向隊尾，這樣進行入棧和出棧的操作時，就可以直接通過這倆個指針直接對鏈表進行頭刪和尾插操作，從而實現出隊列和入隊列操作，；size則表示隊列的數據個數。

實現函數接口

1.初始化和銷毀

因為我們是通過Queue結構體來操作隊列的，所以不論初始化還是后面的函數都需要的是Queue*類型的指針；

//初始化和銷毀
void QueueInit(Queue* pq)
{assert(pq);pq->size = 0;pq->phead = pq->ptail = NULL;
}
void QueueDestroy(Queue* pq)
{assert(pq);QNode* cur = pq->phead;while (cur){QNode* next = cur->next;free(cur);cur = next;}pq->phead = pq->ptail = NULL;pq->size = 0;
}

由于是本質是一個鏈表結構，所以在釋放空間時，需要遍歷鏈表進行釋放。

2.出隊列和入隊列

隊列入數據只能從隊尾插入；出數據只能從隊頭出。

//入隊列(尾插)
void QueuePush(Queue* pq, QueueDataType x)
{assert(pq);//動態申請空間創建空間QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail!");return;}newnode->data = x;newnode->next = NULL;//沒有節點時if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else//存在節點{pq->ptail->next = newnode;pq->ptail = newnode;}//隊列長度pq->size++;
}
//出隊列(頭刪)
void QueuePop(Queue* pq)
{assert(pq);assert(pq->phead != NULL);//只有一個節點if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多個節點{QNode* newhead = pq->phead->next;free(pq->phead);pq->phead = newhead;}pq->size--;
}

入隊列和出隊列就是運用的鏈表的尾插和頭刪的邏輯。

3.獲取隊頭元素和隊尾元素

//隊頭元素和隊尾元素
QueueDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead != NULL);return pq->phead->data;
}
QueueDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail != NULL);return pq->ptail->data;
}

由于我們的Queue結構體中就存儲了隊頭和隊尾的地址，所以這兩個函數就可以直接返回對應的數據。

4.隊列長度+判空

//隊列長度函數
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
//判空
bool QueueEmpty(Queue* pq)
{assert(pq);return !(pq->size);
}

Queue結構體中的size就是在這里起作用的，如果沒有size這個成員，就需要遍歷鏈表來實現。

后記

本篇隊列的介紹和C語言實現就結束啦！

下篇我們將講解幾道棧和隊列的相關OJ題，大家不見不散哦！

那么我們下次見~