3.5 队列的表示和操作的实现

思维导图:

 3.5.1 队列类型 

3.5.1 队列的类型定义

1. 简介

  • 队列是一种特殊的线性表,它的特性是只能在表的一端进行插入操作,而在另一端进行删除操作。
  • 通常将允许插入操作的一端称为队尾,允许删除操作的一端称为队头。

2. 抽象数据类型定义

ADT Queue

数据对象:D = {a₁, a₂, ..., an | ai∈ElemSet, i=1,2,…,n, n≥0}

数据关系:R = {<ai, aj> | ai-1, aj∈D, i=2,…,n}

约定:其中 a₁ 为队头, an 为队尾。

基本操作

  • InitQueue(&Q)

    • 操作结果:构造一个空队列Q。
  • DestroyQueue(&Q)

    • 初始条件:队列Q已存在。
    • 操作结果:销毁队列Q。
  • ClearQueue(&Q)

    • 初始条件:队列Q已存在。
    • 操作结果:将Q清为空队列。
  • QueueEmpty(Q)

    • 初始条件:队列Q已存在。
    • 操作结果:若Q为空队列,返回true;否则,返回false。
  • QueueLength(Q)

    • 初始条件:队列Q已存在。
    • 操作结果:返回Q的元素个数,即队列的长度。
  • GetHead(Q)

    • 初始条件:Q为非空队列。
    • 操作结果:返回Q的队头元素。
  • EnQueue(&Q, e)

    • 初始条件:队列Q已存在。
    • 操作结果:插入元素e为Q的新队尾元素。
  • DeQueue(&Q, &e)

    • 初始条件:Q为非空队列。
    • 操作结果:删除Q的队头元素,并用e返回其值。
  • QueueTraverse(Q)

    • 初始条件:队列Q已存在且非空。
    • 操作结果:从队头到队尾,依次对Q的每个数据元素进行访问。

3. 注意事项

  • 与栈相似,本书后文中引用的队列都基于以上定义的队列类型。
  • 队列的数据元素类型应根据应用程序的需要来定义。

我的理解:

在我看来他其实就是像计算机内存申请一段空间然后用函数限制该段内存空间的行为使其模拟成具有现实生活中队列的特点

3.5.2 循环队列——队列的顺序表示和实现

  1. 队列的存储表示

    • 顺序表示
    • 链式表示
  2. 队列的顺序存储结构

    • 与顺序栈类似
    • 使用连续的存储单元存放从队头到队尾的元素
    • 使用两个整型变量 frontrear(头指针和尾指针)来指示队头和队尾位置
  3. 队列的初始化

    • 创建空队列时,设定 front = rear = 0
    • 新增队尾元素,尾指针 rear 增1
    • 删除队头元素,头指针 front 增1
    • 在非空队中,头指针指向队头元素,尾指针指向队尾元素的下一个位置
  4. “假溢出”问题

    • 当队列没有完全满,但由于受限制的操作导致无法继续添加元素时,称为“假溢出”
    • 解决办法:将顺序队列转变为循环队列(环状空间)
  5. 循环队列的特点

    • 通过模运算实现头、尾指针在顺序表空间内的“循环”移动
    • 不能仅通过头、尾指针的值来判断队列是“满”还是“空”
  6. 判断循环队列的状态

    • 队空的条件:Q.front = Q.rear
    • 队满的条件:(Q.rear + 1) % MAXQSIZE = Q.front
  7. 处理方法

    • 少用一个元素空间:当队列空间为m时,有m-1个元素视为队满
    • 使用标志位:设置一个标志位来区分队列是“空”还是“满”
  8. 循环队列的初始化算法

    • 动态分配一个大小为 MAXQSIZE 的数组空间
    • 设置头、尾指针为0表示队列为空

概念介绍:

  • 队列的存储表示分为两种:顺序表示和链式表示。
  • 队列的顺序存储结构需要两个整型变量:front(头指针)和rear(尾指针),来分别指示队头和队尾的位置。

队列的顺序存储结构

typedef struct {QElemType *base;  // 存储空间的基地址int front;       // 头指针int rear;        // 尾指针
} sqQueue;
  • 初始化时: front = rear = 0。
  • 新增队尾元素: rear增1。
  • 删除队头元素: front增1。

循环队列:

  • 为解决"假溢出"问题,将顺序队列变为环状的空间。
  • 通过取模运算,使头尾指针在顺序表空间内“循环”移动。

