数据结构：队列

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

【存储中间件】Redis核心技术与实战（一）：Redis入门与应用（常用数据结构：集合set、有序集合ZSET）

【存储中间件】Redis核心技术与实战（一）：Redis入门与应用（常用数据结构：集合set、有序集合ZSET）

文章目录 * Redis入门与应用 * Redis常用数据结构 * 集合（set） * 集合内操作命令 * sadd 添加元素 * srem 删除元素 * scard 计算元素个数 * sismember 判断元素是否在集合中 * srandmember 随机从集合返回指定个数元素 * spop 从集合随机弹出元素 * smembers 获取所有元素(不会弹出元素) * 集合间操作命令 * sinter 求多个集合的交集 * suinon 求多个集合的并集 * sdiff 求多个集合的差集 * 将交集、并集、差集的结果保存 * 使用场景 * 有序集合（ZSET） * 集合内操作命令 * zadd添加成员 * zcard 计算成员个数 * zscore 计

【Docker/Redis】服务端高并发分布式结构演进之路

目录 概述 常见概念 基本概念 应用（Application）/ 系统（System） 模块（Module）/ 组件（Component） 分布式（Distributed） 集群（Cluster） 分布式vs 集群。 主（Master）/ 从（Slave） 中间件（Middleware） 容器（Docker） 容器编排（K8S） 评价指标（Metric） 可用性（Availability） 响应时长（Response Time RT） 吞吐（Throughput）vs 并发（Concurrent） 架构演进 单机架构 出现原因 简介 技术案例 架构优缺点 相关软件 应用数据分离架构 出现原因
【MySQL数据库基础】（四）MySQL 表的操作通关指南：创建 / 修改 / 删除一网打尽

【MySQL数据库基础】（四）MySQL 表的操作通关指南：创建 / 修改 / 删除一网打尽

前言         上一篇我们讲了 MySQL 库的核心操作，作为 MySQL 数据存储的核心载体，数据表的操作更是开发和运维中的高频操作。从表的创建、结构设计，到日常的字段增删改、表名修改，再到最后的表删除，每一步都有对应的语法和实操细节，稍不注意就可能踩坑（比如误删字段导致数据丢失）。         这篇文章就基于 MySQL 实战场景，把表的全套操作讲透，从创建表的核心语法、存储引擎的差异，到修改表的各种场景，再到删除表的高危操作注意事项，让你一文掌握 MySQL 表操作的所有精髓，新手也能快速上手！下面就让我们正式开始吧！ 一、创建表：打好基础，定好结构         创建数据表是表操作的第一步，也是最关键的一步 —— 表的结构设计直接决定了后续数据存储的效率和扩展性。MySQL 中创建表的语法支持自定义字段、字段类型、字符集、校验规则和存储引擎，灵活度拉满。 1. 核心创建语法         MySQL 创建表的官方标准语法如下，关键字和可选项的设计和库操作一脉相承，理解起来非常容易： CREATE TABLE
Flutter for OpenHarmony: Flutter 三方库 ferry 在鸿蒙应用中构建高性能类型安全的 GraphQL 通讯架构（现代 API 调用方案）

Flutter for OpenHarmony: Flutter 三方库 ferry 在鸿蒙应用中构建高性能类型安全的 GraphQL 通讯架构（现代 API 调用方案）

欢迎加入开源鸿蒙跨平台社区：https://openharmonycrossplatform.ZEEKLOG.net 前言 随着后端架构的演进，越来越多的 OpenHarmony 项目开始采用 GraphQL 替代传统的 RESTful API。GraphQL 的优势在于“按需取值”，能有效减少冗余数据的传输，这对于追求极致性能的鸿蒙应用尤为重要。然而，手动拼接 GraphQL 字符串、解析动态 Map 依然是繁琐且易错的。 ferry 是一套为 Flutter 量身定制的 GraphQL 客户端全家桶。它通过深度集成代码生成器（Code Generation），让你的鸿蒙应用能以“强类型”方式操作查询。它不仅支持请求与变动，更内置了极致的规范化缓存（Normalized Cache）系统，是构建专业级鸿蒙 GraphQL 应用的终极武器。 一、类型全链路通讯架构 ferry 在本地定义与远程数据之间建立了强类型的映射隧道。