手撕数据结构 —— 队列(C语言讲解)
目录
1.什么是队列
2.如何实现队列
3.队列的实现
Queue.h中接口总览
具体实现
结构的定义
初始化
销毁
入队列
出队列
取队头元素
取队尾元素
判断是否为空
获取队列的大小
4.完整代码附录
Queue.h
Queue.c
1.什么是队列
队列是一种特殊的线性表,只允许在一端进行数据的插入操作,在另一端进行数据的删除操作。队列中的数据元素必须满足先进先出的性质。
- 插入数据的操作叫做入队列,插入数据的一端叫做队尾。
- 删除数据的操作叫做出队列,删除数据的一端叫做队头。
队列逻辑结构如下图所示:

2.如何实现队列
要想实现队列,必须满足队列的要求,也就是以下两点:
- a、在一端插入数据,在另一端删除数据。
- b、满足先进先出的性质。
所以,我们使用数组(顺序表)或者 链表实现,那么使用哪种结构来实现更好呢?
我们可以对比一下:
| 数组(顺序表) | 链表(单链表) | |
| 头插效率 | O(N) | O(1) |
| 头删效率 | O(N) | O(1) |
| 尾插效率 | O(1) | O(N) |
| 尾删效率 | O(1) | O(N) |
貌似使用数组和链表实现都是一样的,在一端进行插入or删除的效率是O(1),在另一端进行删除or插入的效率就是O(N) 。
但是我们可以优化一下链表,链表在尾部进行插入or删除的效率之所以是O(N),是因为需要遍历链表找尾结点,但是,如果我们能够直接找到尾结点,那么链表在尾部进行插入和删除的效率不就都是O(1)了吗?
所以,我们可以使用两个指针head和tail分别指向链表的头结点和尾结点。这样一来,进行尾插时,直接就能找到尾结点,所以尾插的效率也是O(1)。

所以我们实现的队列的最终形态如下:

3.队列的实现
队列的实现,我们主要实现Queue.h和Queue.c文件即可,Queue.h文件中存放声明,Queue.c文件中存放定义。
Queue.h中接口总览

具体实现
结构的定义
实现队列结构的时候,由于我们采用的是链表来实现队列,所以我们需要定义一个个的结点;前面我们分析可知,head指向头结点,tail指向尾结点,可以使得入队列和出队列的时间复杂度都为O(1),所以我们需要管理好head指针和tail指针,这里我们也采用结构体来管理。


初始化
初始化队列只需要初始化 struct Queue 结构体对象中的成员即可。
- head和tail指针都初始化为空。
- size初始化为0。
销毁
销毁队列的时候,首先需要将节点全部释放,然后将head和tail指针置空,并将size置为0。

入队列
入队列的时候要区分两种情况:
- 入队列的结点是第一个结点,此时让head和tail同时指向该结点即可。
- 入队列的结点不是第一个结点,此时让新结点连接到尾结点的后面即可。
- 最后记得将size++。


出队列
出队列的时候要区分三种情况:
- 队列不能为空。
- 只有一个结点的情况。此时,释放结点之后,将head和tail指针置空。
- 不止一个结点的情况。此时,记录head指向的结点,将head后移,然后释放记录的节点。
注意:最后记得将size--。

取队头元素
直接返回head指向的结点的数据即可。

取队尾元素
直接返回tail指向的结点的数据即可。

判断是否为空
当队列为空时,head和tail都指向空,所以直接判断head或者tail是否为空都可以。

获取队列的大小
直接返回struct Queue结构体类型对象中的size即可。

