队列是一种非常基础且重要的数据结构,遵循 “先进先出”(FIFO,First In First Out) 的原则。就像现实生活中的排队:先来的人先服务,后来的人排在队尾。
本文将基于 链式存储结构 的队列实现(C语言),详细讲解每一个功能的实现细节、边界条件以及常见的“坑”。代码已经过测试,你可以直接复制使用。
一、队列的基本概念
-
队头(Front):允许删除元素的一端。
-
队尾(Rear):允许插入元素的一端。
-
核心操作:
-
入队(Push):在队尾插入元素。
-
出队(Pop):删除队头元素。
-
取队头/队尾元素(Front/Back)。
-
判空、求大小、销毁。
-
为什么用链式结构而不是数组?
数组实现的循环队列需要预分配空间,存在“假溢出”或扩容问题。链式队列动态分配节点,理论上不受空间限制,实现更直观。
二、数据结构定义(Queue.h)
我们先看看头文件中定义了哪些结构体和函数接口。
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int QDataType;
// 队列结点的结构
typedef struct QueueNode
{
QDataType data;
struct QueueNode* next;
} QueueNode;
// 队列的结构(持有头尾指针)
typedef struct Queue
{
QueueNode* phead; // 队头指针
QueueNode* ptail; // 队尾指针
// int size; // 队列中有效数据个数(可选,后面会讲)
} Queue;
// 函数声明
void QueueInit(Queue* pq);
void QueueDestroy(Queue* pq);
void QueuePush(Queue* pq, QDataType x);
void QueuePop(Queue* pq);
bool QueueEmpty(Queue* pq);
int QueueSize(Queue* pq);
QDataType QueueFront(Queue* pq);
QDataType QueueBack(Queue* pq);
关键点:
-
队列结构体中只维护了phead和ptail,没有维护size。后续在QueueSize函数中通过遍历链表来计算大小,这是一个“坑”点,我们会在后面详细分析。
-
使用typedef int QDataType方便修改队列元素类型。
三、队列的图形化表示
为了方便理解,我们用ASCII画一个包含3个元素{1, 2, 3}的队列:
队头 (phead) 队尾 (ptail)
↓ ↓
┌───────┐ ┌───────┐ ┌───────┐
│ data=1│ → │ data=2│ → │ data=3│ → NULL
│ next │ │ next │ │ next │
└───────┘ └───────┘ └───────┘
空队列时:phead = ptail = NULL。
四、每个功能的详细实现与解析
1. 初始化 QueueInit
void QueueInit(Queue* pq)
{
assert(pq);
pq->phead = pq->ptail = NULL;
// pq->size = 0; // 如果使用size字段,这里要置0
}
作用:将传入的队列结构体指针pq的头尾指针都置为NULL,表示空队列。
注意:
-
必须断言pq不为空,否则对空指针赋值会崩溃。
-
如果将来启用了size成员,这里也要初始化为0。
2. 销毁队列 QueueDestroy
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;
// pq->size = 0;
}
作用:释放队列中所有动态分配的节点内存,并将头尾指针置空,防止野指针。
图形化过程(销毁含3个节点的队列):
初始:pcur指向节点1 → 保存next=节点2 → free(节点1) → pcur=节点2
重复直到pcur为NULL
最后:phead=ptail=NULL
坑点:
-
必须用临时变量next保存下一个节点,否则free(pcur)后无法访问pcur->next。
-
销毁后记得将pq->phead和pq->ptail置为NULL,否则这些指针变成“悬空指针”,再次使用会导致未定义行为。
3. 入队(队尾插入)QueuePush
void QueuePush(Queue* pq, QDataType x)
{
assert(pq);
QueueNode* newnode = (QueueNode*)malloc(sizeof(QueueNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = NULL;
// 队列为空
if (pq->phead == NULL)
{
pq->phead = pq->ptail = newnode;
}
else
{
// 队列非空:链接新节点到当前队尾后面,然后更新ptail
pq->ptail->next = newnode;
pq->ptail = newnode; // 等价于 pq->ptail = pq->ptail->next;
}
// pq->size++;
}
步骤图解(向{1,2}的队列中插入3):
插入前:
phead → [1|next] → [2|next] → NULL
↑
ptail
插入过程:
1. 创建新节点 [3|NULL]
2. ptail->next = 新节点 → 原节点2的next指向节点3
3. ptail = 新节点 → 队尾指针指向节点3
插入后:
phead → [1|next] → [2|next] → [3|NULL]
↑
ptail
坑点:
-
忘记处理空队列的情况:如果队列为空,直接将phead和ptail指向新节点。如果只写pq->ptail->next = newnode,此时pq->ptail为NULL,会崩溃。
-
malloc可能失败,必须检查返回值并处理错误。
-
新节点的next必须初始化为NULL。
4. 判空 QueueEmpty
bool QueueEmpty(Queue* pq)
{
assert(pq);
return pq->phead == NULL;
}
非常简单,但断言pq非空是必要的。
5. 出队(删除队头)QueuePop
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;
}
// pq->size–;
}
图解出队(从{1,2,3}中弹出队头1):
出队前:
phead → [1|next] → [2|next] → [3|NULL] ← ptail
步骤(非单节点情况):
1. next = phead->next → 指向节点2
2. free(phead) → 释放节点1
3. phead = next → 队头指向节点2
出队后:
phead → [2|next] → [3|NULL] ← ptail
特别处理单节点:
如果phead == ptail,说明只有一个节点。此时如果只执行else分支:next = phead->next得到NULL,然后free(phead),再phead = next变为NULL,但ptail仍然指向已被释放的节点,成为野指针!所以必须单独判断,将ptail也置NULL。
坑点:
-
单节点情况必须单独处理,否则ptail悬空。
-
出队前必须判空,不能对空队列执行QueuePop。
-
别忘了释放被删除节点的内存。
6. 取队头元素 QueueFront
QDataType QueueFront(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->phead->data;
}
很简单,注意判空即可。
7. 取队尾元素 QueueBack
QDataType QueueBack(Queue* pq)
{
assert(!QueueEmpty(pq));
return pq->ptail->data;
}
同样需要判空。
8. 求队列有效元素个数 QueueSize
有两种方式,目前使用的是遍历法:
int QueueSize(Queue* pq)
{
assert(pq);
QueueNode* pcur = pq->phead;
int size = 0;
while (pcur)
{
size++;
pcur = pcur->next;
}
return size;
}
第二种方式:直接返回结构体中的size成员,但当前结构体没有定义size。
这是一个重要的设计取舍:
| 遍历链表 | 不占用额外空间 | 时间复杂度O(n),频繁调用效率低 | 不常需要获取大小的场景 |
| 维护size成员 | O(1)获取大小 | 每次入队/出队需同步修改size,增加代码量 | 频繁调用QueueSize的场景 |
坑点:
-
如果使用遍历法,在需要频繁获取大小(比如循环条件中)时会造成性能浪费。
-
如果选择维护size,务必在QueueInit中初始化为0,在QueuePush中size++,在QueuePop中size–。千万不要忘记同步!
9. 测试代码与输出
void test01()
{
Queue q;
QueueInit(&q);
QueuePush(&q, 1);
QueuePush(&q, 2);
QueuePush(&q, 3);
// QueuePop(&q); // 取消注释可以测试出队
int front = QueueFront(&q);
int rear = QueueBack(&q);
printf("front:%d\\n", front);
printf("rear:%d\\n", rear);
printf("size:%d", QueueSize(&q));
QueueDestroy(&q);
}
int main()
{
test01();
return 0;
}
输出:
front:1
rear:3
size:3
五、常见坑点总结(必看!)
空队列的入队:必须单独处理phead==NULL的情况,让phead和ptail都指向新节点。
单节点的出队:必须单独判断phead == ptail,否则ptail成为野指针。
传参合法性:几乎所有函数都要assert(pq),防止传入空指针。
内存管理:
-
每个malloc都要配对free,使用QueueDestroy释放所有节点。
-
销毁后要将头尾指针置NULL,避免二次释放。
遍历计算size:如果频繁调用,建议改用size成员,用空间换时间。
队列判空:出队、取队头/队尾前必须用QueueEmpty检查,否则对空链表解引用会崩溃。
六、完整代码清单
你可以将以下三个文件放在同一目录下编译运行:
-
Queue.h(见第二节)
-
Queue.c(见第四节各函数实现,注意包含头文件)
-
test.c(见测试代码)
编译命令(gcc):
gcc test.c Queue.c -o queue_test
七、扩展思考
线程安全:上述代码不是线程安全的。多线程环境下需要加锁(如互斥量)保护队列操作。
泛型:通过将QDataType改为void*或使用宏,可以存储任意类型数据。
循环数组队列:与链式队列相比,数组版本更节省内存(无指针开销),但需要处理边界和扩容。
结语
队列虽然结构简单,但实现细节中的边界条件(空、单节点)很容易出错。希望通过本文的详细讲解和图示,你能彻底掌握链式队列的每一个功能及其背后的陷阱。
如果你觉得这篇文章有帮助,欢迎点赞、收藏、评论交流!


![P11246 [GESP202409 六级] 小杨和整数拆分-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108100631-6af049a75855c-220x150.png)
![打卡信奥刷题(3678)用C++实现信奥题 P12274 [蓝桥杯 2024 国 Python B] 设计-171主机测评](https://www.171host.com/wp-content/uploads/2026/11/20261108053830-6af00ad6bdf8d-220x150.png)
