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

数据结构与算法--队列

news 2026/2/10 10:51:45

文章目录

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

提要

  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

业务系统对接大模型的基础方案：架构设计与关键步骤

业务系统对接大模型&#xff1a;架构设计与关键步骤 在当今数字化转型的浪潮中&#xff0c;大语言模型&#xff08;LLM&#xff09;已成为企业提升业务效率和创新能力的关键技术之一。将大模型集成到业务系统中&#xff0c;不仅可以优化用户体验&#xff0c;还能为业务决策提供…...

编程新知 2026/2/8 4:53:03

C++：std::is_convertible

C++标志库中提供is_convertible，可以测试一种类型是否可以转换为另一只类型： template <class From, class To> struct is_convertible; 使用举例： #include <iostream> #include <string>using namespace std;struct A { }; struct B : A { };int main…...

编程新知 2025/6/11 15:23:57

JVM垃圾回收机制全解析

Java虚拟机&#xff08;JVM&#xff09;中的垃圾收集器&#xff08;Garbage Collector&#xff0c;简称GC&#xff09;是用于自动管理内存的机制。它负责识别和清除不再被程序使用的对象&#xff0c;从而释放内存空间&#xff0c;避免内存泄漏和内存溢出等问题。垃圾收集器在Ja…...

编程新知 2026/1/9 14:53:35

【SQL学习笔记1】增删改查+多表连接全解析（内附SQL免费在线练习工具）

可以使用Sqliteviz这个网站免费编写sql语句&#xff0c;它能够让用户直接在浏览器内练习SQL的语法&#xff0c;不需要安装任何软件。 链接如下&#xff1a; sqliteviz 注意&#xff1a; 在转写SQL语法时&#xff0c;关键字之间有一个特定的顺序&#xff0c;这个顺序会影响到…...

编程新知 2026/2/5 4:36:53

k8s业务程序联调工具-KtConnect

概述 原理 工具作用是建立了一个从本地到集群的单向VPN&#xff0c;根据VPN原理&#xff0c;打通两个内网必然需要借助一个公共中继节点&#xff0c;ktconnect工具巧妙的利用k8s原生的portforward能力&#xff0c;简化了建立连接的过程&#xff0c;apiserver间接起到了中继节…...

编程新知 2026/2/1 4:14:14

NXP S32K146 T-Box 携手 SD NAND（贴片式TF卡）：驱动汽车智能革新的黄金组合

在汽车智能化的汹涌浪潮中&#xff0c;车辆不再仅仅是传统的交通工具&#xff0c;而是逐步演变为高度智能的移动终端。这一转变的核心支撑&#xff0c;来自于车内关键技术的深度融合与协同创新。车载远程信息处理盒&#xff08;T-Box&#xff09;方案&#xff1a;NXP S32K146 与…...

编程新知 2026/1/24 14:43:35

音视频——I2S 协议详解

I2S 协议详解 I2S (Inter-IC Sound) 协议是一种串行总线协议&#xff0c;专门用于在数字音频设备之间传输数字音频数据。它由飞利浦&#xff08;Philips&#xff09;公司开发&#xff0c;以其简单、高效和广泛的兼容性而闻名。 1. 信号线 I2S 协议通常使用三根或四根信号线&a…...

编程新知 2026/2/1 2:08:53

无人机侦测与反制技术的进展与应用

国家电网无人机侦测与反制技术的进展与应用 引言 随着无人机&#xff08;无人驾驶飞行器&#xff0c;UAV&#xff09;技术的快速发展&#xff0c;其在商业、娱乐和军事领域的广泛应用带来了新的安全挑战。特别是对于关键基础设施如电力系统&#xff0c;无人机的“黑飞”&…...

编程新知 2026/1/26 6:01:03

NPOI操作EXCEL文件 ——CAD C# 二次开发

缺点:dll.版本容易加载错误。CAD加载插件时&#xff0c;没有加载所有类库。插件运行过程中用到某个类库&#xff0c;会从CAD的安装目录找&#xff0c;找不到就报错了。 【方案2】让CAD在加载过程中把类库加载到内存 【方案3】是发现缺少了哪个库&#xff0c;就用插件程序加载进…...

编程新知 2026/1/26 13:35:42

关于uniapp展示PDF的解决方案

在 UniApp 的 H5 环境中使用 pdf-vue3 组件可以实现完整的 PDF 预览功能。以下是详细实现步骤和注意事项&#xff1a; 一、安装依赖 安装 pdf-vue3 和 PDF.js 核心库&#xff1a; npm install pdf-vue3 pdfjs-dist二、基本使用示例 <template><view class"con…...

编程新知 2025/9/18 20:16:52