数据结构：队列
前言
本篇文章将讲解队列的概念和结构，队列的实现等知识的相关内容，本章代码实现的知识，与单向链表相关，所以如果还没看过单向链表文章，可以看看：
一、队列概念与结构
概念
与栈的数据结构类似，队列：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)特性。
入队列：进行插入操作的一端称为队尾。
出队列：进行删除操作的一端称为队头。
图示：
我们可以将其类比成“单向管道”，数据从管道的一端（队尾）进入，只能从另一端（队头）按顺序流出，中间无法插队或删除中间元素，正好契合了他的“先进先出（FIFO）”的特性。
即：
入队（Enqueue） → 向管道塞入数据；出队（Dequeue） → 从管道取出最先进去的数据；队空 → 管道里没有数据；队满（顺序队列） → 管道被数据塞满，无法再塞入。
结构
队列常见实现方式有顺序队列（数组）和链式队列（链表）。但是如果我们使用顺序结构时，我们的插入值的操作是可以很好的满足，但如果我们删除值呢？如果直接删去头部值，那样头部的空间会被空住了，浪费空间，如果数据很多的情况下那是个不小的损耗，我们如果通过整体前移动一位，那样操作，每次的时间复杂度都是O(n)。至于最好的解决方法，是构建循环队列。循环队列的整体实现较难，所以就不讲数组的结构了。
链式存储
虽然使用链表在入队尾插的时候，时间复杂度也很高，但我们可以定义一个尾结点，在进行插入时通过尾指针来实现:
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct QueueNode { type date; struct QueueNode* next; }QueueNode; typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; }Queue;讲解：
通过头指针（phead）和尾指针（ptail）分别指向队头和队尾，可以支持高效的入队（尾插）和出队（头删）操作。结构成员详解QueueNode（队列节点结构体）date：存储队列元素的数据域（类型为type，此处定义为int）。next：指向后一个节点的指针域，构建链表结构。Queue（队列管理结构体）phead：指向队列的头节点（队头），出队操作从此处移除元素。ptail：指向队列的尾节点（队尾），入队操作从此处添加元素。
二、队列实现
1.队列初始化
- 目标：将队列初始化为空队列状态，即队头（
phead）和队尾（ptail）指针均指向NULL。 - 我们可以将队列的实现简单看成链表的实现，毕竟底层用的是链表。
函数为：
void QueueInit(Queue* h);
代码：
void QueueInit(Queue* h) { assert(h); h->phead = h->ptail = NULL; }讲解：
函数功能
将链式队列初始化为空队列，即队头（phead）和队尾（ptail）指针均指向NULL。assert(h)的作用强制检查传入的队列指针h是否有效（非NULL），若为NULL则程序直接终止并报错，避免后续对空指针的非法访问（如h->phead操作）。初始化逻辑空队列的标志是phead和ptail均为NULL，表示队列中暂无任何节点。
赋值语句 h->phead = h->ptail = NULL 等价于：
h->phead = NULL; h->ptail = NULL; 所以可以以h->phead = h->ptail = NULL 形式简写。
2.入队列
- 入队操作是队列的核心功能，时间复杂度为 O(1)（仅修改指针），我们可将其实现；类比链表的尾差，不同的是，链表尾差需要先遍历到尾节点，在进行插入，我们使用队列的尾指针可以以时间复杂度为 O(1)来访问尾节点的。
图例：
函数为：
void QueuePush(Queue* h, type x);
因为插入的是节点，所以需要与链表一样写一个创建节点的函数：
创建节点的函数
QueueNode* Creat(type x)
代码：
QueueNode* Creat(type x) { QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); if (p == NULL) { printf("创建失败\n"); exit(-1); } p->date = x; p->next = NULL; return p; }讲解：
在此基础上，我们来实现下该函数：
void QueuePush(Queue* h, type x) { assert(h); QueueNode* p = Creat(x); if (h->phead == NULL) { h->phead = h->ptail = p; } else { h->ptail->next = p; h->ptail = h->ptail->next; } }代码讲解：
注：队列为空时（h->phead == NULL）：
头指针（phead）和尾指针（ptail）必须同时指向新节点p，否则后续操作会出现指针混乱（如尾指针仍为NULL）。队列非空时（核心修正点）：h->ptail->next = p：通过尾节点的next指针连接新节点，确保新节点插入队尾（而非队头）。h->ptail = h->ptail->next：等价于h->ptail = p（因ptail->next已指向p），目的是更新尾指针到新节点，保持ptail始终指向队尾。
3.队列判空
- 队列判空的本质是判断队列中是否存在有效元素，我们可以根据队列结构配合头指针和尾指针 来判断，也可以直接根据头指针的值内容来判断。
函数为：
bool QueueEmpty(Queue* h)
代码：
bool QueueEmpty(Queue* h) { assert(h); return h->phead == NULL; }讲解：
这样判断就好，省去了写if else 的代码。
4.出队列
内容为：从链式队列 h 的队头删除节点，并释放其内存。
可近似看做链表的头删。
函数为：
void QueuePop(Queue* h)
图例：
代码：
void QueuePop(Queue* h) { if (QueueEmpty(h)) { return; } if (h->phead == h->ptail) { free(h->phead); h->phead = h->ptail = NULL; } else { QueueNode* p = h->phead->next; free(h->phead); h->phead = p; } }讲解：
1.函数定义与入参void：无返回值（出队操作通常不返回元素）。Queue* h：传入队列的指针，来进行操作。
2. 空队列检查QueueEmpty(h)：调用队列判空函数。作用：若队列为空，直接返回，避免后续操作引发空指针异常（如访问h->phead->next）。
3. 单节点队列的出队处理判断条件：h->phead == h->ptail→ 队列只有1个节点（头、尾指针指向同一节点）。操作逻辑：free(h->phead)：释放唯一的节点内存（避免内存泄漏）。h->phead = h->ptail = NULL：将头、尾指针置空，标记队列为空。
4. 多节点队列的出队处理判断条件：队列有≥2个节点（头、尾指针不重合）。操作逻辑：QueueNode* p = h->phead->next：临时保存原队首节点的下一个节点（避免释放头节点后丢失后续节点的引用）。free(h->phead)：释放原队首节点的内存。h->phead = p：将头指针指向新的队首节点（即原队首的下一个节点）。
5.取队首数据
- 目标：获取队列第一个元素的值，不改变队列结构。
- 记住：操作前需先判断队列是否为空，避免“空指针”或“越界访问”错误发生。
函数为：
type QueueHead(Queue* h);
代码：
type QueueHead(Queue* h) { if (!QueueEmpty(h)) { return h->phead->date; } }讲解：
先判断队列是否为空，非空时返回队首节点的数据，函数功能简单易懂，不过多解释。
6.队列取队尾数据
- 目标：取队尾数据的核心是直接访问队列的尾节点，且需确保队列非空
函数为：
type QueueTail(Queue* h)
代码：
type QueueTail(Queue* h) { if (!QueueEmpty(h)) { return h->ptail->date; } }讲解：
先判断队列是否为空，非空时返回队尾节点的数据，函数功能简单易懂，所以也不过多解释。
7.队列值打印
- 目标：遍历队列的所有节点，依次输出每个节点的数据值。
- 注：需确保队列非空，且遍历过程不破坏队列结构。
函数为：
void QueuePrint(Queue* h);
代码：
void QueuePrint(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { printf("%d ", q->date); q = q->next; } printf("\n"); }讲解：
该函数用于打印链式队列中的所有元素，遍历顺序从队首到队尾，输出每个节点的数据值。调用QueueEmpty(h)检查队列是否为空（通常判断h->phead == NULL），若为空则直接返回，避免无效遍历。q指向队列的头节点，作为遍历的起始点（队首是第一个入队的元素）。循环中依次打印每个节点的date值，直到q为空（遍历至队尾）。
换行收尾：
printf("\n"); 遍历打印节点：
while (q) { // q不为空时继续循环 printf("%d ", q->date); // 输出当前节点的数据 q = q->next; // q移动到下一个节点 } 初始化遍历指针：
QueueNode* q = h->phead; 空队列判断：
if (QueueEmpty(h)) { return; } 8.队列的销毁
- 目标：释放队列占用的所有内存（包括队列结构体本身、节点存储空间），避免内存泄漏。
函数为：
void QueueDestory(Queue* h)
代码：
void QueueDestory(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { QueueNode* p = q; q = q->next; free(p); } h->phead = h->ptail = NULL; }讲解：
销毁链式队列，核心逻辑是遍历释放所有节点，再重置队列的头/尾指针，避免内存泄漏。空队列判断：if (QueueEmpty(h)) return;调用QueueEmpty(h)检查队列是否为空，若为空则直接返回（无需销毁操作）。初始化遍历指针：QueueNode* q = h->phead;q指向队列的头节点，作为遍历的起始点。每次循环先保存当前节点，再移动指针，最后释放节点，避免“释放后无法访问下一个节点”的问题。重置队列状态：h->phead = h->ptail = NULL;将队列的头指针phead和尾指针ptail置空，标记队列已销毁。
综上，队列代码讲解完成。
三、队列代码测试
队列代码，我是通过创建多文件来实现的：
1.h
#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct QueueNode { type date; struct QueueNode* next; }QueueNode; typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; }Queue; void QueueInit(Queue* h); void QueuePush(Queue* h, type x); QueueNode* Creat(type x); bool QueueEmpty(Queue* h); void QueuePop(Queue* h); type QueueHead(Queue* h); void QueueDestory(Queue* h); void QueuePrint(Queue* h); 1.c
#include"1.h" void QueueInit(Queue* h) { assert(h); h->phead = h->ptail = NULL; } QueueNode* Creat(type x) { QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); if (p == NULL) { printf("创建失败\n"); exit(-1); } p->date = x; p->next = NULL; return p; } void QueuePush(Queue* h, type x) { assert(h); QueueNode* p = Creat(x); if (h->phead == NULL) { h->phead = h->ptail = p; } else { h->ptail->next = p; h->ptail = h->ptail->next; } } bool QueueEmpty(Queue* h) { assert(h); return h->phead == NULL; } void QueuePop(Queue* h) { if (QueueEmpty(h)) { return; } if (h->phead == h->ptail) { free(h->phead); h->phead = h->ptail = NULL; } else { QueueNode* p = h->phead->next; free(h->phead); h->phead = p; } } type QueueHead(Queue* h) { if (!QueueEmpty(h)) { return h->phead->date; } } type QueueTail(Queue* h) { if (!QueueEmpty(h)) { return h->ptail->date; } } void QueueDestory(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { QueueNode* p = q; q = q->next; free(p); } h->phead = h->ptail = NULL; } void QueuePrint(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { printf("%d ", q->date); q = q->next; } printf("\n"); }测试函数：main.cpp
#include"1.h" void test() { Queue h; QueueInit(&h); QueuePush(&h, 100); QueuePrint(&h); //100 QueuePush(&h, 10); QueuePrint(&h); //100 10 QueuePush(&h, 0); QueuePush(&h, 20); //100 10 0 20 QueuePrint(&h); QueuePop(&h); QueuePrint(&h); //10 0 20 printf("%d ",QueueHead(&h)); printf("%d ", QueueTail(&h)); QueueDestory(&h); } int main() { test(); }结果：
总结
以上就是今天要讲的内容，本篇文章涉及的知识点为：讲解队列的概念和结构，队列的实现知识的相关内容的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，因为没有找到合适的队列题，深感抱歉，我会在以后的文章里补上。
