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

数据结构与算法--队列

news 2025/7/5 18:27:54

文章目录

    • 提要
    • 队列的定义
    • 队列的认识
    • 队列的应用
    • 队列的抽象数据类型
    • 队列的存储结构
    • 队列的链式存储结构与实现
    • 链队的进队和出队操作
    • 链队的数据类型
    • 初始化链队列
    • 入队操作
    • 出队操作
    • 队列的顺序存储结构与实现
    • 顺序队列的假溢出问题
    • 队列上溢
    • 循环队列
    • 循环队列取下一相邻单元下标运算
    • 队满与队空的问题
    • 解决方法
    • 循环队列入队操作
    • 循环队列出队操作
    • 总结

提要

  1. 队列的定义
  2. 队列的抽象数据类型
  3. 队列的链式存储结构与基本运算的实现
  4. 队列的顺序存储结构与基本运算的实现

队列的定义

  • 队列是一种受限的线性表，只能在一端插入，在另一端删除
  • 队尾（rear）：允许插入的一端
  • 队头（front）：允许删除的一端
  • 入队（enqueue）：在队尾进行的插入操作
  • 出队（dequeue）：在队头进行的删除操作
  • 队列特点：先进先出（FIFO）
  • 栈的应用非常广泛，在CPU内部就有提供栈这个机制。主要用途：函数调用和返回，数字转字符，表达式求值，走迷宫等等。在CPU内部栈主要是用来进行子程序调用和返回，中断时数据保存和返回。在编程语言中：主要用来进行函数的调用和返回。在计算机中，可以说，只要数据的保存满足先进后出的原理，都优先考虑使用栈，所以栈是计算机中不可缺的机制。
    在这里插入图片描述

队列的认识

  • 队列是生活中排队的抽象
  • 插队是不允许的
  • 队列的主要特点是先进先出，所以又把队列称为先进先出表。

队列的应用

  • 记录访问或操作的顺序
  • 对独占资源的调度安排，如打印机
  • 电子商务网站的秒杀功能
  • 大型信息系统中的消息队列

队列的抽象数据类型

  • 数据元素集合：具有相同性质数据元素的有限序列,且只能在称为队尾的一端进行插入操作和在队头的一端进行删除操作。
  • 基本操作：
    • 初始化队列 (InitQueue)
    • 求队列长度 (QueueLength)
    • 入队 (EnQueue)
    • 出队 (DeQueue)
    • 判队空 (QueueEmpty)

队列的存储结构

  • 顺序队列
  • 链队列
  • 在

队列的链式存储结构与实现

  • 链队：采用不带头结点的单链表实现
  • 队头指针和队尾指针
    在这里插入图片描述
    在这里插入图片描述
    链队组成:
    （1）存储队列元素的单链表结点
    （2） 指向队头和队尾指针的链队头结点

链队的进队和出队操作

  • （a）空队
    在这里插入图片描述
  • （b）a、b、c进队
    在这里插入图片描述
  • （c）出队一次
  • 在这里插入图片描述
  • 链队的4要素：
  • 队空条件：front=rear=NULL
  • 队满条件：不考虑
  • 进队e操作：将包含e的结点插入到单链表表尾
  • 出队操作：删除单链表首数据结点

链队的数据类型

  • front指针指向头结点
  • rear指针指向最后一个元素结点
    在这里插入图片描述
    在这里插入图片描述

在这里插入图片描述

初始化链队列

  • 构造一个只有空头结点的链式队列
  • 头尾指针均指向头结点
  • 在这里插入图片描述
  • 在这里插入图片描述

入队操作

  • 生成新结点并插入到链表尾部
    在这里插入图片描述
    在这里插入图片描述

出队操作

  • 判断队列是否为空

  • 在这里插入图片描述

  • 删除队头元素结点

  • 在这里插入图片描述

  • 若被删结点是队尾结点，则更新队尾指针指向头结点。

  • 在这里插入图片描述
    在这里插入图片描述

队列的顺序存储结构与实现

  • 使用数组实现队列

  • 在这里插入图片描述

  • 头尾指针分别表示队头和队尾

顺序队列的假溢出问题

  • 解释了假溢出现象和解决方法

在这里插入图片描述

  • 当rear超出数组最大下标后，队列的空间就用尽了。
    即使数组下标较小的位置还有空闲空间，也不能进行入队操作

队列上溢

真上溢 (rear-front=MaxSize)：队列真正满，无空位。
假上溢：rear已指向队尾，但队列前端仍有空位置。
解决假上溢的方法：
方法一：每次删除队头一个元素后，把整个队列往前移一个位置（造成时间浪费）
方法二：（构造）循环队列

循环队列

  • 首尾相接的队列实现：把数组的首尾两个存储单元看成位置相邻的单元，即允许队列直接从数组中下标最大的位置前进到下标最小的位置。(设数组长度为Max)

