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

数据结构与算法-队列

在这里插入图片描述

队列

  • 🎈1.队列的定义
  • 🎈2.队列的抽象数据类型定义
  • 🎈3.顺序队列(循环队列)
    • 🔭3.1循环队列
    • 🔭3.1循环队列类定义
    • 🔭3.2创建空队列
    • 🔭3.3入队操作
    • 🔭3.4出队操作
    • 🔭3.5队列判空操作
    • 🔭3.6打印循环队列
    • 🔭3.7求队列长度
    • 🔭3.8全部代码实现
  • 🎈4.链队列
    • 🔭4.1链队列动态示意图
    • 🔭4.2链队列的类定义
    • 🔭4.3建立空队列
    • 🔭4.4销毁队列
    • 🔭4.5入队操作
    • 🔭4.6出队操作
    • 🔭4.7取队头元素
    • 🔭4.8队列判空
    • 🔭4.9求队列长度
    • 🔭4.10打印队列
    • 🔭4.11全部代码

🎈1.队列的定义

队列是线性表的特例,它也是一种操作受限的线性表。队列只允许在表的一端进行插入,在另一端进行删除。把允许插入的一端称为队尾允许删除的一端称为队头。从队尾插入元素的操作称为入队,从队头删除元素的操作称为出队。队列是一种先进先出的线性表,即每个元素按照进队的次序出队。
在这里插入图片描述
:其中a1为队头,an为队尾,front指向队头,rear指向队尾(实际上是队尾元素的下一个位置)

🎈2.队列的抽象数据类型定义

在这里插入图片描述

🎈3.顺序队列(循环队列)

队列的顺序存储结构称为顺序队列,一般用循环队列表示。顺序队列是用一组地址连续的存储单元(例如:数组)依次存放从队头到队尾的元素,由于队列的队头和队尾的位置是变化的,因此需要定义一个指向队头的指针(front),也称头指针;一个指向队尾的指针(rear),也称尾指针。

将存储队列的数组看成是头尾相接的圆环,并形成循环存储空间,即允许队列直接从数组中下标最大的位置延续到下标最小的位置,这个操作可以通过取模运算实现。队列的这种头尾相接的顺序存储结构称为循环队列。循环队列如图所示,灰色区域表示队列中已经存储数据元素的存储空间,空白区域则表示空闲存储空间。
在这里插入图片描述

🔭3.1循环队列

在循环队列中进行入队、出队操作,头尾指针均加1,依次向前移动。只不过当头尾指针指向存储空间上届(QueueSize-1)时,其加1操作的结果是指向存储空间的下界0.这种循环意义下的加1操作可以利用模运算来实现,即i=(i+1)%QueueSize.
在这里插入图片描述
注:1.空队列的判定条件:rear==front
2.当a出队后,头指针front的移动方式为:front = (front+1) % QueueSize
3.当a,b,c,d入队后,尾指针rear的移动方式为:rear = (rear+1)%QueueSize.
4.队列满的判定条件是:front=(rear+1)%QueueSize.

🔭3.1循环队列类定义

#define QueueSize 100
typedef int QElemType;
class SqQueue
{
private:QElemType* base;int front;int rear;
public:SqQueue();//构造函数,建立空队列~SqQueue()//析构函数,销毁队列{delete[]base;front = rear = 0;}QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue(QElemType& e);//队列元素出队int EmptyQueue();//队列判空,若队列为空返回1,否则返回0
};

🔭3.2创建空队列

SqQueue::SqQueue()//构造函数
{base = new QElemType[QueueSize];front = rear = 0;
}

🔭3.3入队操作

void SqQueue::EnQueue(QElemType e)
{if (front == (rear + 1) % QueueSize)return;else{base[rear] = e;rear = (rear + 1) % QueueSize;}
}

🔭3.4出队操作

void SqQueue::DeQueue(QElemType& e)
{if (front == rear)//队列为空,无法出队return;else{e = base[front];front = (front + 1) % QueueSize;}
}

🔭3.5队列判空操作

int SqQueue::EmptyQueue()
{if (rear == front)return 1;elsereturn 0;
}

🔭3.6打印循环队列

void SqQueue::print(SqQueue& p)
{if (p.EmptyQueue())cout << "Queue is empty!" << endl;QElemType head = p.front;cout << "Queue elements: ";while (head != p.rear){cout << p.base[head] << " ";head = (head + 1) % QueueSize;}
}

🔭3.7求队列长度

void SqQueue::Length()
{cout << (rear - front + QueueSize) % QueueSize << endl;
}

