《数据结构、算法与应用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
_18arrayQueue.h
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 数组存储的队列的头文件
*/
#pragma once
#ifndef _ARRAYQUEUE_H_
#define _ARRAYQUEUE_H_
#include<sstream>
#include<iostream>
#include "_1myExceptions.h"
#include "_17queue.h"
#include <cmath>
/*测试函数*/
void arrayQueueTest();using namespace std;
template<class T>
class arrayQueue : public queue<T>
{
public:/*成员函数*/arrayQueue(int initialCapacity = 10);~arrayQueue() { delete[] queue; }bool empty() const { return theFront == theBack; }int size() const //返回队列的元素个数{return (queueLength - theFront + theBack) % queueLength;}void clear() { theFront = theBack = 0; }/*清空队列中的元素*/int capacity() const { return queueLength-1; }//返回第一个元素T& front(){if (theFront == theBack)throw queueEmpty();return queue[(theFront + 1) % queueLength];}//返回最后一个元素T& back(){if (theFront == theBack)throw queueEmpty();return queue[theBack];}//删除队首元素void pop(){if (theFront == theBack)throw queueEmpty();theFront = (theFront + 1) % queueLength;queue[theFront].~T();}//向队尾插入元素theElementvoid push(const T& theElement);/*调整队列容量大小*/void resizeQueue(int newLength);void meld(arrayQueue<T>& a, arrayQueue<T>& b);//合并队列a,b到当前队列void split(arrayQueue<T>& a, arrayQueue<T>& b);//将当前队列分成两个队列a,b/*重载操作符*//*重载[]操作符*/T operator[](int i){ return queue[(theFront + i + 1) % queueLength]; }/*友元函数*/friend istream& operator>> <T>(istream& in, arrayQueue<T>& m);//输出但是不pop()元素friend ostream& operator<< <T>(ostream& out, arrayQueue<T>& m);
private:int theFront; // 第一个元素的前一个位置int theBack; // 最后一个元素的位置int queueLength; // 队列的容量,实质上比队列容量(不包含queueFront指向的那一个位置)大1T* queue; // 指向队列首地址的指针
};
/*友元函数*/
/*>>操作符*/
template<class T>
istream& operator>>(istream& in, arrayQueue<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;
}
/*<<操作符*/
template<class T>
ostream& operator<<(ostream& out, arrayQueue<T>& m)
{int size = m.size();for (int i = 0; i < size; i++)out << m.queue[(m.theFront + i + 1) % m.queueLength] << " ";out << endl;return out;
}
/*成员函数*/
/*构造函数*/
template<class T>
arrayQueue<T>::arrayQueue(int initialCapacity)
{if (initialCapacity < 1){ostringstream s("");s << "Initial capacity = " << initialCapacity << "Must be > 0";throw illegalParameterValue(s.str());}queue = new T[initialCapacity+1];queueLength = initialCapacity+1;theFront = theBack = 0;
}/*向队尾插入元素theElement*/
template<class T>
void arrayQueue<T>::push(const T& theElement)
{//首先检查队列是否已满,如已满,则将队列容量加倍if ((theBack + 1) % queueLength == theFront)resizeQueue(2 * (queueLength-1)); theBack = (theBack + 1) % queueLength;queue[theBack] = theElement;
}
/*调整队列容量大小*/
template<class T>
void arrayQueue<T>::resizeQueue(int newLength)
{T* temp = new T[newLength + 1];int size = min((*this).size(), newLength);for (int i = 0; i < size; i++)temp[i] = queue[(theFront + i + 1) % queueLength]; queueLength = newLength+1;theFront = newLength;theBack = size - 1;delete[] queue;queue = temp;
}/*
创建一个新的队列,该表包含了a和b中的所有元素,其中a和b的元素轮流出现,表中的首
元素为a中的第一个元素。在轮流排列元素时,如果某个队列的元素用完了,则把另一个队列的其
余元素依次添加在新队列的后部。代码的复杂性应与两个输入队列的长度呈线性比例关系。
归并后的线性队列是调用对象*this
*/
template <class T>
void arrayQueue<T>::meld(arrayQueue<T>& a, arrayQueue<T>& b)
{(*this).clear();int i = 0;while (i < a.size() && i < b.size()){push(a[i]);push(b[i]);i++;}while (i < a.size()){push(a[i]);i++;}while (i < b.size()){push(b[i]);i++;}
}/*生成两个线性队列a和b,a包含*this中索引为奇数的元素,b包含其余的元素*/
template<class T>
void arrayQueue<T>::split(arrayQueue<T>& a, arrayQueue<T>& b)
{a.clear();b.clear();int size = (*this).size();for (int i = 0; i < size; i++){if (i % 2 == 0)a.push(queue[(theFront + i + 1) % queueLength]);elseb.push(queue[(theFront + i + 1) % queueLength]);}
}
#endif
_18arrayQueue.cpp
/*
Project name : allAlgorithmsTest
Last modified Date: 2022年8月13日17点38分
Last Version: V1.0
Descriptions: 测试_18arrayQueue.h头文件中的所有函数
*/
#include <iostream>
#include <time.h>
#include "_18arrayQueue.h"
using namespace std;/*测试函数*/
void arrayQueueTest()
{cout << endl << "*********************************arrayQueueTest()函数开始*************************************" << endl;arrayQueue<int> a;//测试输入和输出cout << endl << "测试友元函数*******************************************" << endl;cout << "输入输出************************" << endl;cin >> a;cout << "arrayQueue 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 << "capacity()**********************" << endl;cout << "a.capacity() = " << a.capacity() << endl;cout << "push()**************************" << endl;cout << "arrayQueue a is:" << a;a.push(99);a.push(22);cout << "arrayQueue 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 arrayQueue a is:" << a;a.pop();a.pop();cout << "after pop arrayQueue a is:" << a;cout << "resizeQueue()*******************" << endl;cout << "before resizeQueue a.capacity() = " << a.capacity()<<endl;a.resizeQueue(4);cout << "after resizeQueue a.capacity() = " << a.capacity() << endl;cout << "arrayQueue a is:" << a;cout << "a.front() = " << a.front() << endl;cout << "a.back() = " << a.back() << endl;a.push(88);cout << "after resizeQueue a.capacity() = " << a.capacity() << endl;cout << "meld()**************************" << endl;arrayQueue<int> b;cin >> b;cout << "arrayQueue a is:" << a;cout << "arrayQueue b is:" << b;arrayQueue<int> c;c.meld(a, b);cout << "arrayQueue c is:" << c;cout << "split()*************************" << endl;arrayQueue<int> d;arrayQueue<int> e;c.split(d, e);cout << "arrayQueue c is:" << c;cout << "arrayQueue d is:" << d; cout << "arrayQueue e is:" << e;cout << endl << "测试成员函数性能***************************************" << endl;cout << "push()**************************" << endl;arrayQueue<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 << "*********************************arrayQueueTest()函数结束*************************************" << 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),删除元素的那一端称…...

零基础如何学习自动化测试
现在很多测试人员有些急于求成,没有任何基础想当然的,要在一周内上手自动化测试。 在自动化的过程中时候总有人会犯很低级的问题,有语法问题,有定位问题,而且有人居然连__init__.py 文件名都弄错误,还有将…...

系统架构师备考倒计时16天(每日知识点)
1.信息化战略与实施 2.UML图(12个) 3.结构化设计(耦合) 4.SMP与AMP的区别(多核处理器的工作方式) 多核处理器一般有SMP和AMP两种不同的工作方式: SMP(对称多处理技术):将2颗完全一样的处理器封…...

【MySQL系列】- Select查询SQL执行过程详解
【MySQL系列】- Select查询SQL执行过程详解 文章目录 【MySQL系列】- Select查询SQL执行过程详解一、SQL查询语句的执行过程二、SQL执行过程详解2.1. 连接器2.2. 查询缓存2.3. 分析器2.4. 优化器2.5. 执行器 三、undo log 和 redo log作⽤3.1. redo log (重做日志&a…...
软考高级信息系统项目管理师系列之:信息系统项目管理师论文评分参考标准
软考高级信息系统项目管理师系列之:信息系统项目管理师论文评分参考标准 论文满分是 75 分,论文评分可分为优良、及格与不及格 3 个档次。评分的分数可分为: 60 分至 75 分优良(相当于百分制 80 分至 100 分)。45 分至 59 分及格(相当于百分制 60 分至 79 分)。0 分至 44 分…...

MyBatis--多案例让你熟练使用CRUD操作
目录 一、前期准备 二、两种实现CRUD方式 三、增加数据(INSERT) 四、删除数据(DELETE) 五、查询数据(SELECT) 六、更新数据(UPDATE) 一、前期准备 1.创建maven项目并在pom文件…...

用Python造轮子
目录 背景安装setuptools库准备要打包的代码创建setup.py文件打包生成whl文件把库装到电脑上使用这个库 背景 如何把自己写的代码,打包成库方便其他人使用 安装setuptools库 正所谓想要富先修路,先把造轮子要用的库装上 pip install wheel pip insta…...

ARM 堆栈寻址类型区分
文章目录 堆栈指向分类堆栈指向数据分类满递增与满递减空递增与空递减 堆栈指向分类 根据堆栈指针的指向的方向不同,可以划分为向上生成型和向下生成型。 向上生成型: 随着数据的入栈,堆栈的指针逐渐增大,称为:递增…...
每日一练 | 网络工程师软考真题Day43
1、在生成树协议〔STP〕IEEE 802.1d中,根据 来选择根交换机。 A.最小的MAC地址 B.最大的MAC地址 C.最小的交换机ID D.最大的交换机ID 2、在快速以太网物理层标准中,使用两对5类无屏蔽双绞线的是 。 A&…...
jsonXML格式化核心代码
json格式化: 依赖: <dependency><groupId>com.jayway.jsonpath</groupId><artifactId>json-path</artifactId><version>2.6.0</version><scope>compile</scope> </dependency> string t…...

PTQ量化和QAT量化
目录 1--PTQ量化 2--QAT量化 1--PTQ量化 PTQ量化表示训练后量化(Post Training Quantization)。使用一批校准数据对训练好的模型进行校准,将训练好的FP32网络直接转换为定点计算的网络,过程中无需对原始模型进行任何训练&#x…...

【Django 02】数据表构建、数据迁移与管理
1. Django 构建数据表创建与数据迁移 1.1 数据表创建 1.1.1 模块功能 如前所述,models.py文件主要用一个 Python 类来描述数据表。运用这个类,可以通过简单的 Python 代码来创建、检索、更新、删除 数据库中的记录而无需写一条又一条的SQL语句。今天的例子就是在…...

一天吃透Java集合面试八股文
内容摘自我的学习网站:topjavaer.cn 常见的集合有哪些? Java集合类主要由两个接口Collection和Map派生出来的,Collection有三个子接口:List、Set、Queue。 Java集合框架图如下: List代表了有序可重复集合,…...
高级深入--day36
Settings Scrapy设置(settings)提供了定制Scrapy组件的方法。可以控制包括核心(core),插件(extension),pipeline及spider组件。比如 设置Json Pipeliine、LOG_LEVEL等。 参考文档:Settings — Scrapy 1.0.5 文档 内置设置参考手册 BOT_NAME 默认: scrapybot 当您使用 sta…...

Jmeter接口测试工具的一些使用小技巧
如何使用英文界面的JMeter Jmeter启动时会自动判断操作系统的locale 并选择合适的语言启动,所以,我们启动jmeter后,其会出现一个倍感亲切的中文界面。但由于jmeter本身的汉化工作做得不好,你会看到有未被汉化的选项及元件的参数。…...

黄金眼PAAS化数据服务DIFF测试工具的建设实践 | 京东云技术团队
一、背景介绍 黄金眼PAAS化数据服务是一系列实现相同指标服务协议的数据服务,各个服务间按照所生产指标的主题作划分,比如交易实时服务提供实时交易指标的查询,财务离线服务提供离线财务指标的查询。黄金眼PAAS化数据服务支撑了黄金眼APP、黄…...

深入了解RPA业务流程自动化的关键要素
在RPA业务流程自动化实施过程中,哪些因素起着至关重要的作用?这其实没有一个通用的答案,每一个RPA业务流程自动化的部署,都需要结合具体场景去调整,并且进行全面的规划。 首当其冲是要关注以下几点: 1、专…...

CSS记录
1.标准的CSS的盒子模型?与低版本IE的盒子模型有什么不同的? 标准盒子模型box-sizing: border-box; 宽度内容的宽度(content) border padding margin 低版本IE盒子模型:宽度内容宽度(contentborderpaddin…...
Kotlin中类型转换
在 Kotlin 中,类型转换是一种常见的操作,用于将一个数据类型转换为另一个数据类型。在本篇博客中,我们将介绍 Kotlin 中的类型转换,并提供示例代码演示智能类型转换、强制类型转换以及可空类型的转换。 智能类型转换是 Kotlin 中…...
P7557 [USACO21OPEN] Acowdemia S
典型二分: #include<bits/stdc.h> using namespace std; #define int long long const int N1e510; int n,a[N],k,l; bool check(int x) {int cnt0,ans0;for(int i1; i<x; i) {if(a[i]>x) {cnt;continue;}else{if(x-a[i]>k)return false;else{ansans…...
【位运算】消失的两个数字(hard)
消失的两个数字(hard) 题⽬描述:解法(位运算):Java 算法代码:更简便代码 题⽬链接:⾯试题 17.19. 消失的两个数字 题⽬描述: 给定⼀个数组,包含从 1 到 N 所有…...

基于当前项目通过npm包形式暴露公共组件
1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹,并新增内容 3.创建package文件夹...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案
随着新能源汽车的快速普及,充电桩作为核心配套设施,其安全性与可靠性备受关注。然而,在高温、高负荷运行环境下,充电桩的散热问题与消防安全隐患日益凸显,成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...
在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用
1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)
目录 一、👋🏻前言 二、😈sinx波动的基本原理 三、😈波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、🌊波动优化…...
力扣-35.搜索插入位置
题目描述 给定一个排序数组和一个目标值,在数组中找到目标值,并返回其索引。如果目标值不存在于数组中,返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)
推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材) 这个项目能干嘛? 使用 gemini 2.0 的 api 和 google 其他的 api 来做衍生处理 简化和优化了文生图和图生图的行为(我的最主要) 并且有一些目标检测和切割(我用不到) 视频和 imagefx 因为没 a…...

代码规范和架构【立芯理论一】(2025.06.08)
1、代码规范的目标 代码简洁精炼、美观,可持续性好高效率高复用,可移植性好高内聚,低耦合没有冗余规范性,代码有规可循,可以看出自己当时的思考过程特殊排版,特殊语法,特殊指令,必须…...

android RelativeLayout布局
<?xml version"1.0" encoding"utf-8"?> <RelativeLayout xmlns:android"http://schemas.android.com/apk/res/android"android:layout_width"match_parent"android:layout_height"match_parent"android:gravity&…...
Leetcode33( 搜索旋转排序数组)
题目表述 整数数组 nums 按升序排列,数组中的值 互不相同 。 在传递给函数之前,nums 在预先未知的某个下标 k(0 < k < nums.length)上进行了 旋转,使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...