news 2026/4/23 18:35:14

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

作者头像

张小明

前端开发工程师

1.2k 24
文章封面图
【数据结构】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. 队列有什么用？

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

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

二、队列的模拟实现 🛠️

1. 选型：数组 vs 链表？

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

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

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

2. 代码实现

2.1 结构体定义

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

  1. Qnode：表示链表中的每一个节点。
  2. 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;}

运行结果如下：

结果分析：
我们可以清晰地看到：

  • 第一行Front是 1，Size是 4。
  • Pop一次后，第二行Front变成了 2，Size变成了 3。
  • 这完美验证了队列FIFO（先进先出）的特性。

结语 📝

到这里，关于队列的基础知识和链式实现就讲完啦！相比于顺序表，队列在特定场景下的作用不可替代。

如果你觉得这篇文章对你有帮助，不妨点个赞👍支持一下，这对我通过持续输出高质量内容非常重要！后续我会更新更复杂的二叉树等内容，关注不迷路哦~

我们下期见！👋

版权声明: 本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若内容造成侵权/违法违规/事实不符，请联系邮箱：809451989@qq.com进行投诉反馈，一经查实，立即删除！
网站建设 2026/4/23 5:03:00

CUDA安装版本与TensorRT兼容性对照表（2024最新）

CUDA与TensorRT版本兼容性深度指南&#xff08;2024&#xff09; 在当今AI系统部署的实战中&#xff0c;一个看似简单却频频引发生产事故的问题是&#xff1a;为什么模型在开发环境跑得好好的&#xff0c;一到服务器上就加载失败&#xff1f; 答案往往藏在CUDA和TensorRT的版本…

作者头像 李华
网站建设 2026/4/23 10:46:56

【2-64G云服务器盘点】持续更新，2025年汇总大厂云服务器对比选择

写作初衷&#xff1a; 作为一个购买多年云服务器经历的爱好者&#xff0c;最喜欢看各厂商的优惠活动&#xff0c;反复比较各厂商的优惠&#xff0c;找到最具性价比的那一款。 我就像一个互联网的猹&#xff0c;在京东云、阿里云、腾讯云的官网里反复对比、反复横跳&#xff0c;…

作者头像 李华
网站建设 2026/4/23 13:35:53

纪念币预约自动化工具使用指南

纪念币预约自动化工具使用指南 【免费下载链接】auto_commemorative_coin_booking 项目地址: https://gitcode.com/gh_mirrors/au/auto_commemorative_coin_booking 一、工具核心价值 纪念币预约自动化工具是一款基于Python开发的智能脚本&#xff0c;专门帮助用户自动…

作者头像 李华
网站建设 2026/4/23 15:01:34

中国行政区划数据快速入门指南：从零基础到实战应用的5个关键步骤

想要在项目中快速集成中国行政区划数据&#xff1f;ChinaAdminDivisonSHP项目为你提供了完整的分层地理数据解决方案。这个开源项目采用ESRI Shapefile格式&#xff0c;覆盖国家、省、市、区县四级行政边界&#xff0c;是开发地图应用、数据分析项目的理想资源库。 【免费下载链…

作者头像 李华
网站建设 2026/4/23 13:30:18

C语言笔记归纳19：动态内存管理

动态内存管理 目录 动态内存管理 1. &#x1f31f; 为什么需要动态内存管理&#xff1f;&#xff08;普通内存的痛点&#xff09; 2. &#x1f4cc; 程序内存区域划分&#xff08;栈 / 堆 / 静态区 / 代码段&#xff09; 3. &#x1f6e0;️ 四大核心函数详解&#xff08;…

作者头像 李华