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

数据结构与算法--队列

news 2025/7/6 12:06:26

文章目录

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

提要

  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

什么是EULA和DPA

文章目录 EULA&#xff08;End User License Agreement&#xff09;DPA&#xff08;Data Protection Agreement&#xff09;一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA&#xff08;End User License Agreement&#xff09; 定义&#xff1a; EULA即…...

编程新知 2025/7/4 8:55:29

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

编程新知 2025/7/5 15:14:01

【RockeMQ】第2节｜RocketMQ快速实战以及核⼼概念详解（二）

升级Dledger高可用集群 一、主从架构的不足与Dledger的定位 主从架构缺陷 数据备份依赖Slave节点&#xff0c;但无自动故障转移能力&#xff0c;Master宕机后需人工切换&#xff0c;期间消息可能无法读取。Slave仅存储数据&#xff0c;无法主动升级为Master响应请求&#xff…...

编程新知 2025/6/18 22:53:06

今日学习：Spring线程池|并发修改异常|链路丢失|登录续期|VIP过期策略|数值类缓存

文章目录 优雅版线程池ThreadPoolTaskExecutor和ThreadPoolTaskExecutor的装饰器并发修改异常并发修改异常简介实现机制设计原因及意义 使用线程池造成的链路丢失问题线程池导致的链路丢失问题发生原因 常见解决方法更好的解决方法设计精妙之处 登录续期登录续期常见实现方式特…...

编程新知 2025/6/22 19:33:11

【Go语言基础【13】】函数、闭包、方法

文章目录 零、概述一、函数基础1、函数基础概念2、参数传递机制3、返回值特性3.1. 多返回值3.2. 命名返回值3.3. 错误处理 二、函数类型与高阶函数1. 函数类型定义2. 高阶函数&#xff08;函数作为参数、返回值&#xff09; 三、匿名函数与闭包1. 匿名函数&#xff08;Lambda函…...

编程新知 2025/6/16 16:17:22

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement

Cilium动手实验室: 精通之旅---13.Cilium LoadBalancer IPAM and L2 Service Announcement 1. LAB环境2. L2公告策略2.1 部署Death Star2.2 访问服务2.3 部署L2公告策略2.4 服务宣告 3. 可视化 ARP 流量3.1 部署新服务3.2 准备可视化3.3 再次请求 4. 自动IPAM4.1 IPAM Pool4.2 …...

编程新知 2025/7/1 18:57:58

[论文阅读]TrustRAG: Enhancing Robustness and Trustworthiness in RAG

TrustRAG: Enhancing Robustness and Trustworthiness in RAG [2501.00879] TrustRAG: Enhancing Robustness and Trustworthiness in Retrieval-Augmented Generation 代码&#xff1a;HuichiZhou/TrustRAG: Code for "TrustRAG: Enhancing Robustness and Trustworthin…...

编程新知 2025/7/6 4:15:24

ubuntu22.04 安装docker 和docker-compose

首先你要确保没有docker环境或者使用命令删掉docker sudo apt-get remove docker docker-engine docker.io containerd runc安装docker 更新软件环境 sudo apt update sudo apt upgrade下载docker依赖和GPG 密钥 # 依赖 apt-get install ca-certificates curl gnupg lsb-rel…...

编程新知 2025/7/6 4:09:48

软件工程 期末复习

瀑布模型&#xff1a;计划 螺旋模型&#xff1a;风险低 原型模型: 用户反馈 喷泉模型:代码复用 高内聚 低耦合&#xff1a;模块内部功能紧密 模块之间依赖程度小 高内聚&#xff1a;指的是一个模块内部的功能应该紧密相关。换句话说&#xff0c;一个模块应当只实现单一的功能…...

编程新知 2025/7/5 7:04:12

​​企业大模型服务合规指南：深度解析备案与登记制度​​

伴随AI技术的爆炸式发展&#xff0c;尤其是大模型&#xff08;LLM&#xff09;在各行各业的深度应用和整合&#xff0c;企业利用AI技术提升效率、创新服务的步伐不断加快。无论是像DeepSeek这样的前沿技术提供者&#xff0c;还是积极拥抱AI转型的传统企业&#xff0c;在面向公众…...

编程新知 2025/6/30 3:31:51