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

_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语言实现数组队列 定义 队列的定义 队列&#xff08;queue&#xff09;是一个线性表&#xff0c;其插入和删除操作分别在表的不同端进行。插入元素的那一端称为队尾&#xff08;back或rear&#xff09;&#xff0c;删除元素的那一端称…...

零基础如何学习自动化测试

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

系统架构师备考倒计时16天(每日知识点)

1.信息化战略与实施 2.UML图&#xff08;12个&#xff09; 3.结构化设计&#xff08;耦合&#xff09; 4.SMP与AMP的区别&#xff08;多核处理器的工作方式&#xff09; 多核处理器一般有SMP和AMP两种不同的工作方式: SMP(对称多处理技术)&#xff1a;将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 &#xff08;重做日志&a…...

软考高级信息系统项目管理师系列之:信息系统项目管理师论文评分参考标准

软考高级信息系统项目管理师系列之:信息系统项目管理师论文评分参考标准 论文满分是 75 分,论文评分可分为优良、及格与不及格 3 个档次。评分的分数可分为: 60 分至 75 分优良(相当于百分制 80 分至 100 分)。45 分至 59 分及格(相当于百分制 60 分至 79 分)。0 分至 44 分…...

MyBatis--多案例让你熟练使用CRUD操作

目录 一、前期准备 二、两种实现CRUD方式 三、增加数据&#xff08;INSERT&#xff09; 四、删除数据&#xff08;DELETE&#xff09; 五、查询数据&#xff08;SELECT&#xff09; 六、更新数据&#xff08;UPDATE&#xff09; 一、前期准备 1.创建maven项目并在pom文件…...

用Python造轮子

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

ARM 堆栈寻址类型区分

文章目录 堆栈指向分类堆栈指向数据分类满递增与满递减空递增与空递减 堆栈指向分类 根据堆栈指针的指向的方向不同&#xff0c;可以划分为向上生成型和向下生成型。 向上生成型&#xff1a; 随着数据的入栈&#xff0c;堆栈的指针逐渐增大&#xff0c;称为&#xff1a;递增…...

每日一练 | 网络工程师软考真题Day43

1、在生成树协议〔STP〕IEEE 802.1d中&#xff0c;根据 来选择根交换机。 A&#xff0e;最小的MAC地址 B&#xff0e;最大的MAC地址 C&#xff0e;最小的交换机ID D&#xff0e;最大的交换机ID 2、在快速以太网物理层标准中&#xff0c;使用两对5类无屏蔽双绞线的是 。 A&…...

jsonXML格式化核心代码

json格式化&#xff1a; 依赖&#xff1a; <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量化表示训练后量化&#xff08;Post Training Quantization&#xff09;。使用一批校准数据对训练好的模型进行校准&#xff0c;将训练好的FP32网络直接转换为定点计算的网络&#xff0c;过程中无需对原始模型进行任何训练&#x…...

【Django 02】数据表构建、数据迁移与管理

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

一天吃透Java集合面试八股文

内容摘自我的学习网站&#xff1a;topjavaer.cn 常见的集合有哪些&#xff1f; Java集合类主要由两个接口Collection和Map派生出来的&#xff0c;Collection有三个子接口&#xff1a;List、Set、Queue。 Java集合框架图如下&#xff1a; List代表了有序可重复集合&#xff0c…...

高级深入--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 并选择合适的语言启动&#xff0c;所以&#xff0c;我们启动jmeter后&#xff0c;其会出现一个倍感亲切的中文界面。但由于jmeter本身的汉化工作做得不好&#xff0c;你会看到有未被汉化的选项及元件的参数。…...

黄金眼PAAS化数据服务DIFF测试工具的建设实践 | 京东云技术团队

一、背景介绍 黄金眼PAAS化数据服务是一系列实现相同指标服务协议的数据服务&#xff0c;各个服务间按照所生产指标的主题作划分&#xff0c;比如交易实时服务提供实时交易指标的查询&#xff0c;财务离线服务提供离线财务指标的查询。黄金眼PAAS化数据服务支撑了黄金眼APP、黄…...

