【数据结构】C语言实现队列（Queue）：链式存储与操作详解-开发者社区

文章目录

前言 🚀
一、队列的概念 💡
- 1. 什么是队列？
- 2. 队列有什么用？
二、队列的模拟实现 🛠️
- 1. 选型：数组 vs 链表？
- 2. 代码实现
- - 2.1 结构体定义
  - 2.2 初始化
  - 2.3 入队 (Push)
  - 2.4 出队 (Pop)
  - 2.5 获取队头 & 队尾数据
  - 2.6 获取长度 & 判空
  - 2.7 销毁队列
三、代码测试 💻
结语 📝

前言 🚀

哈喽各位小伙伴，欢迎回到我的数据结构系列专栏！👋

这是我们征服数据结构之路的第三站。在前两篇中，我们已经拿下了链表和栈（还没看过的同学强烈建议先补个票，基础打牢才能飞得更高哦~ 链接我放在下面啦）。
https://blog.csdn.net/S_tarfish/article/details/155815933?fromshare=blogdetail&sharetype=blogdetail&sharerId=155815933&sharerefer=PC&sharesource=S_tarfish&sharefrom=from_link
https://blog.csdn.net/S_tarfish/article/details/155418909?fromshare=blogdetail&sharetype=blogdetail&sharerId=155418909&sharerefer=PC&sharesource=S_tarfish&sharefrom=from_link

虽说前两篇的内容可能还略显青涩，但我已经在计划后续的“装修”工程了，敬请期待！😉

好了，闲话少叙，今天我们要解锁一个非常经典且常用的数据结构——队列（Queue）。准备好了吗？让我们开始吧！🚗💨

一、队列的概念 💡

1. 什么是队列？

队列（Queue）是一种特殊的线性表。
它的特殊之处在于，它对数据的访问进行了严格的限制：只允许在表的一端进行插入数据，而在另一端进行删除数据。

这就好比我们在食堂排队打饭：

入队（Push）：新来的人只能站在队尾。
出队（Pop）：只有排在队头的人才能先打到饭离开。

这种操作特性被称为FIFO (First In First Out)，即先进先出。

队尾（Rear/Back）：进行插入操作的一端。
队头（Front/Head）：进行删除操作的一端。

2. 队列有什么用？

你可能会问：“费劲限制这么多，图啥呢？” 其实，队列在计算机科学和日常生活中的应用简直不要太多：

保持公平性：这是最直观的作用。比如银行的叫号系统、医院的挂号系统、餐馆的排队小程序，本质上都是队列。先抽号的先服务，确保了公平。
广度优先遍历（BFS）：在图论和树的算法中，队列是实现 BFS 的核心辅助结构。比如 QQ/微信的“好友推荐”功能（推荐你好友的好友），或者寻找迷宫的最短路径，底层往往都要用到队列。
缓冲区：比如我们在键盘上打字，如果 CPU 忙不过来，按键信息会被暂时存在一个队列里，保证输入的顺序不会乱。

二、队列的模拟实现 🛠️

1. 选型：数组 vs 链表？

在实现队列之前，我们面临一个选择：是用数组（顺序表）还是链表来实现？

如果用数组：入队在数组尾部很简单，但出队（删除头部元素）需要将后续所有元素向前移动，时间复杂度是O(N)，效率较低。
如果用链表：
- 入队：即链表的尾插，如果我们记录了尾节点指针，复杂度是O(1)。
- 出队：即链表的头删，直接释放第一个节点即可，复杂度也是O(1)。

结论：为了追求极致的效率，我们选择使用链表来实现队列！且为了操作方便，我们需要维护一个指向队头的指针和一个指向队尾的指针。

2. 代码实现

2.1 结构体定义

为了方便管理，我们定义两个结构体：

Qnode：表示链表中的每一个节点。
Queue：用来维护队列的整体状态（头指针、尾指针、元素个数）。

