1、隊(duì)列的概念

隊(duì)列是一種先進(jìn)先出(First In First Out ，FIFO)的數(shù)據(jù)結(jié)構(gòu)，可以簡(jiǎn)單理解為排隊(duì)的概念。在隊(duì)列中，數(shù)據(jù)項(xiàng)按照插入的順序排列，并且只能在隊(duì)列的一端插入（稱為隊(duì)尾），在另一端刪除（稱為隊(duì)頭）。

2、隊(duì)列的結(jié)構(gòu)

入隊(duì)列：進(jìn)行插入操作的一端稱為隊(duì)尾
出隊(duì)列：進(jìn)行刪除操作的一端稱為隊(duì)頭

如何選擇合適的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)隊(duì)列（數(shù)組or鏈表）

在前面學(xué)習(xí)的順序表中，我們知道數(shù)組只有在尾插和尾刪效率高為O(1)，當(dāng)需要對(duì)頭部元素操作時(shí)效率較低為O(n)。隊(duì)列的特點(diǎn)是在隊(duì)尾插入元素，在隊(duì)頭刪除元素，序列兩端都需要訪問(wèn)，這就導(dǎo)致使用數(shù)組實(shí)現(xiàn)隊(duì)列時(shí)必定有一端的插入(or刪除)效率低，因此不建議使用數(shù)組實(shí)現(xiàn)隊(duì)列。

3、隊(duì)列的鏈?zhǔn)酱鎯?chǔ)

通過(guò)上面的分析，我選擇鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來(lái)實(shí)現(xiàn)隊(duì)列。這是因?yàn)殒準(zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)兩端的高效訪問(wèn)很簡(jiǎn)單——只需要增加一個(gè)尾指針即可實(shí)現(xiàn)兩端的O(1)訪問(wèn)

3.1 隊(duì)列的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)

定義兩個(gè)結(jié)構(gòu)體

• QNode：保存隊(duì)列中節(jié)點(diǎn)的元素?cái)?shù)據(jù)和下一個(gè)節(jié)點(diǎn)
• Queue：保存頭指針、尾指針和隊(duì)列中有效元素個(gè)數(shù)

typedef int QDateType;
typedef struct QueueNode
{QDateType val;//當(dāng)前節(jié)點(diǎn)的數(shù)據(jù)struct QueueNode* next;//當(dāng)前節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)
}QNode;typedef struct Queue
{QNode* phead;//頭指針QNode* ptail;//尾指針int size;//記錄隊(duì)列有效元素個(gè)數(shù)
}Queue;

3.2 隊(duì)列的常見(jiàn)接口

//初始化
void QueueInit(Queue* pq);
//銷毀
void QueueDestroy(Queue* pq);//入隊(duì)列
void QueuePush(Queue* pq,QDateType x);//出隊(duì)列
void QueuePop(Queue* pq);
//獲取隊(duì)頭元素
QDateType QueueFront(Queue* pq);
//獲取隊(duì)尾元素
QDateType QueueBack(Queue* pq);
//判空
bool QueueEmpty(Queue* pq);
//獲取有效元素個(gè)數(shù)
int QueueSize(Queue* pq);

3.3 隊(duì)列的接口實(shí)現(xiàn)

初始化

頭尾指針置空，隊(duì)列有效元素個(gè)數(shù)初始化為0

void QueueInit(Queue* pq)
{assert(pq);//哨兵位可選可不選（可以有也可以沒(méi)有）pq->phead = pq->ptail = NULL;pq->size = 0;
}

判空

直接返回Queue結(jié)構(gòu)體保存的size即可

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

入隊(duì)列

隊(duì)尾入隊(duì)步驟

（1）申請(qǐng)新節(jié)點(diǎn)并初始化該節(jié)點(diǎn)（將x賦值，下一個(gè)節(jié)點(diǎn)置空）
（2）判斷是否存在尾節(jié)點(diǎn)（隊(duì)列是否為空）

• 存在尾節(jié)點(diǎn)（隊(duì)列不為空）：只需將新節(jié)點(diǎn)接到隊(duì)尾，尾指針后移一位即可。
• 不存在尾節(jié)點(diǎn)（隊(duì)列為空）：改變隊(duì)頭和隊(duì)尾的值即可

（3）隊(duì)列有效節(jié)點(diǎn)個(gè)數(shù)加1

void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));//申請(qǐng)新節(jié)點(diǎn)if (newnode == NULL){perror("malloc fail");return;}//對(duì)新節(jié)點(diǎn)初始化newnode->val = x;newnode->next = NULL;//有尾節(jié)點(diǎn)（隊(duì)列不為空）if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{//一個(gè)有效節(jié)點(diǎn)都沒(méi)（隊(duì)列為空）pq->phead = pq->ptail = newnode;}pq->size++;
}