深入了解RPA业务流程自动化的关键要素

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

CSS记录

1.标准的CSS的盒子模型&#xff1f;与低版本IE的盒子模型有什么不同的&#xff1f; 标准盒子模型box-sizing: border-box; 宽度内容的宽度&#xff08;content&#xff09; border padding margin 低版本IE盒子模型&#xff1a;宽度内容宽度&#xff08;contentborderpaddin…...

Kotlin中类型转换

在 Kotlin 中&#xff0c;类型转换是一种常见的操作&#xff0c;用于将一个数据类型转换为另一个数据类型。在本篇博客中&#xff0c;我们将介绍 Kotlin 中的类型转换&#xff0c;并提供示例代码演示智能类型转换、强制类型转换以及可空类型的转换。 智能类型转换是 Kotlin 中…...

P7557 [USACO21OPEN] Acowdemia S

典型二分&#xff1a; #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)

消失的两个数字&#xff08;hard&#xff09; 题⽬描述&#xff1a;解法&#xff08;位运算&#xff09;&#xff1a;Java 算法代码&#xff1a;更简便代码 题⽬链接&#xff1a;⾯试题 17.19. 消失的两个数字 题⽬描述&#xff1a; 给定⼀个数组&#xff0c;包含从 1 到 N 所有…...

基于当前项目通过npm包形式暴露公共组件

1.package.sjon文件配置 其中xh-flowable就是暴露出去的npm包名 2.创建tpyes文件夹&#xff0c;并新增内容 3.创建package文件夹...

新能源汽车智慧充电桩管理方案:新能源充电桩散热问题及消防安全监管方案

随着新能源汽车的快速普及&#xff0c;充电桩作为核心配套设施&#xff0c;其安全性与可靠性备受关注。然而&#xff0c;在高温、高负荷运行环境下&#xff0c;充电桩的散热问题与消防安全隐患日益凸显&#xff0c;成为制约行业发展的关键瓶颈。 如何通过智慧化管理手段优化散…...

在鸿蒙HarmonyOS 5中使用DevEco Studio实现录音机应用

1. 项目配置与权限设置 1.1 配置module.json5 {"module": {"requestPermissions": [{"name": "ohos.permission.MICROPHONE","reason": "录音需要麦克风权限"},{"name": "ohos.permission.WRITE…...

Unity | AmplifyShaderEditor插件基础(第七集:平面波动shader)

目录 一、&#x1f44b;&#x1f3fb;前言 二、&#x1f608;sinx波动的基本原理 三、&#x1f608;波动起来 1.sinx节点介绍 2.vertexPosition 3.集成Vector3 a.节点Append b.连起来 4.波动起来 a.波动的原理 b.时间节点 c.sinx的处理 四、&#x1f30a;波动优化…...

力扣-35.搜索插入位置

题目描述 给定一个排序数组和一个目标值&#xff0c;在数组中找到目标值&#xff0c;并返回其索引。如果目标值不存在于数组中&#xff0c;返回它将会被按顺序插入的位置。 请必须使用时间复杂度为 O(log n) 的算法。 class Solution {public int searchInsert(int[] nums, …...

推荐 github 项目:GeminiImageApp(图片生成方向,可以做一定的素材)

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

代码规范和架构【立芯理论一】(2025.06.08)

1、代码规范的目标 代码简洁精炼、美观&#xff0c;可持续性好高效率高复用&#xff0c;可移植性好高内聚&#xff0c;低耦合没有冗余规范性&#xff0c;代码有规可循&#xff0c;可以看出自己当时的思考过程特殊排版&#xff0c;特殊语法&#xff0c;特殊指令&#xff0c;必须…...

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 按升序排列&#xff0c;数组中的值 互不相同 。 在传递给函数之前&#xff0c;nums 在预先未知的某个下标 k&#xff08;0 < k < nums.length&#xff09;上进行了 旋转&#xff0c;使数组变为 [nums[k], nums[k1], …, nums[n-1], nums[0], nu…...