《数据结构、算法与应用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语言实现链表队列 定义 队列的定义 队列(queue)是一个线性表,其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾(back或rear),删除元素的那一端称…...
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参考模型中端-端层(传输层、会话层、表示层、应用层)功能介绍
系列文章目录 什么是计算机网络? 什么是网络协议? 计算机网络的结构 数据交换之电路交换 数据交换之报文交换和分组交换 分组交换 vs 电路交换 计算机网络性能(1)——速率、带宽、延迟 计算机网络性能(2)…...
RabbitMQ高级知识点
以下是一些 RabbitMQ 的高级知识点: 1. Exchange: RabbitMQ 中的 Exchange 是消息路由器,用来接收消息并且转发到对应的 Queue 中。Exchange 有四种类型:Direct Exchange、Fanout Exchange、Topic Exchange 和 Headers Exchange。…...
Node直接执行ts文件
Node直接执行ts文件 1、常规流程 node 执行 【ts 文件】 流程: 1、编写ts代码 2、编译成js代码 [命令如 :tsc xx.ts] 3、执行js代码 [node xx.js]2、直接执行 想要直接执行 ts 文件,需要安装如下依赖工具。 执行如下命令: # 安装…...
log4j的级别的说明
一 log4j的级别 1.1 级别类型 TRACE 》DEBUG 》 INFO 》 WARN 》 ERROR 》 FATAL 级别高低顺序为: trace级别最低 ,Fatal级别最高。由左到右,从低到高 1.2 包含范围 原则: 本级别包含本级别以及大于本级别的内容,…...
头脑风暴之约瑟夫环问题
一 问题的引入 约瑟夫问题的源头完全可以命名为“自杀游戏”。本着和谐友爱和追求本质的目的,可以把问题描述如下: 现有n个人围成一桌坐下,编号从1到n,从编号为1的人开始报数。报数也从1开始,报到m人离席,…...
【四:Spring整合Junit】
目录 相同点不同点1、导入依赖增加2、编写的位置不同。。路径一定要与实现类一致 相同点 前面都一样和Spring整合mybatis(基于注解形式)一样Spring整合Mybatis 不同点 1、导入依赖增加 <!-- 单元测试 --><dependency><groupId>junit&…...
openHarmony UI开发
常用组件和布局方式 组件 ArkUI有丰富的内置组件,包括文本、按钮、图片、进度条、输入框、单选框、多选框等。和布局一样,我们也可以将基础组件组合起来,形成自定义组件。 按钮: Button(Ok, { type: ButtonType.Normal, stateEf…...
Qt 目录操作(QDir 类)及展示系统文件实战 QFilelnfo 类介绍和获取文件属性项目实战
一、目录操作(QDir 类) QDir 类提供访问系统目录结构 QDir 类提供对目录结构及其内容的访问。QDir 用于操作路径名、访问有关路径和文件的信息以及操作底层文件系统。它还可以用于访问 Qt 的资源系统 Qt 使用“/”作为通用目录分隔符,与“/”在 URL 中用作路径分…...
2023-9-12 阿里健康2024秋招后端开发-体检及泛医疗二面
1 自我介绍 2 快手实习 2.1 说说你在实习期间遇到的挑战、收获 (1)在设计模式的应用能力上,有了很大的提高,使用模板设计模式,架构实例反向同步到架构定义,使用了策略模式 (2) …...
Qt扫盲-QBrush理论使用总结
Q 理论使用总结 一、概述1. 填充模式2. 笔刷颜色3. 纹理 二、 Qt::GlobalColor 一、概述 QBrush类定义了由 QPainter 绘制的形状的填充模式。画笔有样式、颜色、渐变和纹理。 brush style() 使用Qt::BrushStyle 枚举定义填充模式。默认的笔刷样式是 Qt::NoBrush(取决于你如何…...
互联网Java工程师面试题·Java 面试篇·第三弹
目录 39、JRE、JDK、JVM 及 JIT 之间有什么不同? 40、解释 Java 堆空间及 GC? 41、你能保证 GC 执行吗? 42、怎么获取 Java 程序使用的内存?堆使用的百分比? 43、Java 中堆和栈有什么区别? 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数据可视化工具,以及一套专为用友U8打造的标准化BI数据分析方案。 奥威BI SaaS平台:一键链接用友U8,立得报表 别的BI软件围绕用友U8的数据做可视化:1、准备配置环境;2、下载安装配…...
DOS常用指令
一、dir显示目录 dir命令是Windows系统常用的命令,用于显示目录的文件和子目录的列表。如果不使用参数,此命令将显示磁盘的卷标和序列号,然后是磁盘上的目录和文件列表(包括它们的名称以及每个文件最后修改的日期和时间ÿ…...
【Pycharm中python调用另一个文件类或者函数】
Pycharm中python调用另一个文件类或者函数 本文主要介绍了Pycharm中python调用另一个文件类或者函数,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值,需要的朋友们下面随着小编来一起学习学习吧 文章目录 Pycha…...
pycharm操作git、前后端项目上传到gitee
pycharm操作git 之前用命令做的所有操作,使用pychrm点点就可以完成 克隆代码 上方工具栏Git ⇢ \dashrightarrow ⇢ Clone ⇢ \dashrightarrow ⇢ 填写地址(http、ssh) 提交到暂存区,提交到版本库,推送到远程 直接…...
jmeter监听每秒点击数(Hits per Second)
jmeter监听每秒点击数(Hits per Second) 下载插件添加监听器执行压测,监听结果 下载插件 点击选项,点击Plugins Manager (has upgrades),点击Available Plugins,搜索5 Additional Graphs安装。 添加监听…...
RabbitMQ 消息模型
参考 【RabbitMQ】RabbitMQ架构模型_rabbitmq结构模型-CSDN博客 之前的学习都只是知道名字,但并没有真正的理解,每次看还是不懂,所以今日理解透 ! RabbitMQ 收发消息过程如下: 首先从消费者开始࿱…...
从Wi-Fi到5G:聊聊ASK、PSK、QAM这些‘老技术’在现代通信里到底怎么用的?
从Wi-Fi到5G:ASK、PSK、QAM这些‘老技术’的现代生存指南 在咖啡馆连Wi-Fi刷视频时,很少有人会想到指尖划过的每个字节都承载着百年通信技术的智慧结晶。当5G基站闪烁着蓝色指示灯时,更少有人意识到其中运行的竟是上世纪中叶诞生的调制算法。…...
5分钟解决Windows软件运行错误:Visual C++运行库终极修复指南
5分钟解决Windows软件运行错误:Visual C运行库终极修复指南 【免费下载链接】vcredist AIO Repack for latest Microsoft Visual C Redistributable Runtimes 项目地址: https://gitcode.com/gh_mirrors/vc/vcredist 当您打开软件时突然弹出"缺少MSVCR1…...
如何用AI对话彻底改变你的Godot游戏开发:Godot-MCP终极指南
如何用AI对话彻底改变你的Godot游戏开发:Godot-MCP终极指南 【免费下载链接】Godot-MCP An MCP for Godot that lets you create and edit games in the Godot game engine with tools like Claude 项目地址: https://gitcode.com/gh_mirrors/god/Godot-MCP …...
JD-GUI:Java字节码反编译的终极图形化解决方案
JD-GUI:Java字节码反编译的终极图形化解决方案 【免费下载链接】jd-gui A standalone Java Decompiler GUI 项目地址: https://gitcode.com/gh_mirrors/jd/jd-gui 对于Java开发者来说,面对只有编译后的.class文件却需要理解其内部逻辑的情况并不少…...
结合自适应阈值NMS的YOLOv5密集目标检测:原理详解与完整代码实现
摘要 在密集目标检测场景(如行人检测、细胞检测、拥挤场景车辆检测)中,传统非极大值抑制(NMS)算法由于采用固定阈值,容易造成漏检或误检。本文提出一种结合自适应阈值NMS的YOLOv5改进方法,通过动态计算每个检测框的自适应抑制阈值,显著提升密集场景下的检测性能。文章…...
Fluent环境变量配置全解析:从原理到实践,为什么你的UDF总是编译失败?
Fluent环境变量配置全解析:从原理到实践,为什么你的UDF总是编译失败? 在工程仿真领域,Fluent的UDF(用户自定义函数)是扩展软件功能的利器,但无数工程师在配置环境变量时折戟沉沙。你是否经历过这…...
Obsidian知识管理模板:告别信息碎片化,构建你的第二大脑
Obsidian知识管理模板:告别信息碎片化,构建你的第二大脑 【免费下载链接】obsidian-template Starter templates for Obsidian 项目地址: https://gitcode.com/gh_mirrors/ob/obsidian-template 你是否经常感到信息过载?收藏的文章从未…...
Sentry 从零到一:手把手部署与多端监控实战
1. 为什么选择Sentry作为错误监控方案 第一次接触Sentry是在三年前的一个深夜,当时我们线上商城突然出现大量支付失败的问题。凌晨三点,我还在服务器日志里大海捞针般寻找线索,直到同事推荐了Sentry。接入后仅用15分钟就定位到一个未处理的第…...
5个场景让你的Mac音质焕然一新:eqMac音频均衡器完全指南
5个场景让你的Mac音质焕然一新:eqMac音频均衡器完全指南 【免费下载链接】eqMac macOS System-wide Audio Equalizer & Volume Mixer 🎧 项目地址: https://gitcode.com/gh_mirrors/eq/eqMac 还在为MacBook音质平平而烦恼?无论是视…...
Adobe-GenP 3.0终极指南:一键快速激活Adobe CC全系列软件的完整教程
Adobe-GenP 3.0终极指南:一键快速激活Adobe CC全系列软件的完整教程 【免费下载链接】Adobe-GenP Adobe CC 2019/2020/2021/2022/2023 GenP Universal Patch 3.0 项目地址: https://gitcode.com/gh_mirrors/ad/Adobe-GenP 你知道吗?对于创意工作者…...