循环队列取下一相邻单元下标运算

  • 数组第一个单元的下标为 0
    与下标1的单元相邻
    (0+1)％ Max＝1
    数组最后一个单元的下标为Max－1
    其下一相邻的单元的下标为0
    (Max-1+1)％ Max＝0
    任一位置 X (0≤X≤Max-1)
    X的下一相邻的单元的下标为 (X+1)％Max

  • 数据入队前
    在这里插入图片描述
    在这里插入图片描述

队满与队空的问题

  • 解释了如何判断队列满和队空
  • 在这里插入图片描述

解决方法

  • 少用一个存储单元来区分队满和队空
  • 队空：front==rear
  • 队满：(rear + 1) % MaxSize == front
  • 队列长度：(rear–front+MaxSize) % MaxSize

循环队列入队操作

  • 描述了入队操作的步骤
    在这里插入图片描述

循环队列出队操作

  • 描述了出队操作的步骤
    在这里插入图片描述

总结

  • 循环队列和链队列的比较
    • 时间性能：基本操作都需要常数时间 O(1)
    • 空间性能：循环队列有存储元素个数的限制和空间浪费问题；链队列没有队列满的问题，但有结构性开销

相关文章：

数据结构与算法--队列

文章目录 提要队列的定义队列的认识队列的应用队列的抽象数据类型队列的存储结构队列的链式存储结构与实现链队的进队和出队操作链队的数据类型初始化链队列入队操作出队操作队列的顺序存储结构与实现顺序队列的假溢出问题队列上溢循环队列循环队列取下一相邻单元下标运算队满与…...

编程日记 2024/8/4 4:32:16

＜Qt＞ 常用控件

目录 一、控件概述 二、QWidget 核心属性 （一）QWidget的核心属性概览 1. enabled 2. geometry 3. WindowFrame的影响 4. windowTitle 5. window Icon 6. windowOpacity 7. cursor 8. font 9. toolTip 10. focusPolicy 11. styleSheet 三、…...

编程日记 2024/8/4 4:27:11

关于C/C++的编译、构建、CMake、x86_amd64等问题（自用）

被这些玩意整红温了 编译器版本 x86：编译器为x86版本，输出文件为x86。amd64_x86：编译器为amd64版本，输出文件为x86。amd64：编译器为amd64版本，输出文件为amd64。x86_amd64：编译器为x86版本&am…...

编程日记 2024/8/4 4:25:06

【设计模式】工厂模式详解

1.简介 工厂模式是一种创建型设计模式，通过提供一个接口或抽象类来创建对象，而不是直接实例化对象。工厂模式的主要思想是将对象的创建与使用分离，使得创建对象的过程更加灵活和可扩展。 工厂模式主要包括以下角色： 抽象工厂&a…...

编程日记 2024/8/4 4:24:05

【Spring Boot】用 Spring Security 实现后台登录及权限认证功能

用 Spring Security 实现后台登录及权限认证功能 1.引入依赖2.创建权限开放的页面3.创建需要权限验证的页面4.配置 Spring Security4.1 配置 Spring MVC4.2 配置 Spring Security 5.创建登录页面6.测试权限 1.引入依赖 使用前需要引入相关依赖，见以下代码&#xff…...

编程日记 2024/8/4 4:23:04

PHP开发【石头剪刀布小游戏】

石头剪刀布小游戏 玩法超级简单，你只需要在下面选择石头、剪刀或者布，然后提交，系统就会随机生成电脑的选择，告诉你最终的结果哦！ 游戏规则： 如果你的选择和电脑一样，那么就是平局。如果你赢…...

编程日记 2024/8/4 4:22:02

(leetcode学习)42. 接雨水

给定 n 个非负整数表示每个宽度为 1 的柱子的高度图，计算按此排列的柱子，下雨之后能接多少雨水。 示例 1： 输入：height [0,1,0,2,1,0,1,3,2,1,2,1] 输出：6 解释：上面是由数组 [0,1,0,2,1,0,1,3,2,1,2,1] 表…...

编程日记 2024/8/4 4:17:58

Python编程实例2

一、通过用户输入数字计算阶乘 # 获取用户输入的数字 num int(input("请输入一个数字: ")) factorial 1 # 查看数字是负数&#xff0c;0 或 正数 if num < 0:print("抱歉&#xff0c;负数没有阶乘") elif num 0:print("0 的阶乘为 1") e…...

编程日记 2024/8/4 4:16:56

排序算法：堆排序，golang实现

