当前位置: 首页 > news >正文

【数据结构】实验六:队列

实验六  队列

一、实验目的与要求

1)熟悉C/C++语言(或其他编程语言)的集成开发环境;

2)通过本实验加深对队列的理解,熟悉基本操作;

3  结合具体的问题分析算法时间复杂度。

二、实验内容

  设计你的循环队列实现。 循环队列是一种线性数据结构,其操作表现基于 FIFO(先进先出)原则并且队尾被连接在队首之后以形成一个循环。它也被称为“环形缓冲器”。

  循环队列的一个好处是我们可以利用这个队列之前用过的空间。在一个普通队列里,一旦一个队列满了,我们就不能插入下一个元素,即使在队列前面仍有空间。但是使用循环队列,我们能使用这些空间去存储新的值。

你的实现应该支持如下操作:

MyCircularQueue(k): 构造器,设置队列长度为 k 。

Front: 从队首获取元素。如果队列为空,返回 -1 。

Rear: 获取队尾元素。如果队列为空,返回 -1 。

enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。

deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。

isEmpty(): 检查循环队列是否为空。

isFull(): 检查循环队列是否已满。

三、实验结果

1)请将调试通过的源代码粘贴在下面。(代码注意书写规范、主要模块要有功能注释)

源代码:

#include <iostream>
using namespace std;template <typename T>
class MyCircularQueue{T * data;//当前位置的数据 int front,rear,size;//头指针、尾指针、队列长度 
public://MyCircularQueue(k): 构造器,设置队列长度为 k 。MyCircularQueue(int k=0){data=new T[k+1];//k+1 -> 区分isEmpty和isFull的判断条件 front=rear=0;size=k+1;}//Front: 从队首获取元素。如果队列为空,返回 -1 。T Front(){if(isEmpty()){return -1;}else{return data[front];}}//Rear: 获取队尾元素。如果队列为空,返回 -1 。T Rear(){if(isEmpty()){return -1;}else{return data[rear-1];}}//enQueue(value): 向循环队列插入一个元素。如果成功插入则返回真。bool enQueue(T value){if(isFull()){return 0;}else{data[rear]=value;rear=(rear+1)%size;return 1;}} //deQueue(): 从循环队列中删除一个元素。如果成功删除则返回真。bool deQueue(){if(isEmpty()){return 0;}else{front=(front+1)%size;return 1;}}//isEmpty(): 检查循环队列是否为空。bool isEmpty(){if(rear==front){return 1;}else{return 0;}}//isFull(): 检查循环队列是否已满。bool isFull(){if((rear+1)%size==front){return 1;}else{return 0;}}
};int main(){//初始化循环链表int len;cout<<"Please input the length of your queue"<<endl;cin>>len; MyCircularQueue <int> queue(len);//查看空表 if(queue.isEmpty() ==1){cout<<"The current queue is empty"<<endl;}else{cout<<"The current queue is not empty"<<endl;}cout<<"The front now is "<<queue.Front() <<endl;cout<<"The rear now is "<<queue.Rear() <<endl;cout<<endl;//输入元素 int times;cout<<"Please select the times you want to input"<<endl;cin>>times;int i=0;for(;i<times;i++){int value;cout<<"Please input your value"<<endl;cin>>value;int t=queue.enQueue(value); if(t==1){cout<<"Valid input"<<endl;}else{cout<<"Invalid input"<<endl;break;}}cout<<endl;//判断输入后的情况 if(queue.isEmpty() ==1){cout<<"The current queue is empty"<<endl;}else{cout<<"The current queue is not empty"<<endl;}cout<<"The front now is "<<queue.Front() <<endl;cout<<"The rear now is "<<queue.Rear() <<endl;cout<<endl;//删除元素 int dels;cout<<"Please select the times you want to delete"<<endl;cin>>dels;int ii=0;for(;ii<dels;ii++){int tt=queue.deQueue(); if(tt==1){cout<<"Valid delete"<<endl;}else{cout<<"Invalid delete"<<endl;break;}}cout<<endl;//判断删除后的情况if(queue.isEmpty() ==1){cout<<"The current queue is empty"<<endl;}else{cout<<"The current queue is not empty"<<endl;}cout<<"The front now is "<<queue.Front() <<endl;cout<<"The rear now is "<<queue.Rear() <<endl;cout<<endl;return 0;
}