🔭3.8全部代码实现

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
#define QueueSize 100
typedef int QElemType;
class SqQueue
{
private:QElemType* base;int front;int rear;
public:SqQueue();//构造函数,建立空队列~SqQueue()//析构函数,销毁队列{delete[]base;front = rear = 0;}QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue();//队列元素出队int EmptyQueue();//队列判空,若队列为空返回1,否则返回0void Length();//打印队列void print(SqQueue& p);
};
SqQueue::SqQueue()//构造函数
{base = new QElemType[QueueSize];front = rear = 0;
}
void SqQueue::EnQueue(QElemType e)
{if (front == (rear + 1) % QueueSize)return;else{base[rear] = e;rear = (rear + 1) % QueueSize;}
}
void SqQueue::DeQueue()
{QElemType e;if (front == rear)return;else{e = base[front];front = (front + 1) % QueueSize;}
}
int SqQueue::EmptyQueue()
{if (rear == front)return 1;elsereturn 0;
}
QElemType SqQueue::GetHead()
{if (rear == front)return 0;else{cout << base[front] << endl;return 1;}
}
void SqQueue::Length()
{cout << (rear - front + QueueSize) % QueueSize << endl;
}
void SqQueue::print(SqQueue& p)
{if (p.EmptyQueue())cout << "Queue is empty!" << endl;QElemType head = p.front;cout << "Queue elements: ";while (head != p.rear){cout << p.base[head] << " ";head = (head + 1) % QueueSize;}
}
int main()
{SqQueue p;p.EnQueue(1);p.EnQueue(2);p.EnQueue(3);p.EnQueue(4);p.EnQueue(5);p.EnQueue(6);p.EnQueue(7);p.EnQueue(8);p.EnQueue(9);p.EnQueue(10);p.Length();p.DeQueue();p.GetHead();p.print(p);return 0;
}

✅运行示例:
在这里插入图片描述

🎈4.链队列

队列的链式存储结构称为链队列。链队列可通过带头结点的单链表来实现。此时只允许在单链表的表首进行删除操作和在单链表的表尾进行插入操作。为此,需要设立两个指针,一个指向头结点,称为表首指针(front),另一个指向队尾结点,称为表尾指针(rear).根据队列先进先出的特征,链队列是仅在表头删除元素和表尾插入元素的单链表
在这里插入图片描述

🔭4.1链队列动态示意图

在这里插入图片描述

🔭4.2链队列的类定义

