数据结构：队列

Ne0inhk

— 12 min read
数据结构：队列

前言 

本篇文章将讲解队列的概念和结构，队列的实现等知识的相关内容，本章代码实现的知识，与单向链表相关，所以如果还没看过单向链表文章，可以看看：

https://blog.ZEEKLOG.net/2401_86982201/article/details/154615762?fromshare=blogdetail&sharetype=blogdetail&sharerId=154615762&sharerefer=PC&sharesource=2401_86982201&sharefrom=from_link

一、队列概念与结构

概念

与栈的数据结构类似，队列：只允许在⼀端进⾏插⼊数据操作，在另⼀端进⾏删除数据操作的特殊线性表，队列具有先进先出FIFO(First In First Out)特性。

入队列：进行插入操作的一端称为队尾。

出队列：进行删除操作的一端称为队头。

图示：

我们可以将其类比成“单向管道”，数据从管道的一端（队尾）进入，只能从另一端（队头）按顺序流出，中间无法插队或删除中间元素，正好契合了他的“先进先出（FIFO）”的特性。

即：

入队（Enqueue） → 向管道塞入数据；出队（Dequeue） → 从管道取出最先进去的数据；队空 → 管道里没有数据；队满（顺序队列） → 管道被数据塞满，无法再塞入。

结构

  队列常见实现方式有顺序队列（数组）和链式队列（链表）。但是如果我们使用顺序结构时，我们的插入值的操作是可以很好的满足，但如果我们删除值呢？如果直接删去头部值，那样头部的空间会被空住了，浪费空间，如果数据很多的情况下那是个不小的损耗，我们如果通过整体前移动一位，那样操作，每次的时间复杂度都是O(n)。至于最好的解决方法，是构建循环队列。循环队列的整体实现较难，所以就不讲数组的结构了。

链式存储

  虽然使用链表在入队尾插的时候，时间复杂度也很高，但我们可以定义一个尾结点，在进行插入时通过尾指针来实现:

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct QueueNode { type date; struct QueueNode* next; }QueueNode; typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; }Queue;

讲解：

通过头指针（phead）和尾指针（ptail）分别指向队头和队尾，可以支持高效的入队（尾插）和出队（头删）操作。结构成员详解QueueNode（队列节点结构体）date：存储队列元素的数据域（类型为 type，此处定义为 int）。next：指向后一个节点的指针域，构建链表结构。Queue（队列管理结构体）phead：指向队列的头节点（队头），出队操作从此处移除元素。ptail：指向队列的尾节点（队尾），入队操作从此处添加元素。

二、队列实现

1.队列初始化

  • 目标：将队列初始化为空队列状态，即队头（phead）和队尾（ptail）指针均指向 NULL。
  • 我们可以将队列的实现简单看成链表的实现，毕竟底层用的是链表。

函数为：

void QueueInit(Queue* h);

代码：

void QueueInit(Queue* h) { assert(h); h->phead = h->ptail = NULL; }

讲解：

函数功能

将链式队列初始化为空队列，即队头（phead）和队尾（ptail）指针均指向 NULL。

assert(h) 的作用强制检查传入的队列指针 h 是否有效（非 NULL），若为 NULL 则程序直接终止并报错，避免后续对空指针的非法访问（如 h->phead 操作）。初始化逻辑空队列的标志是 phead 和 ptail 均为 NULL，表示队列中暂无任何节点。

赋值语句 h->phead = h->ptail = NULL 等价于：

h->phead = NULL; h->ptail = NULL;

所以可以以h->phead = h->ptail = NULL 形式简写。

 2.入队列

  • 入队操作是队列的核心功能，时间复杂度为 O(1)（仅修改指针），我们可将其实现；类比链表的尾差，不同的是，链表尾差需要先遍历到尾节点，在进行插入，我们使用队列的尾指针可以以时间复杂度为 O(1)来访问尾节点的。

图例：

函数为：

void QueuePush(Queue* h, type x);

因为插入的是节点，所以需要与链表一样写一个创建节点的函数：

创建节点的函数

QueueNode* Creat(type x)

代码：

QueueNode* Creat(type x) { QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); if (p == NULL) { printf("创建失败\n"); exit(-1); } p->date = x; p->next = NULL; return p; }