目录 前言 堆排序 代码示例 1. 算法包 2. 堆排序代码 3. 模拟程序 4. 运行程序 5. 从大到小排序 堆排序的思想 堆排序的实现逻辑 1. 构建最大堆 2. 排序 循环次数测试 假如 10 条数据进行排序 假如 20 条数据进行排序 假如 30 条数据进行排序 假设 5000 条数据…...

编程日记 2024/8/4 4:15:55

【网络安全入门】学习网络安全必须知道的77个网络基础知识

1、TCP/IP 协议的四层模型&#xff08;网络接口层、网络层、传输层、应用层&#xff09; TCP/IP 协议是互联网通信的基础&#xff0c;四层模型中&#xff0c;网络接口层负责与物理网络的连接&#xff1b;网络层主要处理 IP 数据包的路由和转发&#xff1b;传输层提供端到端的可…...

编程日记 2024/8/4 4:11:50

limit 以及分页 SQL 语句

目录 1. 作用 2. 演示 3. 分页 SQL 语句 1. 作用 获取结果集的一部分&#xff1b; 2. 演示 &#xff08;1&#xff09;如下&#xff0c;获取表的前三行&#xff1b; &#xff08;2&#xff09;只有一个数字&#xff0c;默认从 0 开始&#xff1b; &#xff08;3&#x…...

编程日记 2024/8/4 4:10:49

mysql8.0规范

MySQL 数据库开发规范 目录 背景与目标规范列表 1. 库表设计 1.1 必须字段1.2 命名规范 2. 定义规范 2.1 约束规范2.2 类型规范 2.2.1 字段类型与长度2.2.2 状态字段数据类型2.2.3 布尔型2.2.4 varchar和text, json2.2.5 decimal(m,d) 3. 索引规范4. 其他规范5. SQL 使用 5.…...

编程日记 2024/8/4 4:09:47

现代前端架构介绍（第三部分）：深入了解状态管理层及其对前端App的影响

远离JavaScript疲劳和框架大战&#xff0c;了解真正重要的东西 在第二部分中&#xff0c;我们讨论了功能架构的三个层次。其中一个就是状态管理层&#xff0c;今天我们将对其进行更深入的探讨。下面是现代前端架构系列的第三部分和最后一部分介绍。 状态管理&#xff0c;你可能…...

编程日记 2024/8/4 4:08:46

NLP与搜广推常见面试问题

1 auc指标 AUC的两种意义 一个是ROC曲线的面积另外一个是统计意义。从统计学角度理解&#xff0c;AUC等于随机挑选一个正样本和负样本时&#xff0c;模型对正样本的预测分数大于负样本的预测分数的概率。下图为搜广推场景下的一个计算auc的例子 2 GAUC指标 就是在推荐系统…...

编程日记 2024/8/4 4:07:45

Python怎么实现协程并发呢?

在Python中&#xff0c;实现协程并发主要是通过asyncio库来完成的。asyncio是Python 3.4中引入的标准库&#xff0c;用于编写单线程的并发代码。使用async和await关键字&#xff0c;你可以定义协程和等待其他协程的完成&#xff0c;而不需要创建额外的线程或进程。 下面是一个使…...

编程日记 2024/8/4 4:05:41

专治408开始的晚！8月一定要完成这些事！

八月份才开始408&#xff0c;那到考试最多也只有4-5个月的时间 别担心&#xff0c;可以复习两轮&#xff01; 其实我一直建议大家408复习三轮&#xff0c;但是如果时间不够&#xff0c;那就要在复习质量上下功夫&#xff01; 考408有一个好处&#xff0c;就是不用先确定学校…...

编程日记 2024/8/4 4:04:40

计算机毕业设计选题推荐-校内跑腿业务系统-Java/Python项目实战

✨作者主页&#xff1a;IT毕设梦工厂✨ 个人简介&#xff1a;曾从事计算机专业培训教学&#xff0c;擅长Java、Python、微信小程序、Golang、安卓Android等项目实战。接项目定制开发、代码讲解、答辩教学、文档编写、降重等。 ☑文末获取源码☑ 精彩专栏推荐⬇⬇⬇ Java项目 Py…...

编程日记 2024/8/4 4:03:38

Unity命名验证工具类

在Unity开发中&#xff0c;经常需要验证变量名是否符合命名规范&#xff0c;同时避免使用C#的保留字作为变量名。本教程将演示如何创建一个简单的工具类来实现这一功能。 步骤 1&#xff1a;创建Unity命名验证工具类 首先&#xff0c;我们创建一个C#类&#xff0c;命名为Unit…...

编程日记 2024/8/4 4:02:37

基于cubeMX的STM32开启SPI及DMA

1、打开cubeMX后&#xff0c;设置SPI&#xff0c;如下图 2、设置SPI的DMA中断 3、DMA设置 4、SPI的GPIO设置 5、最后生成代码&#xff0c;可以看到工程文件中有dma.c和spi.c 6、使用举例&#xff1a;如幻彩灯的亮灭使用SPIDMA产生的信号波形来控制&#xff0c;在ws2812.c中调用…...

