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

《数据结构、算法与应用C++语言描述》使用C++语言实现链表队列

《数据结构、算法与应用C++语言描述》使用C++语言实现链表队列

定义

队列的定义

队列(queue)是一个线性表,其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾(back或rear),删除元素的那一端称为队首(front)。

队列的抽象数据类型

在这里插入图片描述

链表队列代码

_17queue.h

抽象类栈。

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			队列的抽象类
*/
#pragma once
#ifndef _QUEUE_H_
#define _QUEUE_H_
template<class T>
class queue
{
public:virtual ~queue() {}virtual bool empty() const = 0;//返回true,当且仅当队列为空virtual int size() const = 0;//返回队列中元素个数virtual T& front() = 0;//返回头元素的引用virtual T& back() = 0;//返回尾元素的引用virtual void pop() = 0;//删除首元素virtual void push(const T& theElement) = 0;//把元素theELment加入队尾
};
#endif

_6chainNode.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日22点06分
Last Version:			V1.0
Descriptions:			链表的结点
*/
#pragma once
#ifndef _CHAINNODE_H_
#define _CHAINNODE_H_
template <class T>
struct chainNode
{//数据成员T element;chainNode<T>* next;//方法chainNode() {}chainNode(const T& element){this->element = element;this->next = nullptr;}chainNode(const T& element, chainNode<T>* next){this->element = element;this->next = next;}
};
#endif

_21linkedQueue.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			链表存储的队列的头文件
*/
#pragma once
#ifndef _LINKEDQUEUE_H_
#define _LINKEDQUEUE_H_
#include<sstream>
#include<iostream>
#include "_1myExceptions.h"
#include "_6chainNode.h"
#include "_17queue.h"
/*测试函数*/
void linkedQueueTest();using namespace std;
template<class T>
class linkedQueue : public queue<T>
{
public:/*成员函数*/linkedQueue(int initialCapacity = 10){theFront = theBack = nullptr;queueSize = 0;}~linkedQueue();bool empty() const { return queueSize == 0; }//返回队列的元素个数int size() const { return queueSize; }/*清空队列中的元素*/void clear();/*返回第一个元素*/T& front() { return theFront->element; }/*返回最后一个元素*/T& back() { return theBack->element; }/*删除队首元素*/void pop(){chainNode<T>* next = theFront->next;delete theFront;theFront = next;queueSize--;}/*向队尾插入元素theElement*/void push(const T& theElement){if (queueSize == 0)theFront = theBack = new chainNode<T>(theElement, nullptr);else{theBack->next = new chainNode<T>(theElement, nullptr);theBack = theBack->next;}       queueSize++;}//void meld(arrayQueue<T>& a, arrayQueue<T>& b);//合并队列a,b到当前队列//void split(arrayQueue<T>& a, arrayQueue<T>& b);//将当前队列分成两个队列a,b/*重载操作符*//*重载[]操作符*/T operator[](int i){chainNode<T>* currentNode = theFront;for (int j = 0; j < i; j++)currentNode = currentNode->next;return currentNode->element;}/*友元函数*/friend istream& operator>> <T>(istream& in, linkedQueue<T>& m);//输出但是不pop()元素friend ostream& operator<< <T>(ostream& out, linkedQueue<T>& m);
private:chainNode<T>* theFront;       // 指向第一个元素的指针chainNode<T>* theBack;        // 指向最后一个元素的指针int queueSize;    // 队列的容量,实质上比队列容量(不包含queueFront指向的那一个位置)大1
};
/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, linkedQueue<T>& m)
{int numberOfElement = 0;cout << "Please enter the number of element:";while (!(in >> numberOfElement)){in.clear();//清空标志位while (in.get() != '\n')//删除无效的输入continue;cout << "Please enter the number of element:";}T cinElement;for (int i = 0; i < numberOfElement; i++){cout << "Please enter the element " << i + 1 << ":";while (!(in >> cinElement)){in.clear();//清空标志位while (in.get() != '\n')//删除无效的输入continue;cout << "Please enter the element " << i + 1 << ":";}m.push(cinElement);}return in;
}
//输出但是不pop()元素
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, linkedQueue<T>& m)
{chainNode<T>* currentNode = m.theFront;while(currentNode != nullptr){cout << currentNode->element << " ";currentNode = currentNode->next;}out << endl;return out;
}
/*成员函数*/
/*析构函数*/
template<class T>
linkedQueue<T>::~linkedQueue()
{chainNode<T>* nextNode = theFront;while (nextNode != nullptr){nextNode = nextNode->next;delete theFront;theFront = nextNode;}
}
/*清空队列中的元素*/
template<class T>
void linkedQueue<T>::clear()
{chainNode<T>* nextNode = theFront;while (nextNode != nullptr){nextNode = nextNode->next;delete theFront;theFront = nextNode;}queueSize = 0;theFront = theBack = nullptr;
}#endif