循环队列操作:

  1. 求队列长度

    • 对于非循环队列:长度 = rear - front
    • 对于循环队列:长度 = (rear - front + MAXQSIZE) % MAXQSIZE
    int QueueLength(SqQueue Q) {return (Q.rear - Q.front + MAXQSIZE) % MAXQSIZE;
    }
    
  2. 入队操作 (EnQueue)

    • 判断队列是否满。
    • 将新元素插入队尾。
    • 队尾指针加1。
    Status EnQueue(SqQueue &Q, QElemType e) {if ((Q.rear + 1) % MAXQSIZE == Q.front)return ERROR;Q.base[Q.rear] = e;Q.rear = (Q.rear + 1) % MAXQSIZE;return OK;
    }
    
  3. 出队操作 (DeQueue)

    • 判断队列是否为空。
    • 保存队头元素的值。
    • 队头指针加1。
    Status DeQueue(SqQueue &Q, QElemType &e) {if (Q.front == Q.rear)return ERROR;e = Q.base[Q.front];Q.front = (Q.front + 1) % MAXQSIZE;return OK;
    }
    

  4. 取队头元素

    • 当队列非空时,获取队头元素。
    QElemType GetHead(SqQueue Q) {if (Q.front != Q.rear)return Q.base[Q.front];
    }
    

注意点:

  • 循环队列中,队满和队空的判断不能仅根据头尾指针是否相等来进行。
  • 常见的两种处理方法:一是少用一个元素空间;二是另设一个标志位。

小结: 循环队列通过环形结构解决了顺序队列的"假溢出"问题,并通过模运算实现头尾指针的循环移动。循环队列的各种操作相对简单,但需要注意队空和队满的判断条件。

3.5.3 链队列 —— 队列的链式表示和实现

链队列概述:

  • 链队列是采用链式存储结构实现的队列。
  • 通常链队列使用单链表来表示。一个链队列需要两个分别指示队头和队尾的指针(称为头指针和尾指针)才能唯一确定。
  • 为了操作方便,链队列添加一个头节点,并使头指针始终指向头节点。

链队列的存储结构:

typedef struct QNode{QElemType data;struct QNode *next;
}QNode,*QueuePtr;typedef struct{QueuePtr front;  // 队头指针QueuePtr rear;   // 队尾指针
}LinkQueue;

操作与实现:

  1. 初始化:

    • 生成新节点作为头节点,队头和队尾指针指向此节点。
    • 头节点的指针域置空。
Status InitQueue(LinkQueue &Q){Q.front = Q.rear = new QNode;Q.front->next = NULL;return OK;
}
  1. 入队:

    • 为入队元素分配节点空间,用指针p指向。
    • 将新节点数据域置为e。
    • 将新节点插入到队尾。
    • 修改队尾指针为p。
    Status EnQueue(LinkQueue &Q, QElemType e){QNode* p = new QNode;p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;
    }
    
  2. 出队:

    • 判断队列是否为空。
    • 临时保存队头元素的值,以释放空间。
    • 修改头节点的指针域,指向下一个节点。
    • 若出队的是最后一个元素,将队尾指针重新赋值指向头节点。
    • 释放原队头元素的空间。
    Status DeQueue(LinkQueue &Q, QElemType &e){if(Q.front == Q.rear) return ERROR;QNode* p = Q.front->next;e = p->data;Q.front->next = p->next;if(Q.rear == p) Q.rear = Q.front;delete p;return OK;
    }
    
  3. 取队头元素:

    • 如果队列非空,返回当前队头元素的值,队头指针不变。
    QElemType GetHead(LinkQueue Q){if(Q.front != Q.rear)return Q.front->next->data;
    }
    

结论:

  • 链队列避免了循环队列设定最大队列长度的限制。如果无法预估所用队列的最大长度,链队列是一个更好的选择。

 

 

 总结:

重点:

  1. 链队列的定义: 链队列使用链式结构(单链表)来实现队列的功能。与数组实现的队列不同,它没有固定的大小限制。
  2. 存储结构: 由节点组成,每个节点有一个数据域和一个指针域。使用头指针和尾指针分别指向队列的头部和尾部。
  3. 基本操作:
    • 初始化: 创建一个空队列,通常由一个头节点组成,头尾指针均指向它。
    • 入队: 在尾部添加元素。
    • 出队: 从头部删除元素。
    • 取队头元素: 获取但不删除头部元素。