出隊(duì)列

（1）判空（隊(duì)列不為空才能出隊(duì)）
（2）判斷隊(duì)列有效節(jié)點(diǎn)的個(gè)數(shù)

• 一個(gè)節(jié)點(diǎn)：釋放該節(jié)點(diǎn)，將頭尾指針置空
• 多個(gè)節(jié)點(diǎn)：定義臨時(shí)QNode類型變量保存頭節(jié)點(diǎn)的下一個(gè)節(jié)點(diǎn)，釋放頭節(jié)點(diǎn)，頭節(jié)點(diǎn)更新為保存的節(jié)點(diǎn)

（3）隊(duì)列有效節(jié)點(diǎn)個(gè)數(shù)減1

void QueuePop(Queue* pq)
{assert(pq);//三種情況：0個(gè)節(jié)點(diǎn)，1個(gè)節(jié)點(diǎn),多個(gè)節(jié)點(diǎn)//0個(gè)assert(pq->phead);//暴力檢查//if (pq->phead == NULL) return;//溫柔檢查//隊(duì)列只有1個(gè)有效節(jié)點(diǎn)if (pq->phead->next==NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else{//隊(duì)列有多個(gè)有效節(jié)點(diǎn)QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}

獲取隊(duì)頭元素

斷言判斷是否存在頭節(jié)點(diǎn)，如果存在直接返回頭節(jié)點(diǎn)的值即可

QDateType QueueFront(Queue* pq)
{assert(pq);//這里只能暴力檢查assert(pq->phead);return pq->phead->val;
}

獲取隊(duì)尾元素

斷言判斷是否存在尾節(jié)點(diǎn)，如果存在直接返回尾節(jié)點(diǎn)的值即可

QDateType QueueBack(Queue* pq)
{assert(pq);//這里只能暴力檢查assert(pq->ptail);return pq->ptail->val;
}

獲取節(jié)點(diǎn)個(gè)數(shù)

返回size即可

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

銷毀

遍歷刪除（釋放）所有節(jié)點(diǎn)，最后頭尾指針懸空，size置0

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;
}

3.4 源代碼

.h文件

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<stdbool.h>
#include<assert.h>
typedef int QDateType;typedef struct QueueNode
{QDateType val;struct QueueNode* next;
}QNode;
入隊(duì)
為什么需要兩個(gè)指針
//void QueuePush(QNode** head,QNode** ptail);
//
出隊(duì)
//void QueuePop(QNode** head);typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入隊(duì)列
void QueuePush(Queue* pq,QDateType x);//出隊(duì)列
void QueuePop(Queue* pq);QDateType QueueFront(Queue* pq);
QDateType QueueBack(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);

.c文件

#include "Queue.h"//初始化
void QueueInit(Queue* pq)
{assert(pq);//哨兵位可選可不選pq->phead = pq->ptail = NULL;pq->size = 0;
}
//銷毀
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;
}//入隊(duì)列
void QueuePush(Queue* pq, QDateType x)
{assert(pq);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc fail");return;}newnode->val = x;newnode->next = NULL;//有尾節(jié)點(diǎn)if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{//一個(gè)有效節(jié)點(diǎn)都沒(méi)pq->phead = pq->ptail = newnode;}pq->size++;
}//出隊(duì)列
void QueuePop(Queue* pq)
{assert(pq);//三種情況：0個(gè)節(jié)點(diǎn)，1個(gè)節(jié)點(diǎn),多個(gè)節(jié)點(diǎn)//0個(gè)assert(pq->phead);//暴力檢查//if (pq->phead == NULL) return;//溫柔檢查//1個(gè)if (pq->phead->next==NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多個(gè){QNode* next = pq->phead->next;free(pq->phead);pq->phead = next;}pq->size--;
}QDateType QueueFront(Queue* pq)
{assert(pq);//這里只能暴力檢查assert(pq->phead);return pq->phead->val;
}
QDateType QueueBack(Queue* pq)
{assert(pq);//這里只能暴力檢查assert(pq->ptail);return pq->ptail->val;
}
bool QueueEmpty(Queue* pq)
{assert(pq);return pq->size == 0;
}
int QueueSize(Queue* pq)
{assert(pq);return pq->size;
}

4、隊(duì)列的順序存儲(chǔ)（循環(huán)隊(duì)列）

雖然隊(duì)列的一般實(shí)現(xiàn)使用鏈?zhǔn)酱鎯?chǔ)，但是也有一些情況可以使用數(shù)組存儲(chǔ)，比如循環(huán)隊(duì)列。
具體可以查看這篇博客———循環(huán)隊(duì)列OJ

END