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

考研篇——数据结构王道3.2.2_队列的顺序实现

目录

  • 1.实现方式说明
  • 2.代码实现
    • 2.1
      • 2.1.1 代码1
      • 2.1.2 代码2
      • 2.1.3 代码3
    • 2.2
      • 2.2.1 代码4
      • 2.2.5 代码5
      • 2.2.6 代码6
  • 总结

1.实现方式说明

多在选择题中考察

队尾指针(rear)有两种指向方式:

  • 队尾指针指向队尾元素的位置,
  • 队尾指针指向队尾元素的下一个位置。

区分队空与队满:

  1. 牺牲一个存储空间,利用队头元素和队尾元素的相对位置来区分队空与队满。
  2. 增加一个变量size记录队列元素个数
  3. 增加一个变量tag记录操作是删除(tag为0)还是插入(tag为1),插入后rear(队尾)=front是队满,删除后rear=front是队空。

所以队列的实现一共有六种情况
在这里插入图片描述
书写代码注意操作实现的前提条件,也就是逻辑问题:

  1. 查、删的前提是队列非空,要进行判断;
  2. 插入的前提是队列不满,要进行判断。

静态数组实现的队列是循环队列,为了循环利用空间,rear的下一个元素为(rear+1)%MaxSize.

2.代码实现

2.1

2.1.1 代码1

C++静态数组实现rear(队尾指针)指向队尾元素的下一个元素,且牺牲一个存储空间来区分队满和队空的判断。
这种情况下队列的长度为(rear+MaxSize-front)%MaxSize.

#include <stdio.h>
#include <assert.h>
#define MaxSize 10
typedef int ElemType;
typedef struct {ElemType data[MaxSize];int front, rear;
}SqQueue;
void InitQueue(SqQueue &Q)
{Q.rear = Q.front = 0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.rear == Q.front)return true;elsereturn false;
}
bool EnQueue(SqQueue& Q,ElemType x) {if ((Q.rear + 1) % MaxSize == Q.front)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{if (QueueEmpty(Q))return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}
bool GetHead(SqQueue Q, ElemType& x)
{//assert(!QueueEmpty(Q));if (QueueEmpty(Q))return false;x = Q.data[Q.front];return true;
}
void testQueue()
{SqQueue Q;InitQueue(Q);//printf("%d\n",QueueEmpty(Q));EnQueue(Q, 5);int x = 0;DeQueue(Q, x);GetHead(Q, x);printf("%d\n",x);
}
int main() {testQueue();return 0;
}

后续代码与代码1相同的部分省略

2.1.2 代码2

C++静态数组实现rear(队尾指针)指向队尾元素的下一个元素,且增加一个变量size记录队列长度来区分队满和队空的判断。

//队尾指针指向队尾元素
//引入size变量来记录队列元素个数
typedef struct {ElemType data[MaxSize];int front, rear;int size;
}SqQueue;
void InitQueue(SqQueue& Q)
{Q.rear = Q.front = 0;Q.size = 0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.size==0)return true;elsereturn false;
}
bool EnQueue(SqQueue& Q, ElemType x) {if (Q.size==MaxSize)//队满的判断return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;Q.size++;return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{if (QueueEmpty(Q))return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;Q.size--;return true;
}

2.1.3 代码3

C++静态数组实现rear(队尾指针)指向队尾元素的下一个元素,且增加一个变量tag来记录判断前队列的上一步操作是入队还是出队来区分队满和队空的判断。