讲解：

在此基础上，我们来实现下该函数：

void QueuePush(Queue* h, type x) { assert(h); QueueNode* p = Creat(x); if (h->phead == NULL) { h->phead = h->ptail = p; } else { h->ptail->next = p; h->ptail = h->ptail->next; } }

代码讲解：



注：队列为空时（h->phead == NULL）：
头指针（phead）和尾指针（ptail）必须同时指向新节点 p，否则后续操作会出现指针混乱（如尾指针仍为 NULL）。队列非空时（核心修正点）：h->ptail->next = p：通过尾节点的 next 指针连接新节点，确保新节点插入队尾（而非队头）。h->ptail = h->ptail->next：等价于 h->ptail = p（因 ptail->next 已指向 p），目的是更新尾指针到新节点，保持 ptail 始终指向队尾。

  3.队列判空

  • 队列判空的本质是判断队列中是否存在有效元素，我们可以根据队列结构配合头指针和尾指针 来判断，也可以直接根据头指针的值内容来判断。

函数为：

bool QueueEmpty(Queue* h)

代码：

bool QueueEmpty(Queue* h) { assert(h); return h->phead == NULL; }

讲解：



这样判断就好，省去了写if else 的代码。

 4.出队列

内容为：从链式队列 h 的队头删除节点，并释放其内存。

可近似看做链表的头删。

函数为：

void QueuePop(Queue* h)

图例：

代码：

void QueuePop(Queue* h) { if (QueueEmpty(h)) { return; } if (h->phead == h->ptail) { free(h->phead); h->phead = h->ptail = NULL; } else { QueueNode* p = h->phead->next; free(h->phead); h->phead = p; } }

讲解：

1.函数定义与入参void：无返回值（出队操作通常不返回元素）。Queue* h：传入队列的指针，来进行操作。

2. 空队列检查QueueEmpty(h)：调用队列判空函数。作用：若队列为空，直接返回，避免后续操作引发空指针异常（如访问h->phead->next）。

3. 单节点队列的出队处理判断条件：h->phead == h->ptail → 队列只有1个节点（头、尾指针指向同一节点）。操作逻辑：free(h->phead)：释放唯一的节点内存（避免内存泄漏）。h->phead = h->ptail = NULL：将头、尾指针置空，标记队列为空。

4. 多节点队列的出队处理判断条件：队列有≥2个节点（头、尾指针不重合）。操作逻辑：QueueNode* p = h->phead->next：临时保存原队首节点的下一个节点（避免释放头节点后丢失后续节点的引用）。free(h->phead)：释放原队首节点的内存。h->phead = p：将头指针指向新的队首节点（即原队首的下一个节点）。

 5.取队首数据

  • 目标：获取队列第一个元素的值，不改变队列结构。
  • 记住：操作前需先判断队列是否为空，避免“空指针”或“越界访问”错误发生。

函数为：

type QueueHead(Queue* h);

代码：

type QueueHead(Queue* h) { if (!QueueEmpty(h)) { return h->phead->date; } }

讲解：

先判断队列是否为空，非空时返回队首节点的数据，函数功能简单易懂，不过多解释。

 6.队列取队尾数据

  • 目标：取队尾数据的核心是直接访问队列的尾节点，且需确保队列非空

函数为：

type QueueTail(Queue* h)

代码：

type QueueTail(Queue* h) { if (!QueueEmpty(h)) { return h->ptail->date; } }

讲解：

先判断队列是否为空，非空时返回队尾节点的数据，函数功能简单易懂，所以也不过多解释。

7.队列值打印

  • 目标：遍历队列的所有节点，依次输出每个节点的数据值。
  • 注：需确保队列非空，且遍历过程不破坏队列结构。

函数为：

void QueuePrint(Queue* h);

代码：

void QueuePrint(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { printf("%d ", q->date); q = q->next; } printf("\n"); }

讲解：

该函数用于打印链式队列中的所有元素，遍历顺序从队首到队尾，输出每个节点的数据值。调用QueueEmpty(h)检查队列是否为空（通常判断h->phead == NULL），若为空则直接返回，避免无效遍历。q指向队列的头节点，作为遍历的起始点（队首是第一个入队的元素）。循环中依次打印每个节点的date值，直到q为空（遍历至队尾）。