_21linkedQueue.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			测试_21linkedQueue.h头文件中的所有函数
*/
#include <iostream>
#include <time.h>
#include "_21linkedQueue.h"
using namespace std;
/*测试函数*/
void linkedQueueTest()
{cout << endl << "*********************************linkedQueueTest()函数开始*************************************" << endl;linkedQueue<int> a;//测试输入和输出cout << endl << "测试友元函数*******************************************" << endl;cout << "输入输出************************" << endl;cin >> a;cout << "linkedQueue a is:" << a;cout << endl << "测试成员函数*******************************************" << endl;cout << "empty()*************************" << endl;cout << "a.empty() = " << a.empty() << endl;cout << "size()**************************" << endl;cout << "a.size() = " << a.size() << endl;cout << "push()**************************" << endl;cout << "before push linkedQueue a is:" << a;a.push(99);a.push(22);cout << "after push linkedQueue a is:" << a;cout << "front()*************************" << endl;cout << "a.front() = " << a.front() << endl;cout << "back()**************************" << endl;cout << "a.back() = " << a.back() << endl;cout << "pop()***************************" << endl;cout << "before pop linkedQueue a is:" << a;a.pop();a.pop();cout << "after pop linkedQueue a is:" << a;cout << "clear()*************************" << endl;a.clear();cout << "after clear linkedQueue a is:" << a;cout << endl << "测试成员函数性能***************************************" << endl;cout << "push()**************************" << endl;linkedQueue<int> f;double clocksPerMillis = double(CLOCKS_PER_SEC) / 1000;clock_t startTime = clock();for (int i = 0; i < 100000000; i++)f.push(i);double pushTime = (clock() - startTime) / clocksPerMillis;cout << 10000 << " push took " << pushTime << " ms" << endl;cout << "*********************************linkedQueueTest()函数结束*************************************" << endl;
}

main.cpp

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			main()函数,控制运行所有的测试函数
*/
#include <iostream>
#include "_18arrayQueue.h"int main()
{arrayQueueTest();return 0;
}

_1myExceptions.h