难点:

  1. 头尾指针的管理: 与单链表操作略有不同,需要注意在进行入队和出队操作时正确地更新头尾指针。
  2. 空间管理: 在出队操作时,不仅要更新指针,还要释放被删除节点的内存空间。
  3. 空队列与只有一个元素的队列的处理: 当队列为空或只有一个元素时,进行出队操作需特别注意头尾指针的变化。

易错点:

  1. 不更新尾指针: 在出队操作时,如果队列只有一个元素,出队后队列为空,此时需要将尾指针重新指向头节点。
  2. 内存泄漏: 出队操作时忘记释放节点的内存空间,会导致内存泄漏。
  3. 空队列操作: 在进行出队或取队头元素操作前,没有检查队列是否为空,可能导致错误或不确定的行为。
  4. 入队操作的指针更新顺序: 先连接新节点再移动尾指针,否则可能丢失队列的后续部分。

综上所述,链队列虽然提供了灵活性,但在实现时需要注意指针操作和内存管理,以确保正确性和效率。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/176268.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【案例实战】NodeJS+Vue3+MySQL实现列表查询功能

这篇文章&#xff0c;给大家带来一个列表查询的功能&#xff0c;从前端到后端的一个综合案例实战。 采用vue3作为前端开发&#xff0c;nodejs作为后端开发。 首先我们先来看一下完成的页面效果。点击分页&#xff0c;可以切换到上一页、下一页。搜索框可以进行模糊查询。 后端…

视频格式高效转换:MP4视频批量转MKV格式的方法

随着数字媒体技术的不断发展&#xff0c;视频格式转换已经成为了我们日常工作中不可或缺的一部分。不同的视频格式适用于不同的场景和设备&#xff0c;因此将视频从一种格式转换为另一种格式往往是我们必须完成的任务。在本文中&#xff0c;我们将重点介绍如何运用云炫AI智剪高…

C#中LINQtoSQL的设置与连接

目录 一、首次安装LinqToSql类 二、非首次安装LinqToSql类 1.接受原有数据库连接 2.建立新的数据库连接 3.建立本地数据库连接 LINQ&#xff08;Language-Integrated Query&#xff0c;语言集成查询&#xff09;是微软公司提供的一项新技术&#xff0c;它能够将查询功能直…

uniapp 中添加 vconsole

uniapp 中添加 vconsole 一、安装 vconsole npm i vconsole二、使用 vconsole 在项目的 main.js 文件中添加如下内容 // #ifdef H5 // 提交前需要注释 本地调试使用 import * as vconsole from "vconsole"; new vconsole() // 使用 vconsole // #endif三、成功

MySQL - 索引详解以及优化;Explain执行计划

官网文档 MySQL :: MySQL 5.7 Reference Manual :: 8.3 Optimization and Indexes Mysql优化&#xff08;出自官方文档&#xff09; - 第八篇&#xff08;索引优化系列&#xff09; 目录 Mysql优化&#xff08;出自官方文档&#xff09; - 第八篇&#xff08;索引优化系列&…

玩转硬件之Micro:bit的玩法(一)

写在前面 这么长时间以来一直在玩软件, 好像软件还没有研究明白&#xff0c;因为工作的转变&#xff0c;又开始接触到硬件&#xff0c;既然开始触碰到硬件了&#xff0c;也想记录一下。有的时候想想要不要写这段前言&#xff0c;但是不写又觉得比较突兀&#xff0c;好端端的怎…

SpringBoot整合Gateway 的Demo(附源码)

源码&#xff0c;可直接下载 Gateway模块 Gateway 的父pom.xml <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://www.w3.org/2001/XMLSchema-instance"xsi:sc…

二叉树OJ题(检查两颗数是否相同、另一棵树的子树、翻转二叉树、判断平衡二叉树)

文章目录 二叉树OJ题一、 检查两颗数是否相同1.思路2.解题步骤3.代码 二、另一棵树的子树1.思路2.代码 三、翻转二叉树1.思路2.解题步骤3.代码 四、判断平衡二叉树1.思路2.代码 二叉树OJ题 一、 检查两颗数是否相同 1.思路 1.两个树&#xff0c;在保证结构相同的同时&#xff0…

iOS 使用dsym符号化线上crash日志(ips文件)

1.获取崩溃日志 可以iphone连接mac复制当时的崩溃日志。 Xcode->Window->Devices View Device Logs 如果是testflight的崩溃是可以分享的&#xff0c;分享出来可能是ips文件。 把文件名称改成my.crash 使用脚本把新版本崩溃日志转成老版本格式 这一步不是必须的&…

如何知道服务器的某个端口是否打开