typedef int QElemType;
//链队列的数据结点类型定义如下:
typedef struct QNode
{QElemType data;QNode* next;
}QNode;
//链队结点类型定义如下:
typedef struct
{QNode* front;QNode* rear;
}LinkQNode;
class LinkQueue
{
private:LinkQNode q;
public:LinkQueue();//构造函数,建立空队列~LinkQueue();QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue(QElemType& e);//队头元素出队int EmptyQueue();//队列判空,若队列为空则返回1,否则返回0int QueueLength();//获取队列长度,即队列中元素个数

🔭4.3建立空队列

LinkQueue::LinkQueue()
{q.front = q.rear = new QNode;q.front->next = NULL;
}

🔭4.4销毁队列

LinkQueue::~LinkQueue()
{QNode* p = q.front->next;while (p){q.front->next = p->next;delete p;p = q.front->next;}delete q.front;//删除最后一个结点
}

🔭4.5入队操作

void LinkQueue::EnQueue(QElemType e)
{QNode* s = new QNode;s->data = e;s->next = NULL;q.rear->next = s;q.rear = s;
}

🔭4.6出队操作

void LinkQueue::DeQueue(QElemType& e)
{if (q.front == q.rear)return;else{QNode* p = q.front->next;q.front->next = p->next;e = p->data;if (p == q.rear){q.rear = q.front;delete p;}	}
}

🔭4.7取队头元素

QElemType LinkQueue::GetHead()
{if (q.front->next != NULL)return q.front->next->data;
}

🔭4.8队列判空

int LinkQueue::EmptyQueue()
{if (q.front->next != NULL)return 0;elsereturn 1;
}

🔭4.9求队列长度

void LinkQueue::QueueLength()
{int length = 0;QNode* p = q.front->next;while (p){length++;p = p->next;}cout << "该链队列的长度为:" << length << endl;
}

🔭4.10打印队列

void LinkQueue::print()
{QNode* p = q.front->next;while (p){cout << p->data<<" ";p = p->next;}cout << endl;
}

🔭4.11全部代码

#define _CRT_SECURE_NO_WARNINGS 1
#include <iostream>
using namespace std;
typedef int QElemType;
//链队列的数据结点类型定义如下:
typedef struct QNode
{QElemType data;QNode* next;
}QNode;
//链队结点类型定义如下:
typedef struct
{QNode* front;QNode* rear;
}LinkQNode;
class LinkQueue
{
private:LinkQNode q;
public:LinkQueue();//构造函数,建立空队列~LinkQueue();QElemType GetHead();//取队头元素void EnQueue(QElemType e);//元素e入队void DeQueue();//队头元素出队int EmptyQueue();//队列判空,若队列为空则返回1,否则返回0void QueueLength();//获取队列长度,即队列中元素个数void print();
};
LinkQueue::LinkQueue()
{q.front = q.rear = new QNode;q.front->next = NULL;
}
LinkQueue::~LinkQueue()
{QNode* p = q.front->next;while (p){q.front->next = p->next;delete p;p = q.front->next;}delete q.front;//删除最后一个结点
}
void LinkQueue::EnQueue(QElemType e)
{QNode* s = new QNode;s->data = e;s->next = NULL;q.rear->next = s;q.rear = s;
}
void LinkQueue::DeQueue()
{QElemType e;if (q.front == q.rear)return;else{QNode* p = q.front->next;q.front->next = p->next;e = p->data;if (p == q.rear){q.rear = q.front;delete p;}	}
}
QElemType LinkQueue::GetHead()
{if (q.front->next != NULL)cout<< q.front->next->data<<endl;return 1;
}
int LinkQueue::EmptyQueue()
{if (q.front->next != NULL)return 0;elsereturn 1;
}
void LinkQueue::QueueLength()
{int length = 0;QNode* p = q.front->next;while (p){length++;p = p->next;}cout << "该链队列的长度为:" << length << endl;
}
void LinkQueue::print()
{QNode* p = q.front->next;while (p){cout << p->data<<" ";p = p->next;}cout << endl;
}int main()
{LinkQueue q;q.EnQueue(1);q.EnQueue(2);q.EnQueue(3);q.EnQueue(4);q.EnQueue(5);q.print();q.DeQueue();q.print();q.GetHead();q.QueueLength();return 0;
}

✅运行示例:
在这里插入图片描述

好啦,关于队列的知识到这里就结束啦,后期会继续更新数据结构与算法的相关知识,欢迎大家持续关注、点赞和评论!❤️❤️❤️

相关文章:

数据结构与算法-队列

队列 &#x1f388;1.队列的定义&#x1f388;2.队列的抽象数据类型定义&#x1f388;3.顺序队列&#xff08;循环队列&#xff09;&#x1f52d;3.1循环队列&#x1f52d;3.1循环队列类定义&#x1f52d;3.2创建空队列&#x1f52d;3.3入队操作&#x1f52d;3.4出队操作&#…...

腾讯云轻量2核4G5M可容纳多少人访问?

腾讯云2核4G5M服务器支持多少人在线访问&#xff1f;卡不卡&#xff1f;腾讯云轻量2核4G5M带宽服务器支持多少人在线访问&#xff1f;5M带宽下载速度峰值可达640KB/秒&#xff0c;阿腾云以搭建网站为例&#xff0c;假设优化后平均大小为60KB&#xff0c;则5M带宽可支撑10个用户…...

【分布式计算】九、容错性 Fault Tolerance

分布式系统应当有一定的容错性&#xff0c;发生故障时仍能运行 一些概念&#xff1a; 可用性Availability&#xff1a;系统是否准备好立即使用 可靠性Reliability&#xff1a;系统连续运行不发生故障 安全性&#xff1a;衡量安全故障的指标&#xff0c;没有严重事件发生 可维护…...

The SDK location is inside Studio install location 解决

The SDK location is inside Studio install location 解决 安装 Android Studio SDK 时提示&#xff1a;The SDK location is inside Studio install location 解决 问题&#xff1a; 由于 SDK 与 编辑器(Android Studio)的安装在同一目录下所以报错。 解决 你需要在 Andro…...

【蓝桥】数树数

一、题目 1、题目描述 给定一个层数为 n n n 的满二叉树&#xff0c;每个点编号规则如下&#xff1a; 具体来说&#xff0c;二叉树从上往下数第 p p p 层&#xff0c;从左往右编号分别为&#xff1a;1,2,3,4&#xff0c;…, 2p-1。 给你一条从根节点开始的路径&#xff0…...

2、Windows下安装

目录 一.安装 1、双击下载的程序&#xff1a; 2、加载完成后&#xff0c;会进入如下界面&#xff08;选第一个Developer Default&#xff09; 3、然后点击Next 点击Execute 然后Next 4.继续next注意端口为3306 5.继续next&#xff0c;输入账户密码&#xff08;要有大小写…...

vue中transition的使用

Vue中的<transition>组件用于在元素或组件添加/移除时应用过渡动画。它能够包裹需要进行过渡效果的元素或组件&#xff0c;通过设置相应的CSS样式来实现过渡动画效果。 <transition name"过渡效果名称" before-enter"beforeEnter" enter"…...

性能测试中如何使用RunnerGo还原混合并发场景

我们在进行软件开发时经常需要进行性能测试、压力测试和负载测试。其中有一类测试场景叫做混合并发测试&#xff0c;需要模拟多个接口下不同数量的用户使用场景&#xff0c;检查同时处理多个并发任务的能力&#xff0c;本文将展示如何使用开源的RunnerGo还原混合并发场景。 在…...

KanziStudio described using object-oriented design patterns(持续更新...)

1.绑定-mvc mvc&#xff0c;model数据与view控件分离。...

线程同步的几种方式

目录 互斥锁条件变量读写锁信号量CAS-- 参考 线程同步方式有互斥锁&#xff0c;条件变量&#xff0c;信号量&#xff0c;读写锁&#xff0c;CAS锁等方式 互斥锁 互斥量 pthread_mutex_t在执行操作之前加锁&#xff0c;操作完之后解锁. 使用互斥量&#xff0c;来确保同一时刻只…...

Linux网络编程系列之服务器编程——多路复用模型

一、什么是多路复用模型 服务器的多路复用模型指的是利用操作系统提供的多路复用机制&#xff0c;同时处理多个客户端连接请求的能力。在服务器端&#xff0c;常见的多路复用技术包括select、poll和epoll等。这些技术允许服务器同时监听多个客户端连接请求&#xff0c;当有请求…...

在SQL语句里使用正则表达式,因该怎么使用

在SQL中使用正则表达式通常需要使用特定的函数或运算符&#xff0c;具体的语法可能因不同的数据库系统而有所不同。以下是使用正则表达式的一般方法&#xff0c;但请注意&#xff0c;具体语法可能会因您使用的数据库而有所不同。 一般情况下&#xff0c;您可以使用以下方法在S…...

扫码登录-测试用例设计

扫码登录测试用例...

PyTorch CUDA GPU高占用测试

0x00 问题描述 安装完成PyTorch、CUDA后&#xff0c;验证PyTorch是否能够通过CUDA高占用GPU&#xff08;占用>95%&#xff09;&#xff0c;特地使用以下代码测试。 0x01 代码设计 这个代码会持续执行神经网络的训练任务&#xff0c;每次循环都进行前向传播、反向传播和参数…...

Java|学习|abstract ,接口 Interface , Object

1.abstract 1.1 abstract abstract 是修饰符&#xff0c;表示抽象的&#xff0c;用来修饰抽象类和抽象方法。 abstract 修饰的类是抽象类&#xff0c;抽象类不能创建对象&#xff0c;主要用于被子类继承。 abstract 修饰的方法是抽象方法&#xff0c;该方法没有方法体&…...

安全的Sui Move是Web3大规模采用之路的基石

没有信任&#xff0c;就没有Web3的大规模采用。还有其他重要障碍阻碍了首个十亿用户的到来&#xff0c;包括令人困惑的用户体验、复杂的身份验证模式以及不确定的监管体系&#xff0c;但所有障碍中&#xff0c;要数大多数人对区块链技术持怀疑和不信任态度最严重。 对于许多人…...

Python中图像相似性度量方法汇总

1. 引言 在当前到处充满着图像的世界里&#xff0c;测量和量化图像之间的相似性已经成为一项关键的任务。无论是图像检索、内容推荐还是视觉搜索&#xff0c;图像相似性方法在现代计算机视觉的应用中都发挥着关键的作用。 幸运的是&#xff0c;Python提供了大量的工具和库&am…...

pycharm中快速对比两个.py文件

在学习一个算法的时候&#xff0c;就想着自己再敲一遍代码&#xff0c;结果最后出现了一个莫名其妙的错误&#xff0c;想跟源文件对比一下到底是在哪除了错&#xff0c;之前我都是大致定位一个一个对比&#xff0c;想起来matlab可以快速查找出两个脚本文件(.m文件)的区别&#…...

C++程序结束

在C程序任意位置结束程序需要return 0&#xff0c;如果只return的话会发生生成错误...

嵌入式学习-核心板、开发板和单片机

目录 核心板开发板单片机三者关系 核心板 核心板是一种电路板&#xff0c;它集成了微处理器、存储器和一些必要的接口电路。它通常用于嵌入式系统或物联网设备中&#xff0c;作为整个系统的核心组件。它的主要功能是将微处理器的指令和数据总线转换为各种外设的接口&#xff0…...

【Axure高保真原型】引导弹窗

今天和大家中分享引导弹窗的原型模板&#xff0c;载入页面后&#xff0c;会显示引导弹窗&#xff0c;适用于引导用户使用页面&#xff0c;点击完成后&#xff0c;会显示下一个引导弹窗&#xff0c;直至最后一个引导弹窗完成后进入首页。具体效果可以点击下方视频观看或打开下方…...

在HarmonyOS ArkTS ArkUI-X 5.0及以上版本中,手势开发全攻略:

在 HarmonyOS 应用开发中&#xff0c;手势交互是连接用户与设备的核心纽带。ArkTS 框架提供了丰富的手势处理能力&#xff0c;既支持点击、长按、拖拽等基础单一手势的精细控制&#xff0c;也能通过多种绑定策略解决父子组件的手势竞争问题。本文将结合官方开发文档&#xff0c…...

高等数学(下)题型笔记(八)空间解析几何与向量代数

目录 0 前言 1 向量的点乘 1.1 基本公式 1.2 例题 2 向量的叉乘 2.1 基础知识 2.2 例题 3 空间平面方程 3.1 基础知识 3.2 例题 4 空间直线方程 4.1 基础知识 4.2 例题 5 旋转曲面及其方程 5.1 基础知识 5.2 例题 6 空间曲面的法线与切平面 6.1 基础知识 6.2…...

Nginx server_name 配置说明

Nginx 是一个高性能的反向代理和负载均衡服务器&#xff0c;其核心配置之一是 server 块中的 server_name 指令。server_name 决定了 Nginx 如何根据客户端请求的 Host 头匹配对应的虚拟主机&#xff08;Virtual Host&#xff09;。 1. 简介 Nginx 使用 server_name 指令来确定…...

从零开始打造 OpenSTLinux 6.6 Yocto 系统(基于STM32CubeMX)(九)

设备树移植 和uboot设备树修改的内容同步到kernel将设备树stm32mp157d-stm32mp157daa1-mx.dts复制到内核源码目录下 源码修改及编译 修改arch/arm/boot/dts/st/Makefile&#xff0c;新增设备树编译 stm32mp157f-ev1-m4-examples.dtb \stm32mp157d-stm32mp157daa1-mx.dtb修改…...

Linux-07 ubuntu 的 chrome 启动不了

文章目录 问题原因解决步骤一、卸载旧版chrome二、重新安装chorme三、启动不了&#xff0c;报错如下四、启动不了&#xff0c;解决如下 总结 问题原因 在应用中可以看到chrome&#xff0c;但是打不开(说明&#xff1a;原来的ubuntu系统出问题了&#xff0c;这个是备用的硬盘&a…...

CMake 从 GitHub 下载第三方库并使用

有时我们希望直接使用 GitHub 上的开源库,而不想手动下载、编译和安装。 可以利用 CMake 提供的 FetchContent 模块来实现自动下载、构建和链接第三方库。 FetchContent 命令官方文档✅ 示例代码 我们将以 fmt 这个流行的格式化库为例,演示如何: 使用 FetchContent 从 GitH…...

ArcGIS Pro制作水平横向图例+多级标注

今天介绍下载ArcGIS Pro中如何设置水平横向图例。 之前我们介绍了ArcGIS的横向图例制作&#xff1a;ArcGIS横向、多列图例、顺序重排、符号居中、批量更改图例符号等等&#xff08;ArcGIS出图图例8大技巧&#xff09;&#xff0c;那这次我们看看ArcGIS Pro如何更加快捷的操作。…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

适应性Java用于现代 API:REST、GraphQL 和事件驱动

在快速发展的软件开发领域&#xff0c;REST、GraphQL 和事件驱动架构等新的 API 标准对于构建可扩展、高效的系统至关重要。Java 在现代 API 方面以其在企业应用中的稳定性而闻名&#xff0c;不断适应这些现代范式的需求。随着不断发展的生态系统&#xff0c;Java 在现代 API 方…...