结果展示:

2)请分析你程序中每个功能模块的算法时间复杂度。

构造循环队列,只需要设置队列长度为k+1并设置相应数组,同时初始头指针和尾指针为0即可。所以,时间复杂度为O(1)。

判断循环队列是否为空队列,只需要判断头指针是否与尾指针重合即可,即return(rear==front)。所以,时间复杂度为O(1)。

判断循环队列是否为空队列,只需要判断尾指针加一取余后是否与头指针重合即可,即return((rear+1)%size==front)。所以,时间复杂度为O(1)。

获取队首元素,只需要先判断循环队列是否为空队列,如果队列非空则直接返回头指针所对应的元素。所以,时间复杂度为O(1)。

获取队尾元素,只需要先判断循环队列是否为空队列,如果队列非空则直接返回尾指针所对应的元素。所以,时间复杂度为O(1)。

向循环队列插入一个元素,只需要先判断循环队列是否为满队列,如果队列非满则直接插入输入元素并重置尾指针。所以,时间复杂度为O(1)。

从循环队列中删除一个元素,只需要先判断循环队列是否为空队列,如果队列非空则直接改变头指针的位置,即可删除队首元素。所以,时间复杂度为O(1)。

 


其他:

#include<stdlib.h>
#include<iostream>
using namespace std;
#define SIZE 6
#define Type char
typedef struct{Type *elem;int front,rear,length;//注意,队列的所谓的指针不是指针,是int 
}Queue;
bool isEmpty(Queue &Q)//: 检查循环队列是否为空。
{if(Q.rear==Q.front){return 1;}else{return 0;}
}
bool isFull(Queue &Q)//: 检查循环队列是否已满。
{if((Q.rear+1)%Q.length==Q.front){return true;}else{return false;}
}
void MyCircularQueue(Queue &Q,int k)//: 构造器,设置队列长度为 k 。
{Q.length=k;Q.elem=new Type[Q.length];Q.front=Q.rear=0;cout<<"长度为k的队列构造完毕"<<endl;
}
int Front(Queue &Q,Type &e)//: 从队首获取元素。如果队列为空,返回 -1 。
{if(isEmpty(Q)){cout<<"空队列"<<endl; return -1;}else{e=Q.elem[Q.front];cout<<"非空"<<endl; cout<<"队首元素"<<e<<"获取成功"<<endl;return 1;}
}
int Rear(Queue &Q,Type &e)//: 获取队尾元素。如果队列为空,返回 -1 。
{if(isEmpty(Q)){cout<<"空队列"<<endl;return -1;}else{cout<<"非空"<<endl;if(Q.rear==0){e=Q.elem[5];cout<<"队尾元素"<<e<<"获取成功"<<endl;return 1;}else{e=Q.elem[Q.rear-1];cout<<"队尾元素"<<e<<"获取成功"<<endl;return 1;}}
}
bool enQueue(Queue &Q,Type value)//: 向循环队列插入一个元素。如果成功插入则返回真。
{if(!isFull(Q)){cout<<"非满"<<endl;Q.elem[Q.rear]=value;//因为初始front和rear都是0开头,所以与下标一致 Q.rear=(1+Q.rear)%Q.length;cout<<value<<"已经插入"<<endl;return true;}else{cout<<"队列已满!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<<value<<"无法入队"<<endl; return false;}
}
int deQueue(Queue &Q,Type &e)//: 从循环队列中删除一个元素。如果成功删除则返回真。
{if(isEmpty(Q)){cout<<"已空"<<endl;return -1;}else{cout<<"非空"<<endl;e=Q.elem[Q.front];Q.front=(Q.front+1)%Q.length;cout<<"删除了"<<e<<endl;return 1;}
}
int getlength(Queue &Q)
{int len;len=(Q.rear-Q.front+Q.length)%Q.length;return len;
}
int main()
{Queue a;Type temp;Type e[11]={'a','b','c','d','e','f','g','h','i','j','k'};int length=SIZE;MyCircularQueue(a,length);//初始化 enQueue(a,e[0]);//入队,到第一次满 enQueue(a,e[1]);enQueue(a,e[2]);enQueue(a,e[3]);enQueue(a,e[4]);if(isFull(a))//判断是否已满 {cout<<"队列已满!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!!"<<endl;} deQueue(a,temp);//删除队首 Front(a,temp);//输出队首队尾元素 Rear(a,temp);enQueue(a,e[5]);//插入两次,看看当队列已满,溢出时的效果  证明了程序在溢出时的插入无效 enQueue(a,e[6]);//队列以满,试图插入的这个是g,查看满后队列是否可以阻止进入 cout<<"该队列长度为"<<getlength(a)<<endl; Front(a,temp);//再次确定   1.队列确实是循环使用的,即0号位被再次利用   2.溢出的那一次插入无效 Rear(a,temp);
} 

相关文章:

【数据结构】实验六:队列

实验六 队列 一、实验目的与要求 1&#xff09;熟悉C/C语言&#xff08;或其他编程语言&#xff09;的集成开发环境&#xff1b; 2&#xff09;通过本实验加深对队列的理解&#xff0c;熟悉基本操作&#xff1b; 3&#xff09; 结合具体的问题分析算法时间复杂度。 二、…...

【Linux线程】第一章||理解线程概念+创建一个线程(附代码加讲解)

线程概念 &#x1f335;什么是线程&#x1f332;线程和进程的关系&#x1f384;线程有以下特点&#xff1a;&#x1f333; 线程的优点&#x1f334; 线程的缺点&#x1f331;线程异常&#x1f33f;线程用途 ☘️手动创建一个进程&#x1f340;运行 &#x1f335;什么是线程 在L…...

Android进阶之微信扫码登录

遇到新需求要搭建微信扫码登录功能,这篇文章是随着我的编码过程一并写的,希望能够帮助有需求的人和以后再次用到此功能的自己。 首先想到的就是百度各种文章,当然去开发者平台申请AppID和密钥是必不可少的,等注册好发现需要创建应用以及审核(要官网,流程图及其他信息),想着先写…...

macOS Monterey 12.6.8 (21G725) Boot ISO 原版可引导镜像

macOS Monterey 12.6.8 (21G725) Boot ISO 原版可引导镜像 本站下载的 macOS 软件包&#xff0c;既可以拖拽到 Applications&#xff08;应用程序&#xff09;下直接安装&#xff0c;也可以制作启动 U 盘安装&#xff0c;或者在虚拟机中启动安装。另外也支持在 Windows 和 Lin…...

Unity自定义后处理——用偏导数求图片颜色边缘

大家好&#xff0c;我是阿赵。   继续介绍屏幕后处理效果的做法。这次介绍一下用偏导数求图形边缘的技术。 一、原理介绍 先来看例子吧。   这个例子看起来好像是要给模型描边。之前其实也介绍过很多描边的方法&#xff0c;比如沿着法线方向放大模型&#xff0c;或者用Ndo…...

本地Git仓库和GitHub仓库SSH传输

SSH创建命令解释 ssh-keygen 用于创建密钥的程序 -m PEM 将密钥的格式设为 PEM -t rsa 要创建的密钥类型&#xff0c;本例中为 RSA 格式 -b 4096 密钥的位数&#xff0c;本例中为 4096 -C “azureusermyserver” 追加到公钥文件末尾以便于识别的注释。 通常以电子邮件地址…...

【C++11】——右值引用、移动语义

目录 1. 基本概念 1.1 左值与左值引用 1.2 右值和右值引用 1.3 左值引用与右值引用 2. 右值引用实用场景和意义 2.1 左值引用的使用场景 2.2 左值引用的短板 2.3 右值引用和移动语义 2.3.1 移动构造 2.3.2 移动赋值 2.3.3 编译器做的优化 2.3.4 总结 2.4 右值引用…...

消息服务概述

消息服务的作用&#xff1a; 在多数应用尤其是分布式系统中&#xff0c;消息服务是不可或缺的重要部分&#xff0c;它使用起来比较简单&#xff0c;同时解决了不少难题&#xff0c;例如异步处理、应用解耦、流量削锋、分布式事务管理等&#xff0c;使用消息服务可以实现一个高…...

【Spring Boot】Web开发 — 数据验证

Web开发 — 数据验证 对于应用系统而言&#xff0c;任何客户端传入的数据都不是绝对安全有效的&#xff0c;这就要求我们在服务端接收到数据时也对数据的有效性进行验证&#xff0c;以确保传入的数据安全正确。接下来介绍Spring Boot是如何实现数据验证的。 1.Hibernate Vali…...

技术分享 | App常见bug解析

功能Bug 内容显示错误 前端页面展示的内容有误。 这种错误的产生有两种可能 1、前端代码写的文案错误 2、接口返回值错误 功能错误 功能错误是在测试过程中最常见的类型之一&#xff0c;也就是产品的功能没有实现。比如图中的公众号登录不成功的问题。 界面展示错乱 产…...

树莓派Pico|RP2040|使用SWD进行调试|构建 “Hello World“ debug版本

文章目录 使用SWD进行调试构建 "Hello World" debug版本安装 GDB使用 GDB 和 OpenOCD 来 debug Hello World TIP重要提示 使用SWD进行调试 基于rp2040的板上的SWD端口重置&#xff0c;加载和运行代码&#xff0c;如树莓派Pico可用于交互式调试已加载的程序。这包括:…...

Ubuntu18.04 下配置Clion

配置Clion 安装gcc、g、make Ubuntu中用到的编译工具是gcc©&#xff0c;g&#xff08;C&#xff09;&#xff0c;make(连接)。因此只需安装对应的工具包即可。Ubuntu下使用命令安装这些包&#xff1a; &#xff08;1&#xff09;安装gcc sudo apt install gcc&am…...

数据库管理-第九十四期 19c OCM之路-第四堂(02)(20230725)

第九十四期 19c OCM之路-第四堂&#xff08;02&#xff09;&#xff08;20230725&#xff09; 第四堂继续&#xff01; 考点3&#xff1a;SQL statement tuning SQL语句调优 收集Schema统计信息 exec dbms_stats.gather_schems_stats(HR);开启制定表索引监控 create index…...

以智慧监测模式守护燃气安全 ,汉威科技“传感芯”凸显智慧力

城市燃气工程作为城市基建的重要组成部分&#xff0c;与城市居民生活、工业生产紧密相关。提升城市燃气服务质量和安全水平&#xff0c;也一直是政府和民众关注的大事。然而&#xff0c;近年来居民住宅、餐饮等工商业场所燃气事故频发&#xff0c;时刻敲响的警钟也折射出我国在…...

【阅读笔记】一种暗通道优先的快速自动白平衡算法

解决问题: 自动白平衡算法中存在白色区域检测错误导致白平衡失效的问题,作者提出了一种基于暗通道优先的白平衡算法。 算法思想: 图像中白色区域或者高饱和度区域的光线透射率较低,根据以上特性利用暗通道法计算图像中白色区域。 算法概述: 作者使用何凯明提出的基于暗…...

OpenStack之云主机管理

一&#xff09;必备知识 1.云主机与快照管理 a-云主机管理 云主机管理是OpenStack云计算平台的核心功能&#xff0c;通常&#xff0c;云主机的管理包括创建、删除、查询等。可使用以下命令对OpenStack的云主机进行管理&#xff1a; openstack server <操作><云主机…...

Linux系列---【Ubuntu 20.04安装KVM】

Ubuntu 20.04安装KVM 一、安装kvm 1.安装kvm sudo apt install qemu-kvm libvirt-daemon-system libvirt-clients bridge-utils 2. 将当前用户添加至libvirt 、 kvm组 sudo adduser $USER libvirt sudo adduser $USER kvm 3.验证安装 virsh list --all 4.启动libvert sudo syst…...

【Vue3】局部组件和全局组件

1. 局部组件 Card.vue <template><div class"card"><header><div>标题</div><div>副标题</div></header><section>内容</section></div> </template><script setup lang"ts"…...

vscode开发Go和Java

vscode开发Go和Java 最新最全 vscode 插件推荐可以参考&#xff1a; https://zhuanlan.zhihu.com/p/623580867 1、公共插件安装 下面是个人使用的插件&#xff1a; # 中文插件 Chinese (Simplified) (简体中文) Language Pack for Visual Studio Code https://marketplace…...

自定义MVC

目录 一.什么是MVC 1.1.三层架构和MVC的区别 二.自定义MVC工作原理图 三.自定义mvc实现 3.1 创建web工程 3.2 中央处理器 3.3 Action接口定义 3.4 实现子控制器 3.5 完善中央控制器 3.5.1 请求分发功能 3.5.2 使用配置文件配置action 3.5.3 请求参数处理 1. 定义接…...

JavaSec-RCE

简介 RCE(Remote Code Execution)&#xff0c;可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景&#xff1a;Groovy代码注入 Groovy是一种基于JVM的动态语言&#xff0c;语法简洁&#xff0c;支持闭包、动态类型和Java互操作性&#xff0c…...

大数据学习栈记——Neo4j的安装与使用

本文介绍图数据库Neofj的安装与使用&#xff0c;操作系统&#xff1a;Ubuntu24.04&#xff0c;Neofj版本&#xff1a;2025.04.0。 Apt安装 Neofj可以进行官网安装&#xff1a;Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...

椭圆曲线密码学(ECC)

一、ECC算法概述 椭圆曲线密码学&#xff08;Elliptic Curve Cryptography&#xff09;是基于椭圆曲线数学理论的公钥密码系统&#xff0c;由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA&#xff0c;ECC在相同安全强度下密钥更短&#xff08;256位ECC ≈ 3072位RSA…...

前端开发面试题总结-JavaScript篇(一)

文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包&#xff08;Closure&#xff09;&#xff1f;闭包有什么应用场景和潜在问题&#xff1f;2.解释 JavaScript 的作用域链&#xff08;Scope Chain&#xff09; 二、原型与继承3.原型链是什么&#xff1f;如何实现继承&a…...

08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险

C#入门系列【类的基本概念】&#xff1a;开启编程世界的奇妙冒险 嘿&#xff0c;各位编程小白探险家&#xff01;欢迎来到 C# 的奇幻大陆&#xff01;今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类&#xff01;别害怕&#xff0c;跟着我&#xff0c;保准让你轻松搞…...

jmeter聚合报告中参数详解

sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample&#xff08;样本数&#xff09; 表示测试中发送的请求数量&#xff0c;即测试执行了多少次请求。 单位&#xff0c;以个或者次数表示。 示例&#xff1a;…...

c# 局部函数 定义、功能与示例

C# 局部函数&#xff1a;定义、功能与示例 1. 定义与功能 局部函数&#xff08;Local Function&#xff09;是嵌套在另一个方法内部的私有方法&#xff0c;仅在包含它的方法内可见。 • 作用&#xff1a;封装仅用于当前方法的逻辑&#xff0c;避免污染类作用域&#xff0c;提升…...

多元隐函数 偏导公式

我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式&#xff0c;给定一个隐函数关系&#xff1a; F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 &#x1f9e0; 目标&#xff1a; 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z​、 …...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...

DeepSeek越强,Kimi越慌?

被DeepSeek吊打的Kimi&#xff0c;还有多少人在用&#xff1f; 去年&#xff0c;月之暗面创始人杨植麟别提有多风光了。90后清华学霸&#xff0c;国产大模型六小虎之一&#xff0c;手握十几亿美金的融资。旗下的AI助手Kimi烧钱如流水&#xff0c;单月光是投流就花费2个亿。 疯…...