【数据结构】实验六:队列
实验六 队列
一、实验目的与要求
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)熟悉C/C语言(或其他编程语言)的集成开发环境; 2)通过本实验加深对队列的理解,熟悉基本操作; 3) 结合具体的问题分析算法时间复杂度。 二、…...

【Linux线程】第一章||理解线程概念+创建一个线程(附代码加讲解)
线程概念 🌵什么是线程🌲线程和进程的关系🎄线程有以下特点:🌳 线程的优点🌴 线程的缺点🌱线程异常🌿线程用途 ☘️手动创建一个进程🍀运行 🌵什么是线程 在L…...
Android进阶之微信扫码登录
遇到新需求要搭建微信扫码登录功能,这篇文章是随着我的编码过程一并写的,希望能够帮助有需求的人和以后再次用到此功能的自己。 首先想到的就是百度各种文章,当然去开发者平台申请AppID和密钥是必不可少的,等注册好发现需要创建应用以及审核(要官网,流程图及其他信息),想着先写…...

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

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

本地Git仓库和GitHub仓库SSH传输
SSH创建命令解释 ssh-keygen 用于创建密钥的程序 -m PEM 将密钥的格式设为 PEM -t rsa 要创建的密钥类型,本例中为 RSA 格式 -b 4096 密钥的位数,本例中为 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 右值引用…...

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

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

技术分享 | App常见bug解析
功能Bug 内容显示错误 前端页面展示的内容有误。 这种错误的产生有两种可能 1、前端代码写的文案错误 2、接口返回值错误 功能错误 功能错误是在测试过程中最常见的类型之一,也就是产品的功能没有实现。比如图中的公众号登录不成功的问题。 界面展示错乱 产…...
树莓派Pico|RP2040|使用SWD进行调试|构建 “Hello World“ debug版本
文章目录 使用SWD进行调试构建 "Hello World" debug版本安装 GDB使用 GDB 和 OpenOCD 来 debug Hello World TIP重要提示 使用SWD进行调试 基于rp2040的板上的SWD端口重置,加载和运行代码,如树莓派Pico可用于交互式调试已加载的程序。这包括:…...

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

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

以智慧监测模式守护燃气安全 ,汉威科技“传感芯”凸显智慧力
城市燃气工程作为城市基建的重要组成部分,与城市居民生活、工业生产紧密相关。提升城市燃气服务质量和安全水平,也一直是政府和民众关注的大事。然而,近年来居民住宅、餐饮等工商业场所燃气事故频发,时刻敲响的警钟也折射出我国在…...

【阅读笔记】一种暗通道优先的快速自动白平衡算法
解决问题: 自动白平衡算法中存在白色区域检测错误导致白平衡失效的问题,作者提出了一种基于暗通道优先的白平衡算法。 算法思想: 图像中白色区域或者高饱和度区域的光线透射率较低,根据以上特性利用暗通道法计算图像中白色区域。 算法概述: 作者使用何凯明提出的基于暗…...
OpenStack之云主机管理
一)必备知识 1.云主机与快照管理 a-云主机管理 云主机管理是OpenStack云计算平台的核心功能,通常,云主机的管理包括创建、删除、查询等。可使用以下命令对OpenStack的云主机进行管理: 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 插件推荐可以参考: https://zhuanlan.zhihu.com/p/623580867 1、公共插件安装 下面是个人使用的插件: # 中文插件 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),可以分为:命令注入(Command Injection)、代码注入(Code Injection) 代码注入 1.漏洞场景:Groovy代码注入 Groovy是一种基于JVM的动态语言,语法简洁,支持闭包、动态类型和Java互操作性,…...

大数据学习栈记——Neo4j的安装与使用
本文介绍图数据库Neofj的安装与使用,操作系统:Ubuntu24.04,Neofj版本:2025.04.0。 Apt安装 Neofj可以进行官网安装:Neo4j Deployment Center - Graph Database & Analytics 我这里安装是添加软件源的方法 最新版…...
椭圆曲线密码学(ECC)
一、ECC算法概述 椭圆曲线密码学(Elliptic Curve Cryptography)是基于椭圆曲线数学理论的公钥密码系统,由Neal Koblitz和Victor Miller在1985年独立提出。相比RSA,ECC在相同安全强度下密钥更短(256位ECC ≈ 3072位RSA…...

前端开发面试题总结-JavaScript篇(一)
文章目录 JavaScript高频问答一、作用域与闭包1.什么是闭包(Closure)?闭包有什么应用场景和潜在问题?2.解释 JavaScript 的作用域链(Scope Chain) 二、原型与继承3.原型链是什么?如何实现继承&a…...
08. C#入门系列【类的基本概念】:开启编程世界的奇妙冒险
C#入门系列【类的基本概念】:开启编程世界的奇妙冒险 嘿,各位编程小白探险家!欢迎来到 C# 的奇幻大陆!今天咱们要深入探索这片大陆上至关重要的 “建筑”—— 类!别害怕,跟着我,保准让你轻松搞…...
jmeter聚合报告中参数详解
sample、average、min、max、90%line、95%line,99%line、Error错误率、吞吐量Thoughput、KB/sec每秒传输的数据量 sample(样本数) 表示测试中发送的请求数量,即测试执行了多少次请求。 单位,以个或者次数表示。 示例:…...
c# 局部函数 定义、功能与示例
C# 局部函数:定义、功能与示例 1. 定义与功能 局部函数(Local Function)是嵌套在另一个方法内部的私有方法,仅在包含它的方法内可见。 • 作用:封装仅用于当前方法的逻辑,避免污染类作用域,提升…...
多元隐函数 偏导公式
我们来推导隐函数 z z ( x , y ) z z(x, y) zz(x,y) 的偏导公式,给定一个隐函数关系: F ( x , y , z ( x , y ) ) 0 F(x, y, z(x, y)) 0 F(x,y,z(x,y))0 🧠 目标: 求 ∂ z ∂ x \frac{\partial z}{\partial x} ∂x∂z、 …...
[特殊字符] 手撸 Redis 互斥锁那些坑
📖 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作,想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁,也顺便跟 Redisson 的 RLock 机制对比了下,记录一波,别踩我踩过…...

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