当前位置: 首页 > news >正文

【数据结构】队列的实现

白日去如箭,达者惜今阳。                                                   --朱敦儒

目录 

🚁前言:​

🏝️一.队列的概念及结构 

🌻二.队列各种功能的实现

🍍1.队列的初始化

🏝️2.队列的尾入

🍉3.队列头的元素

🍁4.队列的头出

🍀5.判断是否为空

🚲6.队列尾的元素

🪂7.销毁队列

🌴三.队列的全部代码 

🌻1.Queue.h:

🍌2.Queue.c:

🍈3.test.c:


🚁前言:

前几天我们对栈进行了实现,栈是数据先进后出,而今天我们要是实现的队列是完全相反的,队列
是数据先进先出。而在栈中我们使用的顺序表(数组)来实现的。而队列却用单链表来实现是更加合适的。

在队列入数据的时候,相当于是尾插,而队列出数据的时候相当于是头删。

  • 队列的顺序结构
    入队,不需要移动任何元素,时间复杂度为O(1)。
    出队,所有元素需要往前移动,时间复杂度为O(N)。
  • 队列的链式结构
    首先我们定义两个指针,队头指针指向第一个节点,队尾指针指向尾节点。
    入队(尾插),时间复杂度为O(1)。
    出队(头删),时间复杂度为O(1)。
    结论:所以我们使用单链表来实现队列。

🏝️一.队列的概念及结构 

     队列:只允许在一端进行插入数据操作,在另一端进行数据操作的特殊线性表,队列具有先进先出FIFO(Frist in First out)。

入队列:进行插入操作的一端称为队尾。
出队列:进行删除操作的一端称为对头。

队列的初始结构:单链表实现

typedef int QDataType;
typedef struct QueueNode
{struct QueueNode* next;//单链表QDataType data;
}QNode;typedef struct Queue
{QNode* head;//队列头QNode* tail;//队列尾
}Queue;

🌻二.队列各种功能的实现

🍍1.队列的初始化

  这里我们实现的单链表是无头不循环的单链表。所以我们把队列头和队列尾初始化为空指针。

//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->head = ps->tail = NULL;
}

🏝️2.队列的尾入

    对于队列的尾入,我们要分为两种情况:
第一种:第一次尾入数据的时候,队列头和队列尾都是指向的同一个位置,并且都是空,当我们要尾入的时候创建一个新的结点,把新结点赋值给队列的头和队列的尾。

第二种:队列已经有数据了,我们把新的结点链接到尾后面,然后再把新结点赋值为新的结点,也就是更新队列的尾。总结:队列头是一直不变的,队列尾入一个数据就需要把队列尾往后面移动一位。
 

//队尾入
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newnode = (QNode*)malloc(sizeof(QNode));//创建一个新的结点if (newnode == NULL){perror("malloc\n");return;}newnode->data = x;newnode->next = NULL;if ( ps->tail == NULL)//第一种情况{ps->head=ps->tail = newnode;//新结点就是队列尾和队列头}else//第二种情况{ps->tail->next = newnode;//队列尾链接新的结点ps->tail = newnode;//更新队列尾}
}

🍉3.队列头的元素

     需要知道队列头的元素是非常简单的,只需要返回队列头的元素即可。

//头的元素
QDataType QueueFront(Queue* ps)
{assert(ps);assert(ps->head);return ps->head->data;
}

🍁4.队列的头出

   队列的头出也是分为两种情况:
第一种:当队列只有一个结点的时候,直接free掉第一个结点即可,然后把队列头和对列尾赋值尾空即可。
第二种:当队列有两个及两个以上的结点的时候,我们先保存队列头的下一个结点,然后free掉队列头即可。

//对头出
void QueuePop(Queue* ps)
{assert(ps);assert(ps->head);if (ps->head->next == NULL)//当队列只有一个结点时{free(ps->head);ps->head = ps->tail = NULL;}else//当队列有两个或者两个以上的结点时{QNode* next = ps->head->next;//free掉第一个结点时,先保存下一个结点free(ps->head);ps->head = next;}
}