/*
Project name :			allAlgorithmsTest
Last modified Date:		2022年8月13日17点38分
Last Version:			V1.0
Descriptions:			综合各种异常
*/
#pragma once
#ifndef _MYEXCEPTIONS_H_
#define _MYEXCEPTIONS_H_
#include <string>
#include<iostream>using namespace std;// illegal parameter value
class illegalParameterValue 
{public:illegalParameterValue(string theMessage = "Illegal parameter value"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// illegal input data
class illegalInputData 
{public:illegalInputData(string theMessage = "Illegal data input"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// illegal index
class illegalIndex 
{public:illegalIndex(string theMessage = "Illegal index"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// matrix index out of bounds
class matrixIndexOutOfBounds 
{public:matrixIndexOutOfBounds(string theMessage = "Matrix index out of bounds"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// matrix size mismatch
class matrixSizeMismatch 
{public:matrixSizeMismatch(string theMessage = "The size of the two matrics doesn't match"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// stack is empty
class stackEmpty
{public:stackEmpty(string theMessage = "Invalid operation on empty stack"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// queue is empty
class queueEmpty
{public:queueEmpty(string theMessage = "Invalid operation on empty queue"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// hash table is full
class hashTableFull
{public:hashTableFull(string theMessage = "The hash table is full"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// edge weight undefined
class undefinedEdgeWeight
{public:undefinedEdgeWeight(string theMessage = "No edge weights defined"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};// method undefined
class undefinedMethod
{public:undefinedMethod(string theMessage = "This method is undefined"){message = theMessage;}void outputMessage() {cout << message << endl;}private:string message;
};
#endif

相关文章:

《数据结构、算法与应用C++语言描述》使用C++语言实现链表队列

《数据结构、算法与应用C语言描述》使用C语言实现链表队列 定义 队列的定义 队列&#xff08;queue&#xff09;是一个线性表&#xff0c;其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾&#xff08;back或rear&#xff09;&#xff0c;删除元素的那一端称…...

RT-Thread学习笔记(四):RT-Thread Studio工具使用

RT-Thread Studio工具使用 官网详细资料实用操作1. 查看 RT-Thread RTOS API 文档2.打开已创建的工程3.添加头文件路径4. 如何设置生成hex文件5.新建工程 官网详细资料 RT-Thread Studio 用户手册 实用操作 1. 查看 RT-Thread RTOS API 文档 2.打开已创建的工程 如果打开项目…...

【计算机网络笔记】OSI参考模型中端-端层(传输层、会话层、表示层、应用层)功能介绍

系列文章目录 什么是计算机网络&#xff1f; 什么是网络协议&#xff1f; 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能&#xff08;1&#xff09;——速率、带宽、延迟 计算机网络性能&#xff08;2&#xff09;…...

RabbitMQ高级知识点

以下是一些 RabbitMQ 的高级知识点&#xff1a; 1. Exchange&#xff1a; RabbitMQ 中的 Exchange 是消息路由器&#xff0c;用来接收消息并且转发到对应的 Queue 中。Exchange 有四种类型&#xff1a;Direct Exchange、Fanout Exchange、Topic Exchange 和 Headers Exchange。…...

Node直接执行ts文件

Node直接执行ts文件 1、常规流程 node 执行 【ts 文件】 流程&#xff1a; 1、编写ts代码 2、编译成js代码 [命令如 &#xff1a;tsc xx.ts] 3、执行js代码 [node xx.js]2、直接执行 想要直接执行 ts 文件&#xff0c;需要安装如下依赖工具。 执行如下命令&#xff1a; # 安装…...

log4j的级别的说明

一 log4j的级别 1.1 级别类型 TRACE 》DEBUG 》 INFO 》 WARN 》 ERROR 》 FATAL 级别高低顺序为&#xff1a; trace级别最低 &#xff0c;Fatal级别最高。由左到右&#xff0c;从低到高 1.2 包含范围 原则&#xff1a; 本级别包含本级别以及大于本级别的内容&#xff0c;…...

头脑风暴之约瑟夫环问题

一 问题的引入 约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的&#xff0c;可以把问题描述如下&#xff1a; 现有n个人围成一桌坐下&#xff0c;编号从1到n&#xff0c;从编号为1的人开始报数。报数也从1开始&#xff0c;报到m人离席&#xff0c…...

【四:Spring整合Junit】

目录 相同点不同点1、导入依赖增加2、编写的位置不同。。路径一定要与实现类一致 相同点 前面都一样和Spring整合mybatis&#xff08;基于注解形式&#xff09;一样Spring整合Mybatis 不同点 1、导入依赖增加 <!-- 单元测试 --><dependency><groupId>junit&…...

openHarmony UI开发

常用组件和布局方式 组件 ArkUI有丰富的内置组件&#xff0c;包括文本、按钮、图片、进度条、输入框、单选框、多选框等。和布局一样&#xff0c;我们也可以将基础组件组合起来&#xff0c;形成自定义组件。 按钮&#xff1a; Button(Ok, { type: ButtonType.Normal, stateEf…...

Qt 目录操作(QDir 类)及展示系统文件实战 QFilelnfo 类介绍和获取文件属性项目实战

一、目录操作(QDir 类) QDir 类提供访问系统目录结构 QDir 类提供对目录结构及其内容的访问。QDir 用于操作路径名、访问有关路径和文件的信息以及操作底层文件系统。它还可以用于访问 Qt 的资源系统 Qt 使用“/”作为通用目录分隔符&#xff0c;与“/”在 URL 中用作路径分…...

2023-9-12 阿里健康2024秋招后端开发-体检及泛医疗二面

1 自我介绍 2 快手实习 2.1 说说你在实习期间遇到的挑战、收获 &#xff08;1&#xff09;在设计模式的应用能力上&#xff0c;有了很大的提高&#xff0c;使用模板设计模式&#xff0c;架构实例反向同步到架构定义&#xff0c;使用了策略模式 &#xff08;2&#xff09; …...

Qt扫盲-QBrush理论使用总结

Q 理论使用总结 一、概述1. 填充模式2. 笔刷颜色3. 纹理 二、 Qt::GlobalColor 一、概述 QBrush类定义了由 QPainter 绘制的形状的填充模式。画笔有样式、颜色、渐变和纹理。 brush style() 使用Qt::BrushStyle 枚举定义填充模式。默认的笔刷样式是 Qt::NoBrush(取决于你如何…...

互联网Java工程师面试题·Java 面试篇·第三弹

目录 39、JRE、JDK、JVM 及 JIT 之间有什么不同&#xff1f; 40、解释 Java 堆空间及 GC&#xff1f; 41、你能保证 GC 执行吗&#xff1f; 42、怎么获取 Java 程序使用的内存&#xff1f;堆使用的百分比&#xff1f; 43、Java 中堆和栈有什么区别&#xff1f; 44、“ab”…...

如何使用VSCode将iPad Pro转化为功能强大的开发工具?

文章目录 前言1. 本地环境配置2. 内网穿透2.1 安装cpolar内网穿透(支持一键自动安装脚本)2.2 创建HTTP隧道 3. 测试远程访问4. 配置固定二级子域名4.1 保留二级子域名4.2 配置二级子域名 5. 测试使用固定二级子域名远程访问6. iPad通过软件远程vscode6.1 创建TCP隧道 7. ipad远…...

将用友U8的数据可视化需要哪些工具?

将金蝶U8的数据可视化需要一个奥威BI数据可视化工具&#xff0c;以及一套专为用友U8打造的标准化BI数据分析方案。 奥威BI SaaS平台&#xff1a;一键链接用友U8&#xff0c;立得报表 别的BI软件围绕用友U8的数据做可视化&#xff1a;1、准备配置环境&#xff1b;2、下载安装配…...

DOS常用指令

一、dir显示目录 dir命令是Windows系统常用的命令&#xff0c;用于显示目录的文件和子目录的列表。如果不使用参数&#xff0c;此命令将显示磁盘的卷标和序列号&#xff0c;然后是磁盘上的目录和文件列表&#xff08;包括它们的名称以及每个文件最后修改的日期和时间&#xff…...

【Pycharm中python调用另一个文件类或者函数】

Pycharm中python调用另一个文件类或者函数 本文主要介绍了Pycharm中python调用另一个文件类或者函数&#xff0c;文中通过示例代码介绍的非常详细&#xff0c;对大家的学习或者工作具有一定的参考学习价值&#xff0c;需要的朋友们下面随着小编来一起学习学习吧 文章目录 Pycha…...

pycharm操作git、前后端项目上传到gitee

pycharm操作git 之前用命令做的所有操作&#xff0c;使用pychrm点点就可以完成 克隆代码 上方工具栏Git ⇢ \dashrightarrow ⇢ Clone ⇢ \dashrightarrow ⇢ 填写地址&#xff08;http、ssh&#xff09; 提交到暂存区&#xff0c;提交到版本库&#xff0c;推送到远程 直接…...

jmeter监听每秒点击数(Hits per Second)

jmeter监听每秒点击数&#xff08;Hits per Second&#xff09; 下载插件添加监听器执行压测&#xff0c;监听结果 下载插件 点击选项&#xff0c;点击Plugins Manager (has upgrades)&#xff0c;点击Available Plugins&#xff0c;搜索5 Additional Graphs安装。 添加监听…...

RabbitMQ 消息模型

参考 ​​​​​​【RabbitMQ】RabbitMQ架构模型_rabbitmq结构模型-CSDN博客 之前的学习都只是知道名字&#xff0c;但并没有真正的理解&#xff0c;每次看还是不懂&#xff0c;所以今日理解透 &#xff01; RabbitMQ 收发消息过程如下&#xff1a; 首先从消费者开始&#xff1…...

SpringBoot-17-MyBatis动态SQL标签之常用标签

文章目录 1 代码1.1 实体User.java1.2 接口UserMapper.java1.3 映射UserMapper.xml1.3.1 标签if1.3.2 标签if和where1.3.3 标签choose和when和otherwise1.4 UserController.java2 常用动态SQL标签2.1 标签set2.1.1 UserMapper.java2.1.2 UserMapper.xml2.1.3 UserController.ja…...

XML Group端口详解

在XML数据映射过程中&#xff0c;经常需要对数据进行分组聚合操作。例如&#xff0c;当处理包含多个物料明细的XML文件时&#xff0c;可能需要将相同物料号的明细归为一组&#xff0c;或对相同物料号的数量进行求和计算。传统实现方式通常需要编写脚本代码&#xff0c;增加了开…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

大模型多显卡多服务器并行计算方法与实践指南

一、分布式训练概述 大规模语言模型的训练通常需要分布式计算技术,以解决单机资源不足的问题。分布式训练主要分为两种模式: 数据并行:将数据分片到不同设备,每个设备拥有完整的模型副本 模型并行:将模型分割到不同设备,每个设备处理部分模型计算 现代大模型训练通常结合…...

06 Deep learning神经网络编程基础 激活函数 --吴恩达

深度学习激活函数详解 一、核心作用 引入非线性:使神经网络可学习复杂模式控制输出范围:如Sigmoid将输出限制在(0,1)梯度传递:影响反向传播的稳定性二、常见类型及数学表达 Sigmoid σ ( x ) = 1 1 +...

用机器学习破解新能源领域的“弃风”难题

音乐发烧友深有体会&#xff0c;玩音乐的本质就是玩电网。火电声音偏暖&#xff0c;水电偏冷&#xff0c;风电偏空旷。至于太阳能发的电&#xff0c;则略显朦胧和单薄。 不知你是否有感觉&#xff0c;近两年家里的音响声音越来越冷&#xff0c;听起来越来越单薄&#xff1f; —…...

HarmonyOS运动开发:如何用mpchart绘制运动配速图表

##鸿蒙核心技术##运动开发##Sensor Service Kit&#xff08;传感器服务&#xff09;# 前言 在运动类应用中&#xff0c;运动数据的可视化是提升用户体验的重要环节。通过直观的图表展示运动过程中的关键数据&#xff0c;如配速、距离、卡路里消耗等&#xff0c;用户可以更清晰…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

Java求职者面试指南:计算机基础与源码原理深度解析

Java求职者面试指南&#xff1a;计算机基础与源码原理深度解析 第一轮提问&#xff1a;基础概念问题 1. 请解释什么是进程和线程的区别&#xff1f; 面试官&#xff1a;进程是程序的一次执行过程&#xff0c;是系统进行资源分配和调度的基本单位&#xff1b;而线程是进程中的…...