#include<stdio.h>#include<stdlib.h>#include<assert.h>#include<stdbool.h>//定义队列元素的数据类型，方便后续修改typedefintQDataType;// 1. 定义队列节点的结构typedefstructQueuenode{QDataType val;structQueuenode*next;}Qnode;// 2. 定义队列本身的结构typedefstructQueue{// 把头和尾的指针封装在一起，队列只能在头尾两端操作// 这样能简化函数参数，不必每次都传递两个指针Qnode*phead;// 指向队头（用于出队）Qnode*ptail;// 指向队尾（用于入队）intsize;// 增加size成员，可以O(1)时间复杂度获取队列长度}Queue;

2.2 初始化

养成好习惯，使用前先初始化。

voidQueueInit(Queue*pq){assert(pq);// 保证传进来的结构体指针有效// 初始状态下，队列为空，头尾指针均置空pq->phead=NULL;pq->ptail=NULL;pq->size=0;}

2.3 入队 (Push)

入队操作实际上就是链表的尾插。这里需要注意处理队列为空的特殊情况。

voidQueuePush(Queue*pq,QDataType x){assert(pq);// 1. 既然是插入，首先要开辟新节点Qnode*newnode=(Qnode*)malloc(sizeof(Qnode));if(newnode==NULL){perror("malloc fail");return;}newnode->val=x;newnode->next=NULL;// 新节点将作为尾节点，next必然指向NULL// 2. 链接节点（分类讨论）// 情况A：如果你是第一个进队的元素if(pq->phead==NULL){// 此时头和尾都是你pq->phead=pq->ptail=newnode;}// 情况B：队列里已经有兄弟了else{// 旧的尾节点指向新节点pq->ptail->next=newnode;// 更新尾指针指向新的节点pq->ptail=newnode;}// 3. 别忘了计数pq->size++;}

2.4 出队 (Pop)

出队操作实际上就是链表的头删。

⚠️注意：这里有一个很容易踩的坑！当队列只剩下一个节点时，删掉它后，不仅phead要变空，ptail也要置空，否则ptail就变成野指针了。

voidQueuePop(Queue*pq){assert(pq);assert(pq->size!=0);// 队列为空时不能删除，断言报错// 1. 保存下一个节点的地址，防止丢失Qnode*next=pq->phead->next;// 2. 释放当前的头节点free(pq->phead);// 3. 更新头指针pq->phead=next;// 4. 【关键判断】如果删完后队列空了// 此时 phead 已经变成了 NULL，但 ptail 还指着刚才被 free 掉的空间if(pq->phead==NULL){pq->ptail=NULL;// 必须手动置空，防止 ptail 变成野指针}// 5. 计数减一pq->size--;}

2.5 获取队头 & 队尾数据

// 取队头数据QDataTypeQueueFront(Queue*pq){assert(pq);assert(pq->size!=0);// 队列不能为空returnpq->phead->val;}// 取队尾数据QDataTypeQueueBack(Queue*pq){assert(pq);assert(pq->size!=0);returnpq->ptail->val;}

2.6 获取长度 & 判空

因为我们在结构体中维护了size，这两个操作非常简单高效。

// 获取队列长度intQueueSize(Queue*pq){assert(pq);returnpq->size;}// 判空：size为0即为空boolEmpty(Queue*pq){assert(pq);returnpq->size==0;}

2.7 销毁队列

有始有终，申请的内存记得释放。

voidQueueDestroy(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;}

三、代码测试 💻

逻辑写得再好，跑起来才是硬道理。让我们写个main函数测试一下我们的队列是否符合“先进先出”的特性。

#include<iostream>usingnamespacestd;// 假设上面的函数声明在 queue.h 中，实现在 queue.c 中// 这里为了演示方便直接包含// #include "queue.h"intmain(){Queue q1;QueueInit(&q1);// 1. 模拟入队：1 2 3 4printf("入队顺序: 1 -> 2 -> 3 -> 4\n");QueuePush(&q1,1);QueuePush(&q1,2);QueuePush(&q1,3);QueuePush(&q1,4);printf("开始出队及获取信息:\n");// 2. 只要队列不为空，就打印队头元素并出队while(!Empty(&q1)){// 打印格式：队头元素 队尾元素 当前长度cout<<"Front:"<<QueueFront(&q1)<<" | Back:"<<QueueBack(&q1)<<" | Size:"<<QueueSize(&q1)<<endl;QueuePop(&q1);}QueueDestroy(&q1);return0;}