数据结构与算法学习笔记三---队列的链式存储表示和实现(C++)

目录

前言

1.队列的概念

2.队列的表示和实现

1.定义

2.初始化

​编辑

3.销毁队列

4.清空队列

5.队列判空

6.队列长度

7.获取队头元素

8.入队

9.出队

10.遍历

11.完整代码

前言

    这篇博客主要讲的是对队列的链式存储。

1.队列的概念

        队列是一种访问受限的线性表。仅允许在表的一端进行插入操作，在表的另一端进行删除操作。和日常生活中的排队是一致的，最先进入队列的元素最早离开。插入的一端称为队头(front)，删除的一端称为队尾(rear)。

        队列的示意图如下：

        图1.队列的示意图

2.队列的表示和实现

1.定义

        我们使用指针我们使用指向结点元素的指针分别表示队列的队头和队尾。

typedef int ElemType;
typedef struct QNode{
    ElemType data;
    struct QNode * next;
}QNode,*QueuePtr;

typedef struct {
    QueuePtr  front,rear;
}LinkQueue;

2.初始化

        链队列的初始化是构造一个只有一个头结点的空队，使队头和队尾指针指向次节点，并将节点的指针置为NULL。如下图2所示。

        图2.链队列的操作示意图

队列的初始化代码如下：

//初始化
Status initLinkQueue(LinkQueue *queue) {
    queue->front = queue->rear = new QNode;
    if (!queue->front) {
        return 0; // 内存分配失败
    }
    queue->front->next = NULL;
    return 1;
}

3.销毁队列

        为链队列增加销毁方法相对简单，只需释放链表中的所有节点即可。

// 销毁队列
Status destroyQueue(LinkQueue *queue) {
    QueuePtr p, q;
    p = queue->front;
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    queue->front = queue->rear = NULL;
    return 1;
}

4.清空队列

        清空队列的方法类似于销毁队列，但是不释放头结点。可以通过循环释放除头结点外的所有节点，并将头结点的 front 和 rear 指针重新指向头结点。

// 清空队列
Status clearQueue(LinkQueue *queue) {
    QueuePtr p, q;
    p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    queue->front->next = NULL; // 确保头结点的 next 指针为空，即队列为空
    // 注意：这里不释放 queue->front，因为它是队列的永久头节点
    queue->rear = queue->front; // 重新设置队尾指针
    return 1;
}

5.队列判空

        当对头和队尾相同的时候，队列为空。

//判空
Status isEmpty(LinkQueue *queue) {
    return queue->front->next == NULL; // 如果头指针的下一个节点为空，则队列为空
}

6.队列长度

        可以通过遍历队列中的元素来计算队列的长度。

// 求队列长度
int queueLength(LinkQueue *queue) {
    int length = 0;
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}

7.获取队头元素

              获取链队列头元素的时候，首先要判断链队列是否是空队列，如果队列为空，不操作；否则，获取队列的头结点的下一个元素即可（因为我们这里用到了头结点，头结点的数据域是不可用使用的）。

//获取队列头元素
Status getHead(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    *e = queue->front->next->data;
    return 1;
}

8.入队

        入队的过程其实是生成一个新的节点，并且修改尾指针，并且把尾指针设置称为新的节点。

//入队
Status enQueue(LinkQueue *queue, ElemType e) {
    QueuePtr p = new QNode;
    if (!p) {
        return 0; // 内存分配失败
    }
    p->data = e;
    p->next = NULL;
    queue->rear->next = p;
    queue->rear = p;
    return 1;
}

9.出队

        连队列的出队首先是判断链队列是否为空，如果为空，则不操作；否则取出表头元素，修改头指针。

//出队
Status deQueue(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    QueuePtr p = queue->front->next;
    *e = p->data;
    queue->front->next = p->next;
    if (queue->rear == p) {
        queue->rear = queue->front; // 如果出队后队列为空，修改队尾指针
    }
    delete p;
    return 1;
}

10.遍历

        这里当队头和队尾相同的时候，链队列即为空队列。

// 遍历队列
void traverseLinkQueue(LinkQueue *queue) {
    if (isEmpty(queue)) {
        cout << "Queue is empty." << endl;
        return;
    }
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        cout << p->data << " "; // 输出队列中的元素
        p = p->next;
    }
    cout << endl; // 输出完毕后换行
}

11.完整代码

#include <iostream>
using namespace std;

typedef int ElemType;
typedef int Status;
typedef struct QNode {
    ElemType data;
    struct QNode *next;
} QNode, *QueuePtr;