🍀5.判断是否为空

在队列出的时候,我们出一个数据就要判断一下队列是否为空,如果为空,我们就不能出数据了。
我们还是和栈的判断空一样,使用bool值来判断。

//判断是否为空
bool QueueEmpty(Queue* ps) 
{assert(ps);return ps->head == NULL;
}

有了上面的代码我们就可以把出队列的数据给打印一下。

很明显这和队列的结构时一致的,即先进先出。 

🚲6.队列尾的元素

//尾的元素
QDataType QueueBack(Queue* ps)
{assert(ps);assert(ps->head);return ps->tail->data;
}

🪂7.销毁队列

最后退出程序,我们再把队列给销毁一下。

//销毁队列
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur = ps->head;while (cur){QNode* next = ps->head->next;free(ps->head);ps->head = next;cur = next;}ps->head = ps->tail == NULL;
}

最后我们再把队列的功能给实现一下:

 

🌴三.队列的全部代码 

🌻1.Queue.h:

#pragma once
#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;
}Queue;//初始化
void QueueInit(Queue* ps);//队尾插
void QueuePush(Queue* ps,QDataType x);//队头出
void QueuePop(Queue* ps);//头的元素
QDataType QueueFront(Queue* ps);//尾的元素
QDataType QueueBack(Queue* ps);//队列的元素个数
int QueueSize(Queue* ps);//判断是否为空
bool QueueEmpty(Queue* ps);//销毁队列
void QueueDestroy(Queue* ps);

🍌2.Queue.c:
 

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"//初始化
void QueueInit(Queue* ps)
{assert(ps);ps->head = ps->tail = NULL;
}//队尾入
void QueuePush(Queue* ps,QDataType x)
{assert(ps);QNode* newnode = (QNode*)malloc(sizeof(QNode));if (newnode == NULL){perror("malloc\n");return;}newnode->data = x;newnode->next = NULL;if ( ps->tail == NULL){ps->head=ps->tail = newnode;}else{ps->tail->next = newnode;ps->tail = newnode;}
}//对头出
void QueuePop(Queue* ps)
{assert(ps);assert(ps->head);if (ps->head->next == NULL)//当队列只有一个结点时{free(ps->head);ps->head = ps->tail = NULL;}else//当队列有两个或者两个以上的结点时{QNode* next = ps->head->next;//free掉第一个结点时,先保存下一个结点free(ps->head);ps->head = next;}
}//头的元素
QDataType QueueFront(Queue* ps)
{assert(ps);assert(ps->head);return ps->head->data;
}//尾的元素
QDataType QueueBack(Queue* ps)
{assert(ps);assert(ps->head);return ps->tail->data;
}//队列的元素个数
int QueueSize(Queue* ps)
{int count = 0;QNode* cur = ps->head;while (cur){count++;cur = cur->next;}return count;
}//销毁队列
void QueueDestroy(Queue* ps)
{assert(ps);QNode* cur = ps->head;while (cur){QNode* next = ps->head->next;free(ps->head);ps->head = next;cur = next;}ps->head = ps->tail == NULL;
}//判断是否为空
bool QueueEmpty(Queue* ps) 
{assert(ps);return ps->head == NULL;
}

🍈3.test.c:

#define _CRT_SECURE_NO_WARNINGS 1
#include"Queue.h"
int main()
{QNode q;QueueInit(&q);QueuePush(&q, 1);QueuePush(&q, 2);QueuePush(&q, 3);QueuePush(&q, 4);printf("对于队列 1 2 3 4 出的数据为:\n");while (!QueueEmpty(&q)){printf("%d ", QueueFront(&q));QueuePop(&q);}QueuePush(&q, 5);QueuePush(&q, 6);QueuePush(&q, 7);QueuePush(&q, 8);printf("\n");printf("队列的元素为 5 6 7 8\n");printf("队列头的元素为:\n");int first = QueueFront(&q);printf("%d\n", first);printf("队列尾的元素为:\n");int tail = QueueBack(&q);printf("%d\n", tail);printf("队列的元素的个数为:\n");int count = QueueSize(&q);printf("%d\n", count);QueueDestroy(&q);printf("退出程序\n");printf("队列已经被销毁……\n");return 0;
}

