欢迎光临
我们一直在努力

队列(Queue)完全指南:从原理到链式实现,手把手带你避坑

队列是一种非常基础且重要的数据结构,遵循 “先进先出”(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*或使用宏,可以存储任意类型数据。

  • 循环数组队列:与链式队列相比,数组版本更节省内存(无指针开销),但需要处理边界和扩容。


  • 结语

    队列虽然结构简单,但实现细节中的边界条件(空、单节点)很容易出错。希望通过本文的详细讲解和图示,你能彻底掌握链式队列的每一个功能及其背后的陷阱。

    如果你觉得这篇文章有帮助,欢迎点赞、收藏、评论交流!

    赞(0)
    未经允许不得转载:171主机测评 » 队列(Queue)完全指南:从原理到链式实现,手把手带你避坑
    分享到: 更多 (0)

    评论 抢沙发

    • 昵称 (必填)
    • 邮箱 (必填)
    • 网址