typedef struct {
    QueuePtr  front, rear;
} LinkQueue;

//初始化
Status initLinkQueue(LinkQueue *queue) {
    queue->front = queue->rear = new QNode;
    if (!queue->front) {
        return 0; // 内存分配失败
    }
    queue->front->next = NULL;
    return 1;
}
// 清空队列
Status clearQueue(LinkQueue *queue) {
    QueuePtr p, q;
    p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        q = p;
        p = p->next;
        delete q;
    }
    queue->front->next = NULL; // 确保头结点的 next 指针为空，即队列为空
    // 注意：这里不释放 queue->front，因为它是队列的永久头节点
    queue->rear = queue->front; // 重新设置队尾指针
    return 1;
}

//判空
Status isEmpty(LinkQueue *queue) {
    return queue->front->next == NULL; // 如果头指针的下一个节点为空，则队列为空
}
// 求队列长度
int queueLength(LinkQueue *queue) {
    int length = 0;
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        length++;
        p = p->next;
    }
    return length;
}



//入队
Status enQueue(LinkQueue *queue, ElemType e) {
    QueuePtr p = new QNode;
    if (!p) {
        return 0; // 内存分配失败
    }
    p->data = e;
    p->next = NULL;
    queue->rear->next = p;
    queue->rear = p;
    return 1;
}

//出队
Status deQueue(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    QueuePtr p = queue->front->next;
    *e = p->data;
    queue->front->next = p->next;
    if (queue->rear == p) {
        queue->rear = queue->front; // 如果出队后队列为空，修改队尾指针
    }
    delete p;
    return 1;
}

//获取队列头元素
Status getHead(LinkQueue *queue, ElemType *e) {
    if (queue->front == queue->rear) {
        return 0; // 队列为空
    }
    *e = queue->front->next->data;
    return 1;
}
// 遍历队列
void traverseLinkQueue(LinkQueue *queue) {
    if (isEmpty(queue)) {
        cout << "Queue is empty." << endl;
        return;
    }
    QueuePtr p = queue->front->next; // 从头结点的下一个节点开始遍历
    while (p) {
        cout << p->data << " "; // 输出队列中的元素
        p = p->next;
    }
    cout << endl; // 输出完毕后换行
}

int main(int argc, const char * argv[]) {
    LinkQueue queue;
    cout<<"链队列初始化中..."<<endl;
    if (initLinkQueue(&queue)) {
        cout<<"链队列初始化成功"<<endl;
    }
    cout<<"链队列判空和长度..."<<endl;
    cout<<"队列长度:"<<queueLength(&queue)<<endl;
    if (isEmpty(&queue)) {
        cout<<"队列为空"<<endl;
    }
    // 入队
    enQueue(&queue, 1);
    enQueue(&queue, 2);
    enQueue(&queue, 3);
    traverseLinkQueue(&queue);
    ElemType head;
    if (getHead(&queue, &head)) {
        cout<<"队头指针:"<<head<<endl;
    }
    cout<<"出队测试......"<<endl;
    int element;
    if (deQueue(&queue, &element)) {
        cout<<"出队列成功,出队元素:"<<element<<endl;
    }
    cout<<"出队之后的队列......"<<endl;
    traverseLinkQueue(&queue);
    cout<<"清空队列......"<<endl;
    if (clearQueue(&queue)) {
        cout<<"队列清空成功,队列长度:"<<queueLength(&queue)<<endl;
    }
    // 出队并打印
    ElemType e;
    while (!isEmpty(&queue)) {
        deQueue(&queue, &e);
        cout << e << " ";
    }
    cout << endl;
    
    return 0;
}

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/615581.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

win11安装各银行的网银助手都无法打开，双击没反应？

win11安装各银行的网银助手都无法打开，双击没反应？

大神贴 右键网银助手属性&#xff0c;在目标后面敲一下空格&#xff0c;输入**-runapp**&#xff0c;应用即可。 如图示例&#xff1a;
阅读更多...
推荐一个开源的MES系统

推荐一个开源的MES系统

软件介绍 HM-MES是一款旨在帮助工厂实现生产计划、工艺管理和质量控制的工业生产管理软件。该软件基于Java Web技术和MySql数据库开发&#xff0c;拥有简洁、易用、安全和稳定等特点&#xff0c;适用于广泛的生产管理场景。 功能描述 1.产品和原材料双向溯源&#xff0c;支持二…
阅读更多...
鸿蒙内核源码分析(远程登录篇) | 内核如何接待远方的客人