4.完整代码附录
Queue.h
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int QDataType;
typedef struct QueueNode // 定义结点
{struct QueueNode* next; // 存储下一个结点的地址 QDataType data; // 存储数据
}QNode;typedef struct Queue // 定义队列
{QNode* head; // 指向头结点 QNode* tail; // 指向尾结点 int size; // 记录队列的大小
}Que;// 初始化
void QueueInit(Que* pq);
// 销毁
void QueueDestroy(Que* pq);
// 入队列
void QueuePush(Que* pq, QDataType x);
// 出队列
void QueuePop(Que* pq);
// 取队头元素
QDataType QueueFront(Que* pq);
// 取队尾元素
QDataType QueueBack(Que* pq);
// 判断是否为空
bool QueueEmpty(Que* pq);
// 获取队列的大小
int QueueSize(Que* pq);
Queue.c
// 初始化队列
void QueueInit(Que* pq)
{assert(pq);pq->head = pq->tail = NULL;pq->size = 0;
}// 销毁队列
void QueueDestroy(Que* pq)
{assert(pq);QNode* cur = pq->head;while (cur) // 遍历释放结点 {QNode* next = cur->next;free(cur);cur = next;}pq->head = pq->tail = NULL;pq->size = 0;
}// 入队列
void QueuePush(Que* pq, QDataType x)
{assert(pq); // pq指针不能为空 QNode* newnode = (QNode*)malloc(sizeof(QNode)); // 申请新结点 if (newnode == NULL){perror("malloc fail");exit(-1);}// 初始化新结点中的成员 newnode->data = x;newnode->next = NULL;if (pq->tail == NULL) // 入队列的结点是第一个结点 {pq->head = pq->tail = newnode;}else // 入队列的结点不是第一个结点 {pq->tail->next = newnode;pq->tail = newnode;}pq->size++;
}// 出队列
void QueuePop(Que* pq)
{assert(pq);assert(!QueueEmpty(pq)); // 出队列的时候,队列不能为空 if (pq->head->next == NULL) // 只有一个结点的情况 {free(pq->head);pq->head = pq->tail = NULL;}else // 不止一个结点的情况 {QNode* next = pq->head->next;free(pq->head);pq->head = next;}pq->size--;
}// 取队头元素
QDataType QueueFront(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->head->data;
}// 取队尾元素
QDataType QueueBack(Que* pq)
{assert(pq);assert(!QueueEmpty(pq));return pq->tail->data;
}// 判空
bool QueueEmpty(Que* pq)
{assert(pq);return pq->head == NULL;
}// 获取队列的大小
int QueueSize(Que* pq)
{assert(pq);return pq->size;
}
相关文章:
手撕数据结构 —— 队列(C语言讲解)
目录 1.什么是队列 2.如何实现队列 3.队列的实现 Queue.h中接口总览 具体实现 结构的定义 初始化 销毁 入队列 出队列 取队头元素 取队尾元素 判断是否为空 获取队列的大小 4.完整代码附录 Queue.h Queue.c 1.什么是队列 队列是一种特殊的线性表࿰…...
Java知识巩固(五)
目录 基本数据类型 基本类型和包装类型的区别? 自动装箱与拆箱了解吗?原理是什么? 为什么浮点数运算的时候回邮精度丢失的风险? 如何解决浮点数运算的精度丢失问题? 超过 long 整型的数据应该如何表示? 基本数据…...
C# 中 yield关键字的使用
yield return有以下优点: 每次迭代时生成一个值,并且在下次迭代时继续从上次离开的地方开始。 延迟执行:只有在实际需要时才会生成下一个值,这对于处理大量数据非常有用。 节省内存:不需要一次性将所有数据加载到内存中…...
YoloDotNet 的基本使用方法详解
文章目录 一、创建项目与引用库二、模型加载与初始化三、图像数据的处理与输入四、目标检测结果的获取与解析五、性能优化与参数调整一、创建项目与引用库 在使用 YoloDotNet 之前,首先需要在开发环境中创建一个新的项目。可以选择使用 Visual Studio 等开发工具,创建一个 C#…...
0x12 Dapr Dashboard configurations 未授权访问漏洞 CVE-2022-38817
参考: Dapr Dashboard configurations 未授权访问漏洞 CVE-2022-38817 | PeiQi文库 (wgpsec.org)免责声明 欢迎访问我的博客。以下内容仅供教育和信息用途: 合法性:我不支持或鼓励非法活动。请确保遵守法律法规。信息准确性:尽管我尽力提供准确的信息,但不保证其完全准确…...
Android activity 启动流程
Android activity 启动流程 本文主要记录下acitivty的启动流程. 1: Activity 我们都知道启动activity调用方法: startActivity(Intent intent)startActivity(Intent intent, Nullable Bundle options)startActivityForResult(RequiresPermission Intent intent, int reques…...
使用 Go 语言实现 WebSocket的核心逻辑
文章目录 WebSocket 简介时序图核心逻辑Client 结构与功能创建新客户端消息读取逻辑 (ReadPump)发送消息逻辑 (Send)客户端管理器 (ClientManager)WebSocket 处理器处理心跳与长连接 总结 本文将基于 Go 语言,通过使用 gorilla/websocket 库来实现一个简单的聊天应用…...
Linux下的杀毒软件介绍
Linux下的杀毒软件介绍 一、Linux杀毒软件的基本概念和作用二、Linux杀毒软件的选择三、Linux杀毒软件推荐四、Linux杀毒软件对应用进程的影响五、结论在当今数字化和网络化的环境中,保护计算机系统的安全至关重要。尽管Linux操作系统因其开源、稳定且相对安全的特性而较少受到…...
JSONP详解
JSONP(JSON with Padding)是一种非官方的协议,它允许在服务器端集成Script tags返回至客户端,通过JavaScript callback的形式实现跨域访问。以下是对JSONP的详细解释: 一、JSONP的背景与原理 背景: 由于浏…...
Leetcode—1115. 交替打印 FooBar【中等】(多线程)
2024每日刷题(180) Leetcode—1115. 交替打印 FooBar C实现代码 class FooBar { private:int n;sem_t fooSem;sem_t barSem;public:FooBar(int n) {this->n n;sem_init(&fooSem, 0, 1);sem_init(&barSem, 0, 0);}~FooBar() {sem_destroy(&…...
Visual Studio Code基础:使用debugpy调试python程序
相关阅读 VS codehttps://blog.csdn.net/weixin_45791458/category_12658212.html?spm1001.2014.3001.5482 一、安装调试器插件 在VS code中可以很轻松地调试Python程序,首先需要安装Python调试器插件,如图1所示。 图1 安装调试器插件 Python Debugge…...
超全!一文详解大型语言模型的11种微调方法
导读:大型预训练模型是一种在大规模语料库上预先训练的深度学习模型,它们可以通过在大量无标注数据上进行训练来学习通用语言表示,并在各种下游任务中进行微调和迁移。随着模型参数规模的扩大,微调和推理阶段的资源消耗也在增加。…...
C 主要函数解析
1、fseek 函数 int fseek(FILE *stream, long offset, int fromwhere); 第一个参数stream为文件指针 第二个参数offset为偏移量,正数表示正向偏移,负数表示负向偏移 第三个参数origin设定从文件的哪里开始偏移,可能取值为:SEEK_CUR、 SEE…...
vue3学习:数字时钟遇到的两个问题
在前端开发学习中,用JavaScript脚本写个数字时钟是很常见的案例,也没什么难度。今天有时间,于是就用Vue的方式来实现这个功能。原本以为是件非常容易的事,没想到却卡在两个问题上,一个问题通过别人的博文已经找到答案&…...
吴恩达深度学习笔记:卷积神经网络(Foundations of Convolutional Neural Networks)3.7-3.8
目录 第四门课 卷积神经网络(Convolutional Neural Networks)第三周 目标检测(Object detection)3.7 非极大值抑制(Non-max suppression)3.8 Anchor Boxes 第四门课 卷积神经网络(Convolutional…...
【Linux】最基本的字符设备驱动
前面我们介绍到怎么编译出内核模块.ko文件,然后还加载了这个驱动模块。但是,那个驱动代码还不完善,驱动写好后怎么在应用层使用也没有介绍。 字符设备抽象 Linux内核中将字符设备抽象成一个具体的数据结构(struct cdevÿ…...
利用 Llama 3.1模型 + Dify开源LLM应用开发平台,在你的Windows环境中搭建一套AI工作流
文章目录 1. 什么是Ollama?2. 什么是Dify?3. 下载Ollama4. 安装Ollama5. Ollama Model library模型库6. 本地部署Llama 3.1模型7. 安装Docker Desktop8. 使用Docker-Compose部署Dify9. 注册Dify账号10. 集成本地部署的 Llama 3.1模型11. 集成智谱AI大模型…...
Docker常用命令分享二
docker的用户组管理过程: 1、sudo : 可以让普通用户临时获得root用户的权限,来新建docker用户组 2、普通用户并没有使用sudo的权限 3、先要让root用户把testing用户加入到sudoers的授权文件中 4、sudoers的文件居然是只读的,先解决这个问…...
【一步步开发AI运动小程序】二十、AI运动小程序如何适配相机全屏模式?
引言 受小程序camera组件预览和抽帧图像不一致的特性影响,一直未全功能支持全屏模式,详见本系列文件第四节小程序如何抽帧;随着插件在云上赛事、健身锻炼、AI体测、AR互动场景的深入应用,各开发者迫切的希望能在全屏模式下应用&am…...
[Java基础] 运算符
[Java基础] 基本数据类型 [Java基础] Java HashMap 的数据结构和底层原理 目录 算术运算符 比较运算符 逻辑运算符 位运算符 赋值运算符 其他运算符 常见面试题 Java语言支持哪些类型的运算符? 请解释逻辑运算符&&和&的区别? 请解释条件运…...
【大模型RAG】拍照搜题技术架构速览:三层管道、两级检索、兜底大模型
摘要 拍照搜题系统采用“三层管道(多模态 OCR → 语义检索 → 答案渲染)、两级检索(倒排 BM25 向量 HNSW)并以大语言模型兜底”的整体框架: 多模态 OCR 层 将题目图片经过超分、去噪、倾斜校正后,分别用…...
练习(含atoi的模拟实现,自定义类型等练习)
一、结构体大小的计算及位段 (结构体大小计算及位段 详解请看:自定义类型:结构体进阶-CSDN博客) 1.在32位系统环境,编译选项为4字节对齐,那么sizeof(A)和sizeof(B)是多少? #pragma pack(4)st…...
【2025年】解决Burpsuite抓不到https包的问题
环境:windows11 burpsuite:2025.5 在抓取https网站时,burpsuite抓取不到https数据包,只显示: 解决该问题只需如下三个步骤: 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...
GitHub 趋势日报 (2025年06月08日)
📊 由 TrendForge 系统生成 | 🌐 https://trendforge.devlive.org/ 🌐 本日报中的项目描述已自动翻译为中文 📈 今日获星趋势图 今日获星趋势图 884 cognee 566 dify 414 HumanSystemOptimization 414 omni-tools 321 note-gen …...
JDK 17 新特性
#JDK 17 新特性 /**************** 文本块 *****************/ python/scala中早就支持,不稀奇 String json “”" { “name”: “Java”, “version”: 17 } “”"; /**************** Switch 语句 -> 表达式 *****************/ 挺好的ÿ…...
【C++从零实现Json-Rpc框架】第六弹 —— 服务端模块划分
一、项目背景回顾 前五弹完成了Json-Rpc协议解析、请求处理、客户端调用等基础模块搭建。 本弹重点聚焦于服务端的模块划分与架构设计,提升代码结构的可维护性与扩展性。 二、服务端模块设计目标 高内聚低耦合:各模块职责清晰,便于独立开发…...
Swagger和OpenApi的前世今生
Swagger与OpenAPI的关系演进是API标准化进程中的重要篇章,二者共同塑造了现代RESTful API的开发范式。 本期就扒一扒其技术演进的关键节点与核心逻辑: 🔄 一、起源与初创期:Swagger的诞生(2010-2014) 核心…...
Linux --进程控制
本文从以下五个方面来初步认识进程控制: 目录 进程创建 进程终止 进程等待 进程替换 模拟实现一个微型shell 进程创建 在Linux系统中我们可以在一个进程使用系统调用fork()来创建子进程,创建出来的进程就是子进程,原来的进程为父进程。…...
Kafka入门-生产者
生产者 生产者发送流程: 延迟时间为0ms时,也就意味着每当有数据就会直接发送 异步发送API 异步发送和同步发送的不同在于:异步发送不需要等待结果,同步发送必须等待结果才能进行下一步发送。 普通异步发送 首先导入所需的k…...
MacOS下Homebrew国内镜像加速指南(2025最新国内镜像加速)
macos brew国内镜像加速方法 brew install 加速formula.jws.json下载慢加速 🍺 最新版brew安装慢到怀疑人生?别怕,教你轻松起飞! 最近Homebrew更新至最新版,每次执行 brew 命令时都会自动从官方地址 https://formulae.…...
