队列先进先出的线性数据结构队列是计算机中非常基础且高频使用的线性数据结构从操作系统的任务调度、广度优先搜索到日常的消息排队、缓冲区设计底层都离不开队列的思想。本文从概念定义、结构选型到代码实现完整拆解队列的核心逻辑。一、队列的核心概念队列是一种操作受限的线性表它只允许在表的一端插入数据在另一端删除数据。执行插入操作的一端称为队尾向队列中添加元素的动作叫「入队」执行删除操作的一端称为队头从队列中移除元素的动作叫「出队」队列中的元素严格遵循先进先出 FIFOFirst In First Out的规则最早进入队列的元素会最先被取出。这和现实中排队办事的逻辑完全一致 —— 先来的人排在队头先处理新来的人只能站在队尾等待。二、队列的底层结构选型理论上数组和链表都可以用来实现队列但两者的执行效率差异很大若用数组实现入队在数组尾部追加效率很高但出队需要从数组头部删除数据后续所有元素都要整体向前挪动时间复杂度为 O (n)数据量越大效率越低。若用链表实现将队头对应链表头、队尾对应链表尾头删和尾插都可以通过指针直接完成时间复杂度稳定在 O (1)。因此在绝大多数工程实现中链表是队列更优的底层选择。三、链式队列的代码实现下面以 C 语言为例实现一个完整的链式队列包含结点定义、队列管理结构以及全部常用操作接口。1. 结构定义首先定义链表结点每个结点存储数据值和指向下一结点的指针typedef int QDataType; // 队列结点结构 typedef struct QueueNode { int val; struct QueueNode* next; } QNode;为了简化操作、提升效率我们再封装一层队列管理结构体同时保存队头指针、队尾指针和当前元素总数// 队列管理结构 typedef struct Queue { QNode* phead; QNode* ptail; int size; } Queue;2. 常用操作接口初始化队列构造一个空队列将头尾指针置空元素计数清零。void QueueInit(Queue* pq);销毁队列遍历释放所有结点内存再复位管理结构体成员避免内存泄漏。void QueueDestroy(Queue* pq);入队队尾插入创建新结点链接到当前队尾结点之后更新队尾指针元素计数 1。void QueuePush(Queue *pq, QDataType x);出队队头删除记录第二个结点的地址释放原队头结点将队头指针后移一位元素计数 -1。void QueuePop(Queue* pq);获取队头数据直接返回队头结点存储的数据值。QDataType QueueFront(Queue* pq);获取队尾数据直接返回队尾结点存储的数据值。QDataType QueueBack(Queue* pq);队列判空判断队列中是否不包含任何元素返回布尔结果。bool QueueEmpty(Queue* pq);获取队列元素个数直接返回管理结构体中记录的 size 数值。int QueueSize(Queue* pq);适用场景循环队列适合容量固定、数据频繁进出的场景比如环形缓冲区、定长消息队列、硬件数据缓存等空间一次申请后反复复用无需频繁进行内存申请与释放。完整代码giteehttps://gitee.com/yang-mianmian-1/queue