1、隊列的概念

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

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

入隊列：進行插入操作的一端稱為隊尾
出隊列：進行刪除操作的一端稱為隊頭

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

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

3、隊列的鏈式存儲

通過上面的分析，我選擇鏈式存儲結(jié)構(gòu)來實現(xiàn)隊列。這是因為鏈式存儲結(jié)構(gòu)實現(xiàn)兩端的高效訪問很簡單——只需要增加一個尾指針即可實現(xiàn)兩端的O(1)訪問

3.1 隊列的鏈式存儲結(jié)構(gòu)

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

• QNode：保存隊列中節(jié)點的元素數(shù)據(jù)和下一個節(jié)點
• Queue：保存頭指針、尾指針和隊列中有效元素個數(shù)

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

3.2 隊列的常見接口

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

3.3 隊列的接口實現(xiàn)

初始化

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

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

判空

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

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

入隊列

隊尾入隊步驟

（1）申請新節(jié)點并初始化該節(jié)點（將x賦值，下一個節(jié)點置空）
（2）判斷是否存在尾節(jié)點（隊列是否為空）

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

（3）隊列有效節(jié)點個數(shù)加1

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

出隊列

（1）判空（隊列不為空才能出隊）
（2）判斷隊列有效節(jié)點的個數(shù)

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

（3）隊列有效節(jié)點個數(shù)減1

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

獲取隊頭元素

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

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

獲取隊尾元素

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

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

獲取節(jié)點個數(shù)

返回size即可

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

銷毀

遍歷刪除（釋放）所有節(jié)點，最后頭尾指針懸空，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;
入隊
為什么需要兩個指針
//void QueuePush(QNode** head,QNode** ptail);
//
出隊
//void QueuePop(QNode** head);typedef struct Queue
{QNode* phead;QNode* ptail;int size;
}Queue;//初始化
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);//入隊列
void QueuePush(Queue* pq,QDateType x);//出隊列
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;
}//入隊列
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é)點if (pq->ptail){pq->ptail->next = newnode;pq->ptail = newnode;}else{//一個有效節(jié)點都沒pq->phead = pq->ptail = newnode;}pq->size++;
}//出隊列
void QueuePop(Queue* pq)
{assert(pq);//三種情況：0個節(jié)點，1個節(jié)點,多個節(jié)點//0個assert(pq->phead);//暴力檢查//if (pq->phead == NULL) return;//溫柔檢查//1個if (pq->phead->next==NULL){free(pq->phead);pq->phead = pq->ptail = NULL;}else//多個{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、隊列的順序存儲（循環(huán)隊列）

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

END