相关文章:

【数据结构】队列的实现

白日去如箭&#xff0c;达者惜今阳。 --朱敦儒目录 &#x1f681;前言&#xff1a;​ &#x1f3dd;️一.队列的概念及结构 &#x1f33b;二.队列各种功能的实现 &#x1f34d;1.队列的初始化 &#x1f3dd;️2.队列…...

【数据库】— 无损连接、Chase算法、保持函数依赖

【数据库】— 无损连接、Chase算法 Chase算法Chase算法举例一种简便方法&#xff1a;分解为两个模式时无损连接和函数依赖的一个简单例子 Chase算法 形式化定义&#xff1a; 构造一个 k k k行 n n n列的表格&#xff0c;每行对应一个模式 R i ( 1 ≤ i ≤ k ) Ri (1≤i ≤ k)…...

用英语翻译中文-汉字英文翻译

中文转英语翻译 作为一款高效、准确的中文转英语翻译软件&#xff0c;我们的产品可以帮助全球用户更好地沟通和合作&#xff0c;实现跨文化交流。 在全球化的今天&#xff0c;中英文翻译已经成为商务、学术、娱乐等各个领域不可或缺的一部分。我们的中文转英语翻译软件是为了…...

瑞吉外卖项目——缓存优化

用户数量多&#xff0c;系统访问量大 频繁访问数据库&#xff0c;系统性能下降&#xff0c;用户体验差 环境搭建 maven坐标 在项目的pom.xml文件中导入spring data redis的maven坐标: <dependency><groupId>org.springframework.boot</groupId><arti…...

从头创建一个新的浏览器,这合理吗?

从头构建一个新浏览器&#xff1f;这如果是不是个天大的“伪需求”&#xff0c;便是一场开发者的噩梦&#xff01; 要知道&#xff0c;如果没有上百亿的资金和数百名研发工程师的投入&#xff0c;从头开始构建一个新的浏览器引擎&#xff0c;几乎是不可能的。然而SerenityOS系统…...

TypeScript泛型类型和接口

本节课我们来开始了解 TypeScript 中泛型类型的概念和接口使用。 一&#xff0e;泛型类型 1. 前面&#xff0c;我们通过泛型变量的形式来存储调用方的类型从而进行检查&#xff1b; 2. 而泛型也可以作为类型的方式存在&#xff0c;理解这一点&#xff0c;先了解下函数的…...

docker命令

1.运行 docker-compose up 2.查看命令 docker images 3.删掉docker镜像: docker rmi -f [id] docker卸载 1.杀死docker有关的容器&#xff1a; docker kill $(docker ps -a -q) 2.删除所有docker容器&#xff1a;docker rm $(docker ps -a -q) 3.删除所有docker镜像&…...

2023 年 3 月 NFT 月度报告

作者&#xff1a;Danielfootprint.network 数据来源&#xff1a;NFT Monthly Report 三月份的 NFT 市场上出现了两个有趣的趋势。一方面&#xff0c;Polygon 链尽管在二月份有所突破&#xff0c;达到了 NFT 总交易量的 4.2%&#xff0c;但于三月再次跌至 1% 以下&#xff0c;…...

【http】 get方法和Post方法区别;http和https

get方法和Post方法 get方法&#xff1a;通过url传参&#xff0c;回显输入的私密信息&#xff0c;不够私密 Post方法&#xff1a;通过正文传参&#xff0c;不会回显&#xff0c;一般私密性有保证。 一般如果上传的图片&#xff0c;音频比较大&#xff0c;推荐Post方法&#x…...

第三章 法的渊源与法的分类

目录 第一节 法的渊源的分类 一、法的渊源释义二、法的渊源种类 第二节 正式法源 一、正式法源的含义二、当代中国的正式法源三、正式法源的一般效力原则 第三节 非正式法源 一、当代中国的非正式法源 第四节 法的分类 一、法的一般分类二、法的特殊分类 第一节 法的渊源的…...