注意&#xff1a;服务器的TCP端口&#xff0c;比如1886端口&#xff0c;出方向 和进方向 都打开才可以用 1、telnet 命令&#xff1a;telnet ip port&#xff0c;port即端口&#xff0c;我们一般最常见的命令就是telnet&#xff0c;但是telnet使用的是tcp协议&#xff0c;换句…

[云原生案例1.] 构建LNMP架构并运行Wordpress个人博客平台

文章目录 1. 当前需求2. 前置准备3. 搭建过程3.1 创建自定义网络3.2 部署并配置nginx3.2.1 创建工作目录并上传相关软件包3.2.2 解压缩相关软件包3.2.3 编写Dockerfile文件3.2.4 编写nginx.conf文件3.2.5 创建nginx镜像3.2.6 运行容器 3.3 部署并配置mysql3.3.1 创建工作目录3.…

在科技展厅设计中,如何通过空间规划来突出展品和主题?

数字多媒体技术在各行业内的广泛应用&#xff0c;使内容展览展示技术得到了更新&#xff0c;尤其是在科技展厅设计中&#xff0c;更是将各类多媒体互动装置的优势发挥到了极致&#xff0c;为观众提供现代化的感官体验&#xff0c;而这其中有效的空间规划对于现代化科技展厅的效…

3D模拟场景开发引擎

在3D工程模拟开发中&#xff0c;有一些专门的引擎和工具可供选择&#xff0c;以帮助您创建逼真的三维模拟和模型。以下是一些用于3D工程模拟的开发引擎和工具&#xff0c;希望对大家有所帮助。北京木奇移动技术有限公司&#xff0c;专业的软件外包开发公司&#xff0c;欢迎交流…

最新Ubuntu20.04安装教程(图文)

总的来说&#xff0c;安装Ubantu包含以下三个步骤&#xff1a; 一、安装虚拟机 二、Ubuntu镜像下载 三、虚拟机配置 一、安装虚拟机 选择安装VMware Workstation&#xff0c;登录其官网下载安装包&#xff0c;链接如下&#xff1a; 下载 VMware Workstation Pro | CN 下载…

iOS实现弹簧放大动画

效果图 实现代码 - (void)setUpContraints {CGFloat topImageCentery (SCREEN_HEIGHT - 370 * PLUS_SCALE) / 2;[self.topIconView mas_makeConstraints:^(MASConstraintMaker *make) {make.centerX.mas_equalTo(0);make.centerY.equalTo(self.view.mas_top).with.offset(t…

面试官:聊聊kafka线上使用会有哪些问题?

哪些环节会造成消息丢失&#xff1f; 首先说说哪些环节会丢消息 消息生产者&#xff1a; &#xff08;1&#xff09;acks0&#xff1a; 表示producer不需要等待任何broker确认收到消息的回复&#xff0c;就可以继续发送下一条消息。性能最高&#xff0c;但是最容易丢消 息。大…

关键点检测、姿态识别、目标检测、车牌识别等项目部署代码+数据集汇总

一、AI健身计数 1、图片视频检测 &#xff08;cpu运行&#xff09;&#xff1a; 注&#xff1a;左上角为fps&#xff0c;左下角为次数统计。 1.哑铃弯举&#xff1a;12&#xff0c;14&#xff0c;16 详细环境安装教程&#xff1a;pyqt5AI健身CPU实时检测mediapipe 可视化界面…

VS LiveShare使用操作介绍

VS LiveShare的使用教程 文章简介下载过程 文章简介 本篇文章主要介绍了如何安装和使用LiveShare的过程。 下载过程 1.在扩展->管理扩展&#xff0c;搜索Live Share后&#xff0c;下载对应的安装包&#xff0c;安装后对VS进行重启 2.安装后界面右上角会出现Live Share标…

docker环境安装+maven依赖继承问题

1&#xff0c;docker环境安装 我们使用yum指令进行安装&#xff0c;分别cmd运行&#xff1a; yum install -y yum-utils device-mapper-persistent-data lvm2 yum-contig-manager --add-repo https://download.docker.com/linux/centos/docker-ce.rep具体解释如下&#xff1a;…

目标检测中常见指标 - mAP

文章目录 1. 评价指标2. 计算示例3. COCO评价指标 1. 评价指标 在目标检测领域&#xff0c;比较常用的两个公开数据集&#xff1a;pascal voc和coco。 目标检测与图像分类明显差距是很大的&#xff0c;在图像分类中&#xff0c;我们通常是统计在验证集当中&#xff0c;分类正…