当前位置: 首页 > 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…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

LeetCode - 394. 字符串解码

题目 394. 字符串解码 - 力扣&#xff08;LeetCode&#xff09; 思路 使用两个栈&#xff1a;一个存储重复次数&#xff0c;一个存储字符串 遍历输入字符串&#xff1a; 数字处理&#xff1a;遇到数字时&#xff0c;累积计算重复次数左括号处理&#xff1a;保存当前状态&a…...

Qwen3-Embedding-0.6B深度解析:多语言语义检索的轻量级利器

第一章 引言&#xff1a;语义表示的新时代挑战与Qwen3的破局之路 1.1 文本嵌入的核心价值与技术演进 在人工智能领域&#xff0c;文本嵌入技术如同连接自然语言与机器理解的“神经突触”——它将人类语言转化为计算机可计算的语义向量&#xff0c;支撑着搜索引擎、推荐系统、…...

数据链路层的主要功能是什么

数据链路层&#xff08;OSI模型第2层&#xff09;的核心功能是在相邻网络节点&#xff08;如交换机、主机&#xff09;间提供可靠的数据帧传输服务&#xff0c;主要职责包括&#xff1a; &#x1f511; 核心功能详解&#xff1a; 帧封装与解封装 封装&#xff1a; 将网络层下发…...

Android 之 kotlin 语言学习笔记三(Kotlin-Java 互操作)

参考官方文档&#xff1a;https://developer.android.google.cn/kotlin/interop?hlzh-cn 一、Java&#xff08;供 Kotlin 使用&#xff09; 1、不得使用硬关键字 不要使用 Kotlin 的任何硬关键字作为方法的名称 或字段。允许使用 Kotlin 的软关键字、修饰符关键字和特殊标识…...

Element Plus 表单(el-form)中关于正整数输入的校验规则

目录 1 单个正整数输入1.1 模板1.2 校验规则 2 两个正整数输入&#xff08;联动&#xff09;2.1 模板2.2 校验规则2.3 CSS 1 单个正整数输入 1.1 模板 <el-formref"formRef":model"formData":rules"formRules"label-width"150px"…...

CSS设置元素的宽度根据其内容自动调整

width: fit-content 是 CSS 中的一个属性值&#xff0c;用于设置元素的宽度根据其内容自动调整&#xff0c;确保宽度刚好容纳内容而不会超出。 效果对比 默认情况&#xff08;width: auto&#xff09;&#xff1a; 块级元素&#xff08;如 <div>&#xff09;会占满父容器…...

网站指纹识别

网站指纹识别 网站的最基本组成&#xff1a;服务器&#xff08;操作系统&#xff09;、中间件&#xff08;web容器&#xff09;、脚本语言、数据厍 为什么要了解这些&#xff1f;举个例子&#xff1a;发现了一个文件读取漏洞&#xff0c;我们需要读/etc/passwd&#xff0c;如…...

C/C++ 中附加包含目录、附加库目录与附加依赖项详解

在 C/C 编程的编译和链接过程中&#xff0c;附加包含目录、附加库目录和附加依赖项是三个至关重要的设置&#xff0c;它们相互配合&#xff0c;确保程序能够正确引用外部资源并顺利构建。虽然在学习过程中&#xff0c;这些概念容易让人混淆&#xff0c;但深入理解它们的作用和联…...

怎么让Comfyui导出的图像不包含工作流信息,

为了数据安全&#xff0c;让Comfyui导出的图像不包含工作流信息&#xff0c;导出的图像就不会拖到comfyui中加载出来工作流。 ComfyUI的目录下node.py 直接移除 pnginfo&#xff08;推荐&#xff09;​​ 在 save_images 方法中&#xff0c;​​删除或注释掉所有与 metadata …...