在Ubuntu18.04或者20.04下搭建edk2运行环境

#更新完之后依次执行下面两条命令 1.apt-get update 2.apt-get upgrade 如果执行之后出现源不能更新的问题,到/etc/apt/sources.list.d 下删除对应的ppa源重新更新即可解决 git clone https://github.com/tianocore/edk2.git cd edk2 git submodule update --init 如果git cl…...

多线程编程常用函数用法

一、多线程编程常用函数用法 1、pthread_create 头文件 #include<pthread.h>函数声明 int pthread_create(pthread_t*restrict tidp,const pthread_attr_t *restrict_attr,void*&#xff08;*start_rtn)(void*),void *restrict arg)函数功能 pthread_create是UNIX环境…...

C++ 标准模板库(Standard Template Library,STL)

✅作者简介&#xff1a;人工智能专业本科在读&#xff0c;喜欢计算机与编程&#xff0c;写博客记录自己的学习历程。 &#x1f34e;个人主页&#xff1a;小嗷犬的个人主页 &#x1f34a;个人网站&#xff1a;小嗷犬的技术小站 &#x1f96d;个人信条&#xff1a;为天地立心&…...

一个寄存器的bit2 bit3位由10修改成11,C示例

方法1&#xff1a; 如果需要将一个寄存器中的 bit2 和 bit3 两个位从 11 修改为 10&#xff0c;可以使用如下的 C 语言代码实现&#xff1a; // 将寄存器的 bit2 和 bit3 位从 11 修改为 10 volatile uint32_t *reg_addr (volatile uint32_t *)0x12345678; // 假设寄存器地址…...

【洛谷】P1631 序列合并

【洛谷】 P1631 序列合并 题目描述 有两个长度为 N N N 的单调不降序列 A , B A,B A,B&#xff0c;在 A , B A,B A,B 中各取一个数相加可以得到 N 2 N^2 N2 个和&#xff0c;求这 N 2 N^2 N2 个和中最小的 N N N 个。 输入格式 第一行一个正整数 N N N&#xff1b; 第二…...

2023年七大最佳勒索软件解密工具

勒索软件是目前最恶毒且增长最快的网络威胁之一。作为一种危险的恶意软件&#xff0c;它会对文件进行加密&#xff0c;并用其进行勒索来换取报酬。 幸运的是&#xff0c;我们可以使用大量的勒索软件解密工具来解锁文件&#xff0c;而无需支付赎金。如果您的网络不幸感染了勒索软…...

prettier 命令行工具来格式化多个文件

prettier 命令行工具来格式化多个文件 你可以使用 prettier 命令行工具来格式化多个文件。以下是一个使用命令行批量格式化文件的示例&#xff1a; 安装 prettier 如果你还没有安装 prettier&#xff0c;你可以使用以下命令安装它&#xff1a; npm install -g prettier 进入…...

我发现了PMP通关密码!这14页纸直接背!

一周就能背完的PMP考试技巧只有14页纸 共分成了4大模块 完全不用担心看不懂 01关键词篇 第1章引论 1.看到“驱动变革”--选项中找“将来状态” 2.看到“依赖关系”--选项中找“项目集管理” 3.看到“价值最大化”--选项中找“项目组合管理” 4.看到“可行性研究”--选项中…...

Medical X-rays Dataset汇总(长期更新)

目录​​​​​​​ ChestX-ray8 ChestX-ray14 VinDr-CXR VinDr-PCXR ChestX-ray8 ChestX-ray8 is a medical imaging dataset which comprises 108,948 frontal-view X-ray images of 32,717 (collected from the year of 1992 to 2015) unique patients with the text-mi…...

一文告诉你如何做好一份亚马逊商业计划书的框架