鸿蒙内核源码分析(远程登录篇) | 内核如何接待远方的客人

什么是远程登录? 每个人都有上门做客的经历,抖音也一直在教我们做人,做客不要空手去,总得带点东西,而对中国人你就不能送钟,不能送梨,最好也别送鞋,因他们与 终 离 邪 谐音,犯忌讳. 这是人情世故,叫礼仪,是中华文明圈的共识,是相互交流信任的基础. 那互联网圈有没有这种共识呢…
阅读更多...
内网渗透之如何批量PTH获取主机权限？

内网渗透之如何批量PTH获取主机权限？

—— 利用CrakMapExec工具进行全网段批量PTH CrackMapExec&#xff08;CME&#xff09;是一款后渗透利用工具&#xff0c;可帮助自动化大型活动目录(AD)网络安全评估任务。其缔造者byt3bl33d3r称&#xff0c;该工具的生存概念是&#xff0c;“利用AD内置功能/协议达成其功能&…
阅读更多...
SpringBoot实现图片验证码

SpringBoot实现图片验证码

引入依赖 <dependency><groupId>com.github.whvcse</groupId><artifactId>easy-captcha</artifactId><version>1.6.2</version> </dependency>代码实现 package com.qiangesoft.captcha.controller;import com.wf.captcha.*…
阅读更多...
实体同城商家短视频获客，3天直播课，玩转实体商家私域，引爆门店增长

实体同城商家短视频获客，3天直播课，玩转实体商家私域，引爆门店增长

课程内容&#xff1a; 实体同城3天直播课【资料】 实体商家获客第一天 .mp4 实体商家获客第二天上.mp4 实体商家获客第二天,mp4 实体商家获客第三天.mp4 实体商家获客第4天.mp4 网盘自动获取 链接&#xff1a;https://pan.baidu.com/s/1lpzKPim76qettahxvxtjaQ?pwd0b8x…
阅读更多...
暗区突围PC测试资格 暗区突围PC端测试资格获取教程

暗区突围PC测试资格 暗区突围PC端测试资格获取教程

《暗区突围》的横空出世&#xff0c;犹如一颗震撼弹投入了游戏圈&#xff0c;它不仅颠覆了传统射击游戏的框架&#xff0c;更以独特的撤离生存机制和深度的装备打造系统&#xff0c;激发了无数玩家的探险欲和竞技精神。在这个由精密设计的地图和复杂多变的战术构成的虚拟舞台中…
阅读更多...
HTTP超时时间设置

HTTP超时时间设置

在进行超时时间设置之前我们需要了解一次http请求经历的过程 浏览器进行DNS域名解析&#xff0c;得到对应的IP地址根据这个IP&#xff0c;找到对应的服务器建立连接&#xff08;三次握手&#xff09;建立TCP连接后发起HTTP请求&#xff08;一个完整的http请求报文&#xff09;服…
阅读更多...
MySQL中索引失效的问题

MySQL中索引失效的问题

索引失效的情况 这是正常查询情况&#xff0c;满足最左前缀&#xff0c;先查有先度高的索引。 1. 注意这里最后一种情况&#xff0c;这里和上面只查询 name 小米科技 的命中情况一样。说明索引部分丢失&#xff01; 2. 这里第二条sql中的&#xff0c;status > 1 就是范围查…
阅读更多...
基于单片机的直流电机控制方法研究

基于单片机的直流电机控制方法研究

摘要&#xff1a;分析表明&#xff0c;我国用电设备应用数量的持续增加&#xff0c;单片机在电力领域的应用范围也在不断扩大。基 于对电动机运行转速的有效控制&#xff0c;成为自动控制系统关注的重点。研究单片机控制直流电机运行状态的 方法。 关键词&#xff1a;单片机&a…
阅读更多...
30年赚1000亿美元--“量化之王”和他最传奇的基金“大奖章”的秘密

30年赚1000亿美元--“量化之王”和他最传奇的基金“大奖章”的秘密

文艺复兴是华尔街最成功、最神秘的机构之一。从1988-2018年的30年里&#xff0c;文艺复兴仅向内部员工开放的旗舰基金“大奖章”累计创造了超过1000亿美元的收益&#xff0c;年均回报率高达39%。作为对比&#xff0c;同期“股神”巴菲特的年均回报率为20.5%。 而且&#xff0c;…
阅读更多...
【C语言—猜数字小游戏】

【C语言—猜数字小游戏】

