【数据结构入坑指南（六）】
一、队列初探：核心概念与结构设计1.1 深入理解“先进先出”（FIFO）--概念：只允许在一端进行插入数据操作，在另一端进行删除数据操作的特殊线性表，队列具有“先进先出”与栈截然不同的的特点。
入队列：进行插入操作的一端称为队尾；出队列：进行删除操作的一端称为队头；1.1.1 关键抉择：链表 vs 数组--那么实现队，底层结构选择数组实现还是链表实现呢？
：那当然是都可以实现，此时—>二者的插入、删除算法操作总会有一个时间复杂度为O(1)。但是链表有补救操作（尾插为O(N)）——>定义一个指针始终指向尾节点，这就不会导致还要进行循环遍历找到尾节点来插入。
1.2 搭建队列的“骨架”--结构，因为底层实现是链表，就要将节点结构、队列结构一同定义。
代码语言：javascript复制typedef int QDataType;
//链表节点结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
//队列结构
typedef struct Queue
{
QueueNode* phead;
QueueNode* ptail;
}Queue;二、核心功能实现：从零搭建完整队列--下面也是实现一些擦插入、删除操作，先进行初始化
2.1 准备工作：搭建稳固的基础2.1.1 队列初始化：一切从这里开始--初始，头、尾指针均指向NULL。
代码语言：javascript复制//初始化
void QueueInit(Queue* pq)
{
assert(pq);//防止空指针
pq->phead = pq->ptail = NULL;
}2.1.2 判空检测：守护队列的“安全门”--此操作，在出队列时，判断是否有节点。
代码语言：javascript复制bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}2.2 入队操作：在队尾优雅地添加数据代码语言：javascript复制Queue.c
#include "Queue.h"
//入队（尾插）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建新节点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("mallpc fail!");
exit (1);
}
newnode->data = x;
newnode->next = NULL;
//刚开始，链表为空，没有节点
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;//尾指针链接新节点
pq->ptail = pq->ptail->next;//尾指针移动到新节点
}
}
test.c
#include "Queue.h"
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
}
int main()
{
test01();
return 0;
} --插入节点就要先申请一份节点大小的空间，其中节点结构：Data存要求插入的数据，next指 NULL。
--刚开始，队列中没有节点，新插入的节点为第一节点，导致头指针、尾指针都指向新节点。
--以后直接是尾指针 next 指向新节点，然后尾指针移动到新节点。
2.3 出队操作：从队头安全地移除数据代码语言：javascript复制Queue.c
#include "Queue.h"
//出队列
void QueuePop(Queue* pq)
{
assert(!QueueEmpty(pq));//队列是否有节点
//队列中只有一个节点
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
//创建指针将下个节点保存
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
}
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
}
int main()
{
test01();
return 0;
} --操作前，先判断队列是否有节点，有节点才能出队列。
--没有节点，头指针、尾指针都指向空。
--否则，创建新 next 指针将第二节点的地址先保存（也就是头指针指向的结构体中的 next 指针保存着地址），释放后，头指针指向新指针。
2.4 销毁队列：善始善终的内存管理--销毁队列，需要遍历队列依次释放空间（注意提前保存下一节点的地址），最后将头指针、尾指针置空。
代码语言：javascript复制Queue.c
#include "Queue.h"
//销毁
void QueueDesTroy(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
//保存下一节点的地址
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
}三、功能扩展：让队列更加强大3.1 窥探队首：获取但不破坏--因为事先已经定义了指向头节点的指针，且指向的结构体中存在存储当前节点数据的 data 变量，直接返回 data 即可。
代码语言：javascript复制Queue.c
#include "Queue.h"
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
test.c
#include "Queue.h"
void test01()
{
//初始化
Queue q;
QueueInit(&q);
//入队
QueuePush(&q, 1);
QueuePop(&q);
QueuePush(&q, 2);
QueuePop(&q);
QueuePush(&q, 3);
QueuePop(&q);
QueuePush(&q, 4);
//取队首
printf("%d\n", QueueFront(&q));
}
int main()
{
test01();
return 0;
}--随着phead指向的改变，其指向的结构体中访问到的的data、next也随之改变。
3.2 窥探队尾：快速访问末端元素--与上面的取队首数据算法思路一样，也是事先定义了指向尾节点的指针，且指向的结构体中存在存储当前节点数据的 data 变量，直接返回 data 即可。
代码语言：javascript复制Queue.c
#include "Queue.h"
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
test.c
#include "Queue.h"
void test01()
{
//初始化
Queue q;
QueueInit(&q);
//入队
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//取队尾
printf("%d->", QueueBack(&q));
}
int main()
{
test01();
return 0;
}3.3 清点元素：高效统计队列大小--这就需要进行循环内遍历到尾节点，统计个数
代码语言：javascript复制Queue.c
#include "Queue.h"
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
++size;
pcur = pcur->next;
}
return size;
}四、完整代码展示：理论与实践的完美结合4.1 Queue.h：队列的“蓝图”与接口代码语言：javascript复制#include
#include
#include
#include
typedef int QDataType;
//链表节点结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
}QueueNode;
//队列结构
typedef struct Queue
{
QueueNode* phead;//指向队头
QueueNode* ptail;//指向队尾
}Queue;
//初始化
void QueueInit(Queue* pq);
//判队列是否为空
bool QueueEmpty(Queue* pq);
//入队（尾插）
void QueuePush(Queue* pq, QDataType x);
//出队列(队头)
void QueuePop(Queue* pq);
//取队头数据
QDataType QueueFront(Queue* pq);
//取队尾数据
QDataType QueueBack(Queue* pq);
//队列有效元素个数
int QueueSize(Queue* pq);4.2 Queue.c：核心逻辑的完整实现代码语言：javascript复制#include "Queue.h"
//初始化
void QueueInit(Queue* pq)
{
assert(pq);//不能传空指针
pq->phead = pq->ptail = NULL;
}
//入队（尾插）
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
//创建新节点
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("mallpc fail!");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
//刚开始，链表为空，没有节点
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
pq->ptail->next = newnode;//尾指针链接新节点
pq->ptail = pq->ptail->next;//尾指针移动到新节点
}
}
//判队列是否为空
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
//出队列
void QueuePop(Queue* pq)
{
assert(!QueueEmpty(pq));
//队列中只有一个节点
if (pq->phead == pq->ptail)
{
free(pq->phead);
pq->phead = pq->ptail = NULL;
}
else
{
//创建指针将下个节点保存
QueueNode* next = pq->phead->next;
free(pq->phead);
pq->phead = next;
}
}
//取队头数据
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
//取队尾数据
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
//队列有效元素个数
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
++size;
pcur = pcur->next;
}
return size;
}
//销毁
void QueueDesTroy(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
while (pcur)
{
//保存下一节点的地址
QueueNode* next = pcur->next;
free(pcur);
pcur = next;
}
pq->phead = pq->ptail = NULL;
}4.3 test.c：功能验证与测试用例代码语言：javascript复制#include "Queue.h"
void test01()
{
//初始化
Queue q;
QueueInit(&q);
//入队
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
QueuePush(&q, 4);
//出队
/*QueuePop(&q);
QueuePop(&q);
QueuePop(&q);
QueuePop(&q);*/
//取队首
/*printf("%d->", QueueFront(&q));
QueuePop(&q);
printf("%d->", QueueFront(&q));
QueuePop(&q);
printf("%d->", QueueFront(&q));
QueuePop(&q);
printf("%d->", QueueFront(&q));*/
//取队尾
//printf("%d->", QueueBack(&q));
//有效数据
printf("size：%d\n", QueueSize(&q));
}
int main()
{
test01();
return 0;
} 回顾：
【面试高频数据结构（五）】--《手把手实现栈结构：附带完整代码与注释，深度揭秘数组实现香在哪？》
【面试高频数据结构（四）】--《超越单链表的局限：双链表“哨兵位”设计模式，如何让边界处理代码既优雅又健壮？》
结语：队列的实现标志着你在线性数据结构领域已登堂入室。接下来，二叉树与堆的学习将带你进入非线性数据结构的新世界。有趣的是，队列正是基于堆实现的——现在打下的队列基础，将在下一章绽放新的光彩。