《数据结构、算法与应用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 收发消息过程如下: 首先从消费者开始࿱…...
手把手教你配置STM32 IAP跳转:从BootLoader关中断到APP开中断的完整流程
STM32 IAP跳转实战指南:从BootLoader到APP的中断管理全解析 引言 在嵌入式开发领域,IAP(In-Application Programming)技术为产品固件升级提供了极大便利,但其中的跳转过程却暗藏玄机。许多开发者第一次尝试实现STM32的…...
从‘毛玻璃’到‘小钢珠’:揭秘PCB铜箔粗糙度建模的认知升级与Huray方程前世今生
从‘毛玻璃’到‘小钢珠’:PCB铜箔粗糙度建模的认知革命 在高速电路设计中,信号完整性的维护犹如在风暴中保持灯塔的稳定发光。当我们把信号传输速度推向GHz级别时,PCB铜箔表面那些肉眼不可见的微观起伏,突然变成了吞噬信号能量的…...
SAP ABAP 深度剖析:COMMIT WORK 与 ROLLBACK WORK 的异步世界与同步抉择
1. 异步与同步的数据库提交机制 在SAP ABAP开发中,COMMIT WORK和ROLLBACK WORK就像数据库操作的"确认键"和"撤销键"。但很多人不知道的是,标准的COMMIT WORK实际上是个"慢性子"——它采用的是异步更新机制。这就好比你在电…...
保姆级教程:手把手教你用第三种方法修复ClickHouse只读表(附详细命令)
ClickHouse表只读状态精准修复实战指南 遇到ClickHouse表突然变成只读状态,就像开车时突然发现方向盘锁死一样让人措手不及。这种状况通常发生在ZooKeeper压力过大或元数据丢失时,但别担心,本文将带你深入理解问题本质,并掌握一种…...
ESP32 RMT驱动WS2812灯条:从官方例程到彩虹跑马灯,一份避坑指南
ESP32 RMT驱动WS2812灯条:从基础到高级特效的实战指南 当你在深夜的工作室里,看着一排WS2812灯条随着代码的节奏流淌出绚丽的色彩,那种将数字信号转化为视觉艺术的成就感,正是嵌入式开发的魅力所在。ESP32的RMT外设与WS2812的结合…...
2025届学术党必备的降AI率工具解析与推荐
Ai论文网站排名(开题报告、文献综述、降aigc率、降重综合对比) TOP1. 千笔AI TOP2. aipasspaper TOP3. 清北论文 TOP4. 豆包 TOP5. kimi TOP6. deepseek 于学术写作跟内容创作这两个领域当中,原创性方面的要求变得越发严格起来。降重网…...
从‘小隔间’到‘光晕’:用大白话拆解CCD/CMOS传感器那些事儿(附避坑指南)
从‘小隔间’到‘光晕’:用大白话拆解CCD/CMOS传感器那些事儿(附避坑指南) 想象你正用手机拍摄落日,太阳周围却糊成一团光斑;或是夜间拍照时,路灯变成了拖着长尾巴的彗星。这些让人头疼的成像问题ÿ…...
代码随想录算法训练营 Day40 | 动态规划 part13
647. 回文子串 给你一个字符串 s ,请你统计并返回这个字符串中 回文子串 的数目。 回文字符串 是正着读和倒过来读一样的字符串。 子字符串 是字符串中的由连续字符组成的一个序列。 class Solution { public:int countSubstrings(string s) {int n s.size();vecto…...
风力发电仿真避坑指南:Matlab中Pm-Wm曲线画不对?可能是这几个参数单位搞错了
风力发电仿真避坑指南:Matlab中Pm-Wm曲线画不对?可能是这几个参数单位搞错了 在风力发电系统仿真中,机械功率(Pm)与转子转速(Wm)的关系曲线是评估机组性能的核心指标。然而许多工程师在使用Matlab绘制这条关键曲线时,常会遇到结果…...
革命性PCB缺陷检测数据集:DeepPCB如何重塑电子制造业质量标准
革命性PCB缺陷检测数据集:DeepPCB如何重塑电子制造业质量标准 【免费下载链接】DeepPCB A PCB defect dataset. 项目地址: https://gitcode.com/gh_mirrors/de/DeepPCB 在电子制造业的精密世界中,PCB(印刷电路板)的微小缺陷…...