一、游戏规则 电脑自动生成一个1~100范围内的随机数&#xff0c;由玩家猜测本轮生成的随机数是什么&#xff0c;系统根据玩家猜测数据的⼤⼩给出猜⼤了或猜⼩了的反馈&#xff0c;直到玩家猜对&#xff0c;游戏结束。 如何生成随机数&#xff1a;【C语言】/*如何生成随机值*/-C…
阅读更多...
【gpedit.msc】组策略编辑器的安装，针对windows家庭版，没有此功能

【gpedit.msc】组策略编辑器的安装，针对windows家庭版，没有此功能

创建一个记事本文件然后放入以下内容 echo offpushd "%~dp0"dir /b %systemroot%\Windows\servicing\Packages\Microsoft-Windows-GroupPolicy-ClientExtensions-Package~3*.mum >gp.txtdir /b %systemroot%\servicing\Packages\Microsoft-Windows-GroupPolicy-…
阅读更多...
mac第三方软件怎么删除 MacBook卸载第三方应用程序 mac第三方恶意软件删除不了怎么办呢

mac第三方软件怎么删除 MacBook卸载第三方应用程序 mac第三方恶意软件删除不了怎么办呢

Mac是一款优秀的个人电脑&#xff0c;它拥有流畅的操作系统、强大的性能和丰富的应用程序。但是&#xff0c;随着使用时间的增加&#xff0c;你可能会发现你的Mac上安装了一些不需要或者不喜欢的第三方软件&#xff0c;这些软件可能会占用你的空间、影响你的速度或者带来安全风…
阅读更多...
构建无服务器数仓（二）Apache DolphinScheduler 集成以及 LOB 粒度资源消费分析

构建无服务器数仓（二）Apache DolphinScheduler 集成以及 LOB 粒度资源消费分析

引言 在数据驱动的世界中&#xff0c;企业正在寻求可靠且高性能的解决方案来管理其不断增长的数据需求。本系列博客从一个重视数据安全和合规性的 B2C 金融科技客户的角度来讨论云上云下混合部署的情况下如何利用亚马逊云科技云原生服务、开源社区产品以及第三方工具构建无服务…
阅读更多...
利用OpenShift的ImageStream部署临时版本

利用OpenShift的ImageStream部署临时版本

公司是港企&#xff0c;项目都部署在OpenShift上统一管理&#xff0c;因为运行环境为香港网络(外网)&#xff0c;配置、中间件等大陆无法直接访问联通。因此在大陆开发时&#xff0c;测试是个很大的问题。为了避免往Git上频繁提交未确定可用的版本&#xff0c;选择用利用OpenSh…
阅读更多...
java-函数式编程-jdk

java-函数式编程-jdk

背景 函数式接口很简单&#xff0c;但是不是每一个函数式接口都需要我们自己来写jdk 根据 有无参数&#xff0c;有无返回值&#xff0c;参数的个数和类型&#xff0c;返回值的类型 提前定义了一些通用的函数式接口 IntPredicate 参数&#xff1a;有一个&#xff0c;类型是int类…
阅读更多...
基于CCS5.5的双音多频(DTMF)信号检测仿真实验(①检测型音频文件②输入生成音频并检测)

基于CCS5.5的双音多频(DTMF)信号检测仿真实验(①检测型音频文件②输入生成音频并检测)

DTMF的优点 我们知道，DTMF根本上仍然是频谱分析，基础还是DFT，但DFT通常需要对一整段数据做变换，而DTMF不同，每输入一个采样点就计算一次，更有利于硬件实现。 基于CCS的双音多频(DTMF)信号检测原理 公式详细推导 详细的公式推导在下面这篇博客中已经进行了详细的描述，…
阅读更多...
哈希算法在区块链中的应用

哈希算法在区块链中的应用

哈希算法是区块链技术的核心组件之一&#xff0c;它确保了区块链数据的不可篡改性和安全性。在本文中&#xff0c;我们将探讨哈希算法的基本原理&#xff0c;以及它在区块链中的具体应用。 哈希算法的基本原理 哈希算法是一种数学函数&#xff0c;它接收输入&#xff08;或“消…
阅读更多...
Shell编程之循环语句

Shell编程之循环语句

目录 1.for循环语句&#xff08;遍历循环&#xff09; 1.1 for语句的结构 1.2 for语句的执行流程 1.3 for语句应用示例 1.4 echo命令参数 2.while循环语句 2.1 while语句应用示例 2.2 通过while循环读取行内容 3.until 4.双重循环 4.1 双重循环案例 4.2 循环的退出 …
阅读更多...
最新文章

Copyright @ 2022~2023