//队尾指针指向队尾元素
//引入tag变量来记录队列元素个数,元素入队tag为1,出队tag为1
typedef struct {ElemType data[MaxSize];int front, rear;int tag;
}SqQueue;
void InitQueue(SqQueue& Q)
{Q.rear = Q.front = 0;Q.tag = 0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.rear == Q.front&&Q.tag==0)return true;elsereturn false;
}
bool EnQueue(SqQueue& Q, ElemType x) {if (Q.rear == Q.front && Q.tag == 1)return false;Q.data[Q.rear] = x;Q.rear = (Q.rear + 1) % MaxSize;Q.tag = 1;return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{if (QueueEmpty(Q))return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;Q.tag = 0;return true;
}

其实我们遇到的问题是,Q.rear==Q.front可以表示队空和队满两种状态,那么我们考虑怎么将二者分开呢?1.牺牲一个存储单元,将队满对队空的判断条件区别开;2.增加size变量;3.增加tag变量,只有入队之后才有可能队满,出队之后才有可能队空。
三种情况的对比图如下:
在这里插入图片描述

2.2

2.2.1 代码4

C++静态数组实现rear(队尾指针)指向队尾元素,且牺牲一个存储空间来区分队满和队空的判断。

//队尾指针指向队尾元素下一个元素
//牺牲一个存储空间
void InitQueue(SqQueue& Q)
{Q.rear = -1;Q.front = 0;
}
bool QueueEmpty(SqQueue Q)
{if ((Q.rear + 1) % MaxSize == Q.front)return true;elsereturn false;
}
bool EnQueue(SqQueue& Q, ElemType x) {if ((Q.rear + 2) % MaxSize == Q.front)return false;Q.rear = (Q.rear + 1) % MaxSize;Q.data[Q.rear] = x;return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{if (QueueEmpty(Q))return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;return true;
}

2.2.5 代码5

C++静态数组实现rear(队尾指针)指向队尾元素,且增加一个变量size记录队列长度来区分队满和队空的判断。

typedef struct {ElemType data[MaxSize];int front, rear;int size;
}SqQueue;
void InitQueue(SqQueue& Q)
{Q.rear = -1;Q.front = 0;Q.size=0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.size==0)return true;elsereturn false;
}
bool EnQueue(SqQueue& Q, ElemType x) {if (Q.size==MaxSize)return false;Q.rear = (Q.rear + 1) % MaxSize;Q.data[Q.rear] = x;Q.size++;return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{if (QueueEmpty(Q))return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;Q.size--;return true;
}

2.2.6 代码6

C++静态数组实现rear(队尾指针)指向队尾元素的下一个元素,且增加一个变量tag来记录判断前队列的上一步操作是入队还是出队来区分队满和队空的判断。

typedef struct {ElemType data[MaxSize];int front, rear;int tag;
}SqQueue;
void InitQueue(SqQueue& Q)
{Q.rear = -1;Q.front = 0;Q.tag=0;
}
bool QueueEmpty(SqQueue Q)
{if (Q.tag==0)return true;elsereturn false;
}
bool EnQueue(SqQueue& Q, ElemType x) {if ((Q.rear + 1) % MaxSize == Q.front &&Q.tag==0)return false;Q.rear = (Q.rear + 1) % MaxSize;Q.data[Q.rear] = x;Q.tag=1;return true;
}
bool DeQueue(SqQueue& Q, ElemType& x)
{if (QueueEmpty(Q))return false;x = Q.data[Q.front];Q.front = (Q.front + 1) % MaxSize;Q.tag=0;return true;
}

总结

以上部分为王道课件代码,部分为自写代码,有问题欢迎交流。
注:王道本身图画得很形象,此处不再做图,有兴趣的伙伴可以去看一下王道该章节的内容。

相关文章:

考研篇——数据结构王道3.2.2_队列的顺序实现

目录 1.实现方式说明2.代码实现2.12.1.1 代码12.1.2 代码22.1.3 代码3 2.22.2.1 代码42.2.5 代码52.2.6 代码6 总结 1.实现方式说明 多在选择题中考察 队尾指针&#xff08;rear&#xff09;有两种指向方式&#xff1a; 队尾指针指向队尾元素的位置&#xff0c;队尾指针指向…...

从零开始理解 Trie 树:高效字符串存储与查找的利器【自动补全、拼写检查】

题目分析 这道题让我们实现一个 Trie 类&#xff08;也称为前缀树&#xff09;&#xff0c;以便高效地插入和查询字符串。前缀树是一种特殊的树形数据结构&#xff0c;适用于快速存储和检索字符串数据集中的键&#xff0c;比如实现 自动补全 和 拼写检查。 题目要求 Trie 类…...

关于sse、websocket与流式渲染

一、SSE是什么&#xff1f; 网络中的 SSE (Server-Sent Events) 是一种服务器向浏览器单向推送数据的机制&#xff0c;常用于需要实时更新的数据传输&#xff0c;如新闻推送、股票行情、聊天应用等。 SSE 的特点&#xff1a; 单向通信&#xff1a;服务器向客户端推送数据&…...

Python 语法与数据类型详解

Python 语法与数据类型详解 Python 以其简洁易读的语法和丰富多样的数据类型在编程领域占据重要地位。深入理解 Python 的语法和数据类型是掌握这门语言的关键。 一、Python 语法概述 &#xff08;一&#xff09;缩进规则 Python 独特的缩进规则是其语法的重要特征之一。与…...

LeetCode题练习与总结:扁平化嵌套列表迭代器--341

一、题目描述 给你一个嵌套的整数列表 nestedList 。每个元素要么是一个整数&#xff0c;要么是一个列表&#xff1b;该列表的元素也可能是整数或者是其他列表。请你实现一个迭代器将其扁平化&#xff0c;使之能够遍历这个列表中的所有整数。 实现扁平迭代器类 NestedIterato…...

51单片机快速入门之 AD(模数) DA(数模) 转换 2024/10/25

51单片机快速入门之 AD(模数) DA(数模) 转换 2024/10/25 声明:本文图片来源于网络 A模拟信号特点: 电压或者电流 缓慢上升 随着时间连续缓慢上升或下降 D数字信号特点:电压或者电流 保持一段时间的高/低电平 状态 / 突变 (高电压瞬间低电压) 数字电路中 通常将0-1v电压称…...

Typora 、 Minio and PicGo 图床搭建

流程介绍 本地安装Typora笔记工具拥有一台装有docker的服务器配置minio云图床管理控制页面下载PicGo上传工具服务器Docker环境搭建—Ubuntu系统 删除旧docker的所有依赖(非root用户) # 删除docker及安装时自动安装的所有包 sudo apt-get autoremove docker docker-ce docker…...

【计网】UDP Echo Server与Client实战:从零开始构建简单通信回显程序

目录 前言&#xff1a; 1.实现udpserver类 1.1.创建udp socket 套接字 --- 必须要做的 socket&#xff08;&#xff09;讲解 代码实现&#xff1a;​编辑 代码讲解&#xff1a; 1.2.填充sockaddr_in结构 代码实现&#xff1a; 代码解析&#xff1a; 1.3.bind sockfd和…...

微服务网关Zuul

一、Zuul简介 Zuul是Netflix开源的微服务网关&#xff0c;包含对请求的路由和过滤两个主要功能。 1&#xff09;路由功能&#xff1a;负责将外部请求转发到具体的微服务实例上&#xff0c;是实现外部访问统一入口的基础。 2&#xff09;过滤功能&#xff1a;负责对请求的过程…...

BuildCTF线上赛WP

Build::CTF flag不到啊战队--WP 萌新战队&#xff0c;还请多多指教~ 目录 Build::CTF flag不到啊战队--WP Web ez!http find-the-id Pwn 我要成为沙威玛传奇 Misc what is this? 一念愚即般若绝&#xff0c;一念智即般若生 别真给我开盒了哥 四妹&#xff0c;你听…...

《使用Gin框架构建分布式应用》阅读笔记:p143-p207

《用Gin框架构建分布式应用》学习第10天&#xff0c;p143-p207总结&#xff0c;总计65页。 一、技术总结 1.auth0 本人实际工作中未遇到过&#xff0c;mark一下&#xff0c;参考&#xff1a;https://auth0.com/。 2.使用template (1)c.File() (2)router.Static() (3)rou…...

华为网络管理配置实例

目录 组网需求 数据规划 配置思路 操作步骤 结果验证 配置脚本 管理员可以通过eSight网管系统对FW进行监控和管理&#xff0c;接收FW的告警。 组网需求 如图1所示&#xff0c;某企业在网络边界处部署了FW作为安全网关&#xff0c;并部署了eSight网管系统对网络设备进行集中…...

大语言模型数据处理方法(基于llama模型)

文章目录 前言一、基于huggingface的DataCollatorForSeq2Seq方法解读1、DataCollatorForSeq2Seq方法2、batch最长序列填充3、指定长度填充二、构建大语言模型数据加工模块1、数据读取2、数据加工1、数据格式2、预训练(pretrain)数据加工3、微调(sft)数据加工①、sft数据加工…...

爱奇艺大数据多 AZ 统一调度架构

01# 导语 爱奇艺大数据技术广泛应用于运营决策、用户增长、广告分发、视频推荐、搜索、会员营销等场景&#xff0c;为公司的业务增长和用户体验提供了重要的数据驱动引擎。 多年来&#xff0c;随着公司业务的发展&#xff0c;爱奇艺大数据平台已积累了海量数据&#xff0c;这…...

【C++篇】栈的层叠与队列的流动:在 STL 的韵律中探寻数据结构的优雅之舞

文章目录 C 栈与队列详解&#xff1a;基础与进阶应用前言第一章&#xff1a;栈的介绍与使用1.1 栈的介绍1.2 栈的使用1.2.1 最小栈1.2.2 示例与输出 1.3 栈的模拟实现 第二章&#xff1a;队列的介绍与使用2.1 队列的介绍2.2 队列的使用2.2.1 示例与输出 2.3 队列的模拟实现2.3.…...

使用 Flask 实现简单的登录注册功能

目录 1. 引言 2. 环境准备 3. 数据库设置 4. Flask 应用基本配置 5. 实现用户注册 6. 实现用户登录 7. 路由配置 8. 创建前端页面 9. 结论 1. 引言 在这篇文章中&#xff0c;我们将使用 Flask 框架创建一个简单的登录和注册系统。Flask 是一个轻量级的 Python Web 框架…...

计算机毕业设计Python+大模型微博情感分析 微博舆情预测 微博爬虫 微博大数据 舆情分析系统 大数据毕业设计 NLP文本分类 机器学习 深度学习 AI

温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 温馨提示&#xff1a;文末有 CSDN 平台官方提供的学长联系方式的名片&#xff01; 《Python大模型微博情感分析…...

CTF--Misc题型小结

&#xff08;萌新笔记&#xff0c;多多关照&#xff0c;不足之处请及时提出。&#xff09; 不定时更新~ 目录 密码学相关 文件类型判断 file命令 文件头类型 strings读取 隐写术 尺寸修改 文件头等缺失 EXIF隐写 thumbnail 隐写 文件分离&提取 binwalk foremo…...

深度学习系列——RNN/LSTM/GRU,seq2seq/attention机制

1、RNN/LSTM/GRU可参考&#xff1a; https://zhuanlan.zhihu.com/p/636756912 &#xff08;1&#xff09;对于这里面RNN的表示中&#xff0c;使用了输入x和h的拼接描述&#xff0c;其他公式中也是如此 &#xff08;2&#xff09;各符号图含义如下 2、关于RNN细节&#xff0c;…...

通过call指令来学习指令摘要表的细节

E8 cw cw 表示E8后面跟随2 字节 (什么数不知道) rel16 指在与指令同一代码段内的相对地址偏移 D ,指向Instruction Operand Encoding 表中的D列, 他告诉我们 操作数1 是一个0FFSET N.S. 在64位模式下&#xff0c;某些指令需要使用“地址覆盖前缀”&#xff08;address over…...

10分钟使用Strapi(无头CMS)生成基于Node.js的API接口,告别繁琐开发,保姆级教程,持续更新中。

一、什么是Strapi&#xff1f; Strapi 是一个开源的无头&#xff08;headless&#xff09; CMS&#xff0c;开发者可以自由选择他们喜欢的开发工具和框架&#xff0c;内容编辑人员使用自有的应用程序来管理和分发他们的内容。得益于插件系统&#xff0c;Strapi 是一个灵活的 C…...

创建插件 DLL 项目

Step 1: 创建插件 DLL 项目 在 Visual Studio 中创建一个新的 DLL 项目&#xff0c;并添加以下文件和代码。 头文件&#xff1a;CShapeBase.h cpp 复制代码 #pragma once #include <afxwin.h> // MFC 必需头文件 #include <string> #include <vector> #i…...

OpenCV双目相机外参标定C++

基于OpenCV库实现双目测量系统外参标定过程。通过分析双目测量系统左右相机拍摄的棋盘格标定板图像&#xff0c;包括角点检测、立体标定、立体校正和畸变校正的步骤&#xff0c;获取左右相机的相对位置关系和姿态。 a.检测每张图像中的棋盘格角点&#xff0c;并进行亚像素级精…...

【GESP】C++一级练习BCQM3055,4位数间隔输出

一级知识点取余、整除运算和格式化输出知识点应用。其实也可以用string去处理&#xff0c;那就属于GESP三级的知识点范畴了&#xff0c;孩子暂未涉及。 题目题解详见&#xff1a;https://www.coderli.com/gesp-1-bcqm3055/ https://www.coderli.com/gesp-1-bcqm3055/https://w…...

纯血鸿蒙的最难时刻才开始

关注卢松松&#xff0c;会经常给你分享一些我的经验和观点。 纯血鸿蒙(HarmonyOS NEXT)也正式发布了&#xff0c;绝对是一个历史性时刻&#xff0c;但最难的鸿蒙第二个阶段&#xff0c;也就是生态圈的建设&#xff0c;才刚刚开始。 目前&#xff0c;我劝你现在不要升级到鸿蒙…...

记一个mysql的坑

数据库表user&#xff0c; 存在一个name字段&#xff0c;字段为varchar类型 现在user表有这么两条记录: idnameageclass1NULL18一班2lisi20二班 假如我根据下面这一条件去更新&#xff0c;更新成功数据行显示为0 update user set age 19 where age 18 and class “一班”…...

Java中的设计模式:单例模式详解

摘要 单例模式&#xff08;Singleton Pattern&#xff09;是Java中最常用的设计模式之一&#xff0c;属于创建型模式。它的主要目的是确保一个类在系统中只有一个实例&#xff0c;并提供一个全局访问点来访问该实例。 1. 单例模式的定义 单例模式确保一个类只有一个实例&…...

NanoTrack原理与转tensorrt推理

文章目录 前言一、NanoTrack 工作原理二、运行demo与转换tensorrt模型2.1 运行pt模型demo2.2 转onnx模型2.3 转tensorrt模型2.4 运行trt模型推理 三、推理速度对比总结 前言 NanoTrack 是一种轻量级且高效的目标跟踪算法&#xff0c;基于Siamese网络架构&#xff0c;旨在在资源…...

YOLO11改进 | 卷积模块 | 卷积模块替换为选择性内核SKConv【附完整代码一键运行】

秋招面试专栏推荐 &#xff1a;深度学习算法工程师面试问题总结【百面算法工程师】——点击即可跳转 &#x1f4a1;&#x1f4a1;&#x1f4a1;本专栏所有程序均经过测试&#xff0c;可成功执行&#x1f4a1;&#x1f4a1;&#x1f4a1; 本文给大家带来的教程是将YOLO11的卷积替…...

CentOS进入单用户模式进行密码重置

一、单用户模式介绍 单用户模式是一种特殊的启动模式&#xff0c;主要用于系统维护和故障排除。在单用户模式下&#xff0c;系统以最小化的状态启动&#xff0c;只有最基本的系统服务会被加载&#xff0c;通常只有root用户可以登录。这种模式提供了对系统的完全控制&#xff0…...

做任务给佣金的网站/亚马逊查关键词排名工具

题目链接&#xff1a;http://61.187.179.132/JudgeOnline/problem.php?id1856 题意&#xff1a;有n个1和m个0组成的串&#xff0c;使得任意前k个中1的个数不少于0的个数。有多少种这样的串&#xff1f; 思路&#xff1a;设1为向(1,1)方向走&#xff0c;0为向(1,-1)方向走。那么…...

led高端网站建设/自动的网站设计制作

现在微信的用户体验一直被产品经理们所推崇,今天这里具体分析一下微信在WebView的进度条上怎么提升用户体验.最终微信的加载进度条的效果图网络正常的状态&#xff0c;分为两种加载速度,前部分正常速度加载,后边速度特意放慢,让用户感觉到你在非常卖力的在进行网络请求.断开网络…...

腾讯官方网站建设/网站 推广

资料下载 coding无法使用浏览器打开&#xff0c;必须用git工具下载&#xff1a; git clone https://e.coding.net/weidongshan/linux/doc_and_source_for_drivers.git视频观看 百问网驱动大全 先学习输入系统应用编程 1. 百问网Linux视频体系 2. 建议 在《Linux系列教程之…...

漯河网站优化/成功营销案例分享

一、分析什么是顺序表&#xff1f;顺序表是指用一组地址连续的存储单元依次存储各个元素&#xff0c;使得在逻辑结构上相邻的数据元素存储在相邻的物理存储单元中的线性表。一个标准的顺序表需要实现以下基本操作&#xff1a;1、初始化顺序表2、销毁顺序表3、清空顺序表4、检测…...

iis6.1的网站建设及权限设置/互联网下的网络营销

//阿里面试//2010 年&#xff0c;阿里正当红。那年 BAT 的名气还没有现今那么响亮。就业的时候&#xff0c;很多毕业生还是会选择 HP, IBM, EMC, SONY, ORACLE&#xff0c;Microsoft 等一类的外企。这些外企在毕业生眼中代表的是名牌&#xff0c;权威&#xff0c;以及自由&…...

做网站可能遇到的困难/优化营商环境条例解读

###转载于:https://www.cnblogs.com/tinaluo/p/9278671.html...