?🔑🔑博客主頁：阿客不是客

🍓🍓系列專欄：漸入佳境之數據結構與算法

歡迎來到泊舟小課堂

😘博客制作不易歡迎各位👍點贊+?收藏+?關注

一、隊列的概念

隊列是一個線性的數據結構，并且這個數據結構只允許在一端進行插入，另一端進行刪除，禁止直接訪問除這兩端以外的一切數據，且隊列是一個先進先出的數據結構。

通常，稱進數據的一端為隊尾，出數據的一端為隊首，數據元素進隊列的過程稱為入隊，出隊列的過程稱為出隊

隊列與棧類似，實現方式有兩種。一種是以數組的方式實現，另一種以單鏈表來實現。這兩種實現方式各有優劣，并且都有細節需要處理。

二、隊列的聲明與初始化

隊列只有鏈式的設計方法，其本身分為多種隊列，如順序隊列和循環隊列，還有衍生的優先隊列等等，以順序隊列的設計為例。

首先是隊列的結點設計，可以設計出兩個結構體，一個結構體 Node 表示結點，其中包含有 data 針，如圖：

其中 data 表示數據，其可以是簡單的類型，也可以是復雜的結構體。next 指針表示，下一個的指針，其指向下一個結點，通過 next 指針將各個結點鏈接。

然后再添加一個結構體，其包括了兩個分別永遠指向隊列的隊尾和隊首的指針，看到這里是不是覺得和棧很像？

主要的操作只對這兩個指針進行操作，如圖所示：

代碼實現如下：

typedef int QDataType;
// 鏈式結構：表示隊列 
typedef struct QListNode
{struct QListNode* next;QDataType val;
}QNode;// 隊列的結構 
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;

對于初始化需要初始化兩個類型，一個是初始化結點，一個是初始化隊列。代碼中的描述，初始化隊列有些不同，當初始化隊列的時候，需要將頭尾兩個結點指向的內容統統置為空，表示是一個空隊列，函數代碼可以表示為：

void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}

三、入隊

入隊操作如圖：

進行入隊(push)操作的時候，同樣的，首先需要判斷隊列是否為空，如果隊列為空的話，需要將頭指針和尾指針一同指向第一個結點：

如果隊列不為空的時候，這時只需要將尾結點向后移動，通過不斷移動?next指針指向新的結點構成隊列即可。

void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("realloc fail");}newnode->next = NULL;newnode->val = x;if (pq->ptail == NULL){pq->phead = pq->ptail = newnode;}else{pq->ptail->next = newnode;pq->ptail = newnode;}pq->size++;
}

四、出隊

出隊操作如圖：

出隊(pop)操作，是指在隊列不為空的情況下進行的一個判斷，當然在此也一定要進行隊列判空的操。

如圖，如果隊列只有一個元素了，也就是說頭尾指針均指向了同一個結點，那么直接將頭尾兩指針置空，并釋放這一個結點即可，如圖：

當隊列含有以上個元素時，需要將隊列的頭指針指向頭指針當前指向的下一個元素，并釋放掉當前元素即可，如圖：

代碼實現如下：

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

五、獲取隊頭和隊尾元素

我們有頭尾節點的指針，只需要注意鏈表和節點元素不能為空即可

// 獲取隊列頭部元素 
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}

六、獲取隊列中有效元素個數

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

七、檢測隊列是否為空

bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}

八、銷毀隊列

void QueueDestroy(Queue* pq)
{assert(pq);for (int i = 0; i < pq->size; i++){QNode* next = pq->phead;pq->phead = pq->phead->next;free(next);}pq->phead = pq->ptail = NULL;
}

九、完整代碼

9.1 Queue.h

typedef int QDataType;
// 鏈式結構：表示隊列 
typedef struct QListNode
{struct QListNode* next;QDataType val;
}QNode;// 隊列的結構 
typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;// 初始化隊列 
void QueueInit(Queue* pq);
// 隊尾入隊列 
void QueuePush(Queue* pq, QDataType x);
// 隊頭出隊列 
void QueuePop(Queue* pq);
// 獲取隊列頭部元素 
QDataType QueueFront(Queue* pq);
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* pq);
// 獲取隊列中有效元素個數 
int QueueSize(Queue* pq);
// 檢測隊列是否為空
bool QueueEmpty(Queue* pq);
// 銷毀隊列 
void QueueDestroy(Queue* pq);

9.2 Queue.c

// 初始化隊列
void QueueInit(Queue* pq)
{assert(pq);pq->phead = NULL;pq->ptail = NULL;pq->size = 0;
}
// 隊尾入隊列 
void QueuePush(Queue* pq, QDataType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("realloc fail");}newnode->next = NULL;newnode->val = x;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);if (pq->phead == pq->ptail){free(pq->phead);pq->phead = pq->ptail = NULL;} else{QNode* next = pq->phead;pq->phead = pq->phead->next;free(next);}pq->size--;
}
// 獲取隊列頭部元素 
QDataType QueueFront(Queue* pq)
{assert(pq);assert(pq->phead);return pq->phead->val;
}
// 獲取隊列隊尾元素 
QDataType QueueBack(Queue* pq)
{assert(pq);assert(pq->ptail);return pq->ptail->val;
}
// 獲取隊列中有效元素個數 
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}
// 檢測隊列是否為空，如果為空返回非零結果，如果非空返回0 
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
// 銷毀隊列 
void QueueDestroy(Queue* pq)
{assert(pq);for (int i = 0; i < pq->size; i++){QNode* next = pq->phead;pq->phead = pq->phead->next;free(next);}pq->phead = pq->ptail = NULL;
}