换行收尾：

printf("\n");

遍历打印节点：

while (q) { // q不为空时继续循环 printf("%d ", q->date); // 输出当前节点的数据 q = q->next; // q移动到下一个节点 }

初始化遍历指针：

QueueNode* q = h->phead;

空队列判断：

if (QueueEmpty(h)) { return; }

 8.队列的销毁

  • 目标：释放队列占用的所有内存（包括队列结构体本身、节点存储空间），避免内存泄漏。

函数为：

void QueueDestory(Queue* h)

代码：

void QueueDestory(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { QueueNode* p = q; q = q->next; free(p); } h->phead = h->ptail = NULL; }

讲解：

销毁链式队列，核心逻辑是遍历释放所有节点，再重置队列的头/尾指针，避免内存泄漏。空队列判断：if (QueueEmpty(h)) return;调用QueueEmpty(h)检查队列是否为空，若为空则直接返回（无需销毁操作）。初始化遍历指针：QueueNode* q = h->phead;q指向队列的头节点，作为遍历的起始点。每次循环先保存当前节点，再移动指针，最后释放节点，避免“释放后无法访问下一个节点”的问题。重置队列状态：h->phead = h->ptail = NULL;将队列的头指针phead和尾指针ptail置空，标记队列已销毁。

综上，队列代码讲解完成。

三、队列代码测试

队列代码，我是通过创建多文件来实现的：

1.h

#include<stdio.h> #include<stdlib.h> #include<assert.h> typedef int type; typedef struct QueueNode { type date; struct QueueNode* next; }QueueNode; typedef struct Queue { struct QueueNode* phead; struct QueueNode* ptail; }Queue; void QueueInit(Queue* h); void QueuePush(Queue* h, type x); QueueNode* Creat(type x); bool QueueEmpty(Queue* h); void QueuePop(Queue* h); type QueueHead(Queue* h); void QueueDestory(Queue* h); void QueuePrint(Queue* h);

1.c

#include"1.h" void QueueInit(Queue* h) { assert(h); h->phead = h->ptail = NULL; } QueueNode* Creat(type x) { QueueNode* p = (QueueNode*)malloc(sizeof(QueueNode)); if (p == NULL) { printf("创建失败\n"); exit(-1); } p->date = x; p->next = NULL; return p; } void QueuePush(Queue* h, type x) { assert(h); QueueNode* p = Creat(x); if (h->phead == NULL) { h->phead = h->ptail = p; } else { h->ptail->next = p; h->ptail = h->ptail->next; } } bool QueueEmpty(Queue* h) { assert(h); return h->phead == NULL; } void QueuePop(Queue* h) { if (QueueEmpty(h)) { return; } if (h->phead == h->ptail) { free(h->phead); h->phead = h->ptail = NULL; } else { QueueNode* p = h->phead->next; free(h->phead); h->phead = p; } } type QueueHead(Queue* h) { if (!QueueEmpty(h)) { return h->phead->date; } } type QueueTail(Queue* h) { if (!QueueEmpty(h)) { return h->ptail->date; } } void QueueDestory(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { QueueNode* p = q; q = q->next; free(p); } h->phead = h->ptail = NULL; } void QueuePrint(Queue* h) { if (QueueEmpty(h)) { return; } QueueNode* q = h->phead; while (q) { printf("%d ", q->date); q = q->next; } printf("\n"); }

测试函数：main.cpp

#include"1.h" void test() { Queue h; QueueInit(&h); QueuePush(&h, 100); QueuePrint(&h); //100 QueuePush(&h, 10); QueuePrint(&h); //100 10 QueuePush(&h, 0); QueuePush(&h, 20); //100 10 0 20 QueuePrint(&h); QueuePop(&h); QueuePrint(&h); //10 0 20 printf("%d ",QueueHead(&h)); printf("%d ", QueueTail(&h)); QueueDestory(&h); } int main() { test(); }

结果：

  总结

  以上就是今天要讲的内容，本篇文章涉及的知识点为：讲解队列的概念和结构，队列的实现知识的相关内容的相关内容，为本章节知识的内容，希望大家能喜欢我的文章，谢谢各位，因为没有找到合适的队列题，深感抱歉，我会在以后的文章里补上。

Read more

★ 算法OJ题 ★ 前缀和算法（上）

★ 算法OJ题 ★ 前缀和算法（上）

Ciallo～(∠・ω< )⌒☆ ~ 今天，将和大家一起做几道前缀和算法题 ~ ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 澄岚主页：椎名澄嵐-ZEEKLOG博客 算法专栏：★ 优选算法100天 ★_椎名澄嵐的博客-ZEEKLOG博客 ❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️❄️ 目录 壹  【模板】一维前缀和 1.1 题目 1.2 算法解析 1.3 撰写代码 贰  【模板】二维前缀和 2.1 题目 2.2 算法解析 2.3 撰写代码 叁  寻找数组的中心下标 3.1 题目 3.2 算法解析 3.3 撰写代码 肆  除自身以外数组的乘积 4.1

By Ne0inhk
无中生有——无监督学习的原理、算法与结构发现

无中生有——无监督学习的原理、算法与结构发现

“世界上绝大多数数据都没有标签。 真正的智能，不是在已知答案中选择，而是在混沌中发现秩序。” ——无监督学习的哲学 一、为什么需要无监督学习？ 在前七章中，我们系统学习了监督学习（Supervised Learning）的核心范式：给定输入 x\mathbf{x}x 和对应标签 yyy，学习映射 f:x↦yf: \mathbf{x} \mapsto yf:x↦y。无论是线性回归、决策树，还是神经网络，都依赖于标注数据这一稀缺资源。 然而，现实世界的数据绝大多数是未标注的： * 用户浏览日志（只有行为，没有“好/坏”标签）； * 医学影像（只有图像，没有诊断结论）； * 社交网络（只有连接关系，没有群体划分）； * 传感器时序（只有数值流，没有异常标记）

By Ne0inhk
【 C/C++ 算法】入门动态规划-----路径问题（以练代学式）

【 C/C++ 算法】入门动态规划-----路径问题（以练代学式）

>每日激励：“不设限和自我肯定的心态：I can do all things。 — Stephen Curry” 绪论 ： 本章是动态规划的第二篇，本章将开始二维的动态规划，在二维中的动态规划本质和一维的分析来说差不太多，只不过状态表示从一维变成了二维，而在二维上所能管理的状态就从一维的两个变成了二维的三个，也就是x轴，y轴，数组中的值。若没看了解过动规算法，我强烈建议先看第一篇blog，因为当你看完第一篇你就对动规基本认识了，其中也就能认识到它的五步骤分析法，这里也就不扩充说明而是直接使用了 ———————— 早关注不迷路，话不多说安全带系好，发车啦（建议电脑观看）。 路径问题🛣️ 本章主要还是在二维数组中的进行的动态规划： 同样还是五步走：状态表示、状态方程、初始化、移动方向、返回结果 1. 其中在二维中状态表示就会和一位略有不同，不同本质一样： 从以 i 结尾.，… ==》从左上角到达 i j 位置，… 1. 当然在最后一题中发现上面这种常规方法实现不通，因为状态方程会受后面状态影响 2.

By Ne0inhk
Flutter 三方库 collection 的鸿蒙化适配指南 - 实现具备高级集合操作与相等性深度判定算法的算法底座、支持端侧多维数据结构的高性能治理实战

Flutter 三方库 collection 的鸿蒙化适配指南 - 实现具备高级集合操作与相等性深度判定算法的算法底座、支持端侧多维数据结构的高性能治理实战

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net Flutter 三方库 collection 的鸿蒙化适配指南 - 实现具备高级集合操作与相等性深度判定算法的算法底座、支持端侧多维数据结构的高性能治理实战 前言 在进行 Flutter for OpenHarmony 开发时，面对复杂的业务 JSON 转化、深层嵌套的集合对比或需要对列表执行高频的优先级排序（Priority Queue）时，原生 List 和 Map 的功能往往显得捉襟见肘。collection 是 Dart 官方维护的最权威、最核心的集合工具库。本文将探讨如何在鸿蒙端构建极致、稳健的数据处理架构。 一、原直观解析 / 概念介绍 1.1 基础原理 该库扩展了 Dart 标准库中的集合能力。它不仅提供了如 Equality（深度相等判定）、PriorityQueue（

By Ne0inhk