编程日记 2024/8/4 4:01:36

AI大模型技术的四大核心架构分析

AI大模型技术的四大核心架构演进之路 随着人工智能技术的飞速发展&#xff0c;大模型技术已经成为AI领域的重要分支。 深度剖析四大大模型技术架构&#xff1a;纯粹的Prompt提示词法、Agent Function Calling机制&#xff0c;RAG&#xff08;检索增强生成&#xff09;及Fine-…...

编程日记 2024/8/4 4:00:35

OpenLayers 可视化之热力图

注&#xff1a;当前使用的是 ol 5.3.0 版本&#xff0c;天地图使用的key请到天地图官网申请&#xff0c;并替换为自己的key 热力图&#xff08;Heatmap&#xff09;又叫热点图&#xff0c;是一种通过特殊高亮显示事物密度分布、变化趋势的数据可视化技术。采用颜色的深浅来显示…...

编程新知 2025/6/18 7:54:42

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

编程新知 2025/7/1 6:27:20

DAY 47

三、通道注意力 3.1 通道注意力的定义 # 新增&#xff1a;通道注意力模块&#xff08;SE模块&#xff09; class ChannelAttention(nn.Module):"""通道注意力模块(Squeeze-and-Excitation)"""def __init__(self, in_channels, reduction_rat…...

编程新知 2025/7/5 1:30:02

SpringCloudGateway 自定义局部过滤器

场景&#xff1a; 将所有请求转化为同一路径请求&#xff08;方便穿网配置&#xff09;在请求头内标识原来路径&#xff0c;然后在将请求分发给不同服务 AllToOneGatewayFilterFactory import lombok.Getter; import lombok.Setter; import lombok.extern.slf4j.Slf4j; impor…...

编程新知 2025/7/4 9:37:32

浅谈不同二分算法的查找情况

二分算法原理比较简单&#xff0c;但是实际的算法模板却有很多&#xff0c;这一切都源于二分查找问题中的复杂情况和二分算法的边界处理&#xff0c;以下是博主对一些二分算法查找的情况分析。 需要说明的是&#xff0c;以下二分算法都是基于有序序列为升序有序的情况&#xf…...

编程新知 2025/7/4 17:40:43

Mac下Android Studio扫描根目录卡死问题记录

环境信息 操作系统: macOS 15.5 (Apple M2芯片)Android Studio版本: Meerkat Feature Drop | 2024.3.2 Patch 1 (Build #AI-243.26053.27.2432.13536105, 2025年5月22日构建) 问题现象 在项目开发过程中&#xff0c;提示一个依赖外部头文件的cpp源文件需要同步&#xff0c;点…...

编程新知 2025/7/5 13:24:58

【VLNs篇】07：NavRL—在动态环境中学习安全飞行

项目内容论文标题NavRL: 在动态环境中学习安全飞行 (NavRL: Learning Safe Flight in Dynamic Environments)核心问题解决无人机在包含静态和动态障碍物的复杂环境中进行安全、高效自主导航的挑战&#xff0c;克服传统方法和现有强化学习方法的局限性。核心算法基于近端策略优化…...

编程新知 2025/7/4 2:54:13

MFC 抛体运动模拟：常见问题解决与界面美化

在 MFC 中开发抛体运动模拟程序时，我们常遇到 轨迹残留、无效刷新、视觉单调、物理逻辑瑕疵 等问题。本文将针对这些痛点，详细解析原因并提供解决方案，同时兼顾界面美化，让模拟效果更专业、更高效。 问题一：历史轨迹与小球残影残留 现象 小球运动后，历史位置的 “残影”…...

编程新知 2025/7/2 15:32:43

虚拟电厂发展三大趋势：市场化、技术主导、车网互联

市场化&#xff1a;从政策驱动到多元盈利 政策全面赋能 2025年4月&#xff0c;国家发改委、能源局发布《关于加快推进虚拟电厂发展的指导意见》&#xff0c;首次明确虚拟电厂为“独立市场主体”&#xff0c;提出硬性目标&#xff1a;2027年全国调节能力≥2000万千瓦&#xff0…...

编程新知 2025/6/16 11:14:36

Golang——9、反射和文件操作

反射和文件操作 1、反射1.1、reflect.TypeOf()获取任意值的类型对象1.2、reflect.ValueOf()1.3、结构体反射 2、文件操作2.1、os.Open()打开文件2.2、方式一&#xff1a;使用Read()读取文件2.3、方式二&#xff1a;bufio读取文件2.4、方式三&#xff1a;os.ReadFile读取2.5、写…...

编程新知 2025/6/21 10:52:13