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

数据结构与算法--队列

news 2025/9/6 13:41:32

文章目录

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

提要

  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

相机Camera日志实例分析之二：相机Camx【专业模式开启直方图拍照】单帧流程日志详解

【关注我&#xff0c;后续持续新增专题博文&#xff0c;谢谢&#xff01;&#xff01;&#xff01;】 上一篇我们讲了&#xff1a; 这一篇我们开始讲&#xff1a; 目录 一、场景操作步骤 二、日志基础关键字分级如下 三、场景日志如下&#xff1a; 一、场景操作步骤 操作步…...

编程新知 2025/8/22 3:28:25

如何在看板中体现优先级变化

在看板中有效体现优先级变化的关键措施包括&#xff1a;采用颜色或标签标识优先级、设置任务排序规则、使用独立的优先级列或泳道、结合自动化规则同步优先级变化、建立定期的优先级审查流程。其中&#xff0c;设置任务排序规则尤其重要&#xff0c;因为它让看板视觉上直观地体…...

编程新知 2025/9/5 23:10:53

（二）TensorRT-LLM | 模型导出（v0.20.0rc3）

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

编程新知 2025/8/22 4:15:24

CentOS下的分布式内存计算Spark环境部署

一、Spark 核心架构与应用场景 1.1 分布式计算引擎的核心优势 Spark 是基于内存的分布式计算框架&#xff0c;相比 MapReduce 具有以下核心优势&#xff1a; 内存计算&#xff1a;数据可常驻内存&#xff0c;迭代计算性能提升 10-100 倍&#xff08;文档段落&#xff1a;3-79…...

编程新知 2025/8/21 20:43:48

dedecms 织梦自定义表单留言增加ajax验证码功能

增加ajax功能模块&#xff0c;用户不点击提交按钮&#xff0c;只要输入框失去焦点&#xff0c;就会提前提示验证码是否正确。 一&#xff0c;模板上增加验证码 <input name"vdcode"id"vdcode" placeholder"请输入验证码" type"text&quo…...

编程新知 2025/8/22 5:00:36

2.Vue编写一个app

1.src中重要的组成 1.1main.ts // 引入createApp用于创建应用 import { createApp } from "vue"; // 引用App根组件 import App from ./App.vue;createApp(App).mount(#app)1.2 App.vue 其中要写三种标签 <template> <!--html--> </template>…...

编程新知 2025/8/21 17:38:03

Python如何给视频添加音频和字幕

在Python中&#xff0c;给视频添加音频和字幕可以使用电影文件处理库MoviePy和字幕处理库Subtitles。下面将详细介绍如何使用这些库来实现视频的音频和字幕添加&#xff0c;包括必要的代码示例和详细解释。 环境准备 在开始之前&#xff0c;需要安装以下Python库&#xff1a;…...

编程新知 2025/9/3 4:12:17

【JavaSE】绘图与事件入门学习笔记

-Java绘图坐标体系 坐标体系-介绍 坐标原点位于左上角&#xff0c;以像素为单位。 在Java坐标系中,第一个是x坐标,表示当前位置为水平方向&#xff0c;距离坐标原点x个像素;第二个是y坐标&#xff0c;表示当前位置为垂直方向&#xff0c;距离坐标原点y个像素。 坐标体系-像素 …...

编程新知 2025/8/16 22:52:27

项目部署到Linux上时遇到的错误（Redis，MySQL，无法正确连接，地址占用问题）

Redis无法正确连接 在运行jar包时出现了这样的错误 查询得知问题核心在于Redis连接失败&#xff0c;具体原因是客户端发送了密码认证请求&#xff0c;但Redis服务器未设置密码 1.为Redis设置密码&#xff08;匹配客户端配置&#xff09; 步骤&#xff1a; 1&#xff09;.修…...

编程新知 2025/9/4 15:57:54

GC1808高性能24位立体声音频ADC芯片解析

1. 芯片概述 GC1808是一款24位立体声音频模数转换器&#xff08;ADC&#xff09;&#xff0c;支持8kHz~96kHz采样率&#xff0c;集成Δ-Σ调制器、数字抗混叠滤波器和高通滤波器&#xff0c;适用于高保真音频采集场景。 2. 核心特性 高精度&#xff1a;24位分辨率&#xff0c…...

编程新知 2025/9/5 11:49:49