“做亚马逊很赚钱”、“我也来做”、“哎&#xff0c;亏钱了”诸如此类的话听了实在是太多。亚马逊作为跨境电商老大哥&#xff0c;许多卖家还是对它怀抱着很高的期许。但是&#xff0c;事实的残酷的。有人入行赚得盆满钵盈&#xff0c;自然也有人亏得血本无归。 会造成这种两…...

【解密LSTM、GRU如何解决传统RNN梯度消失问题】

解密LSTM与GRU&#xff1a;如何让RNN变得更聪明&#xff1f; 在深度学习的世界里&#xff0c;循环神经网络&#xff08;RNN&#xff09;以其卓越的序列数据处理能力广泛应用于自然语言处理、时间序列预测等领域。然而&#xff0c;传统RNN存在的一个严重问题——梯度消失&#…...

【2025年】解决Burpsuite抓不到https包的问题

环境&#xff1a;windows11 burpsuite:2025.5 在抓取https网站时&#xff0c;burpsuite抓取不到https数据包&#xff0c;只显示&#xff1a; 解决该问题只需如下三个步骤&#xff1a; 1、浏览器中访问 http://burp 2、下载 CA certificate 证书 3、在设置--隐私与安全--…...

CMake控制VS2022项目文件分组

我们可以通过 CMake 控制源文件的组织结构,使它们在 VS 解决方案资源管理器中以“组”(Filter)的形式进行分类展示。 🎯 目标 通过 CMake 脚本将 .cpp、.h 等源文件分组显示在 Visual Studio 2022 的解决方案资源管理器中。 ✅ 支持的方法汇总(共4种) 方法描述是否推荐…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

蓝桥杯 冶炼金属

原题目链接 &#x1f527; 冶炼金属转换率推测题解 &#x1f4dc; 原题描述 小蓝有一个神奇的炉子用于将普通金属 O O O 冶炼成为一种特殊金属 X X X。这个炉子有一个属性叫转换率 V V V&#xff0c;是一个正整数&#xff0c;表示每 V V V 个普通金属 O O O 可以冶炼出 …...

【JVM面试篇】高频八股汇总——类加载和类加载器

目录 1. 讲一下类加载过程&#xff1f; 2. Java创建对象的过程&#xff1f; 3. 对象的生命周期&#xff1f; 4. 类加载器有哪些&#xff1f; 5. 双亲委派模型的作用&#xff08;好处&#xff09;&#xff1f; 6. 讲一下类的加载和双亲委派原则&#xff1f; 7. 双亲委派模…...

一些实用的chrome扩展0x01

简介 浏览器扩展程序有助于自动化任务、查找隐藏的漏洞、隐藏自身痕迹。以下列出了一些必备扩展程序&#xff0c;无论是测试应用程序、搜寻漏洞还是收集情报&#xff0c;它们都能提升工作流程。 FoxyProxy 代理管理工具&#xff0c;此扩展简化了使用代理&#xff08;如 Burp…...

6.计算机网络核心知识点精要手册

计算机网络核心知识点精要手册 1.协议基础篇 网络协议三要素 语法&#xff1a;数据与控制信息的结构或格式&#xff0c;如同语言中的语法规则语义&#xff1a;控制信息的具体含义和响应方式&#xff0c;规定通信双方"说什么"同步&#xff1a;事件执行的顺序与时序…...

比特币:固若金汤的数字堡垒与它的四道防线

第一道防线&#xff1a;机密信函——无法破解的哈希加密 将每一笔比特币交易比作一封在堡垒内部传递的机密信函。 解释“哈希”&#xff08;Hashing&#xff09;就是一种军事级的加密术&#xff08;SHA-256&#xff09;&#xff0c;能将信函内容&#xff08;交易细节&#xf…...

从0开始学习R语言--Day17--Cox回归

Cox回归 在用医疗数据作分析时&#xff0c;最常见的是去预测某类病的患者的死亡率或预测他们的结局。但是我们得到的病人数据&#xff0c;往往会有很多的协变量&#xff0c;即使我们通过计算来减少指标对结果的影响&#xff0c;我们的数据中依然会有很多的协变量&#xff0c;且…...