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

数据结构——栈和队列(队列的定义、顺序队列以及链式队列的基本操作)

目录

队列(queue)的定义

顺序队——队列的顺序表示和实现

顺序队列(循环队列)的类型定义

顺序队列上溢问题的解决方法

​编辑

循环队列的基本操作

队列的基本操作——队列的初始化

队列的基本操作——求队列的长度

队列的基本操作——循环队列入队

队列的基本操作——循环队列出队

队列的基本操作——取队头元素

队列的基本操作——取队尾元素

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

链队列的类型定义

链队列的基本操作

链队列的基本操作——链队列初始化

链队列的基本操作——链队列销毁

链队列的基本操作——将元素e入队

链队列的基本操作——将元素e出队


队列(queue)的定义

顺序队——队列的顺序表示和实现

  • 队列和栈一样,也是限定只能在表的“端点”进行的线性表
  • 队列在插入的时候,只能在表尾进行插入,在删除的时候,只能在表头进行删除。(先进先出),表尾即队尾,表头即队头
  • 栈和队列是线性表的子集(是插入和删除位置受限的线性表)
  • 由于队列的操作具有先进先出的特性,使得队列成为程序设计中解决类似排队问题的有用工具。
  • 队列的逻辑结构与同线性表相同,仍为一对一关系。
  • 队列的存储结构有顺序队和链队,以循环顺序队列更常见。
  • 关键是掌握入队出队操作,具体实现依顺序队或链队的不同而不同。

顺序队列(循环队列)的类型定义

  • 队列的顺序表示——用一维数组base[MAXQSIZE]
#define MAXQSIZE 100 //最大队列长度
typedef struct
{QElemType* base; //初始化的动态分配存储空间int front; //头指针(队头元素的下标)int rear;  //尾指针(队尾元素的下标)
}SqQueue;
顺序队列上溢问题的解决方法

初始:front = rear = 0

入队:base[rear] = x;  rear++;

出队:x = base[front]; front++;

空队标志:front == rear

上面的假设存在什么问题呢?有下面的两种情况:

解决上溢出的方法

1、将队中元素依次向队头方向移动。

缺点:浪费时间,每移动一次,队中元素都要移动。

2、将队空间设想成一个循环的表,即分配给队列的m个存储单元可以循环使用,当rear为maxqsize时,若向量的开始端空着,又可以从头使用空着的空间。当front为maxqsize时,也是一样。

解决假上溢的方法——引入循环队列

base[0]接在base[MAXQSIZE-1]之后,若rear+1==M,则令rear = 0;

实现方法:利用%运算

插入元素

Q.base[Q.rear] = x;  //base为动态分配的一维数组
Q.rear = (Q.rear + 1) % MAXQSIZE;

删除元素

x = Q.base[Q.front];
Q.front = (Q.front + 1) % MAXQSIZE;

将上述方法想象成循环队列,如下图:

如果这样操作的话就会出现新的问题,就是队空和队满的时候,front = rear 

那么如何解决这个问题呢,我们接下面往下分析:

解决方案:

1、另外设一个标志以区别队空、队满

2、另设一个变量,记录元素个数

3、少用一个元素空间循环队列解决队满时判断方法——少用一个元素空间

循环队列的基本操作

  • 队列的基本操作——队列的初始化
#define MAXQSIZE 100
typedef int QElemType;
Status InitQueue(SqQueue& Q) //C++中的引用操作,不是单纯的值拷贝,类似给变量取别名,还是同一块内存
{Q.base = new QElemType[MAXQSIZE]; //分配数组空间,利用C++关键字new实现//.base = malloc(MAXQSIZE*sizeof(QElemType)); //C语言实现if (!Q.base)exit(OVERFLOW);Q.front = Q.rear = 0;return OK;
}
  • 队列的基本操作——求队列的长度
int QueueLength(SqQueue Q)
{return ((Q.rear-Q.front+MQXQSIZE)%MAXQSIZE);
}
  • 队列的基本操作——循环队列入队
Status EnQueue(SqQueue& Q, QlemType e)
{if ((Q.rear + 1) % MAXQSIZE == Q.front)return ERROR;  //队满Q.base[Q.rear] = e;    //新元素加入队尾Q.rear = (Q.rear + 1) % MAXQSIZE;//队尾指针+1return OK;
}
  • 队列的基本操作——循环队列出队
Status EnQueue(SqQueue& Q, QlemType &e)
{if ((Q.rear = Q.front)return ERROR;  //队空e = Q.base[front];    //保存队头元素Q.front = (Q.front + 1) % MAXQSIZE;//队头指针+1return OK;
}
  • 队列的基本操作——取队头元素
SElemType GetHead(SqQueue Q)
{if(Q.front!=Q.rear) //队列不为空return Q.base[Q.front];//返回队头指针元素的值,队头指针不变
}
  • 队列的基本操作——取队尾元素

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

        若用户无法估计所用队列的长度,则宜采用链队列

链队列的类型定义

#define MAXQSIZE 100  //最大队列长度
typedef struct Qnode
{QElemType data;struct Qnode* next;
}QNode,*QueuePtr;  //一个是结点类型,一个是指向结点的指针typedef struct
{QueuePtr front;//队头指针QueuePtr rear; //队尾指针
}LinkQueue; //链式队列

链队列的基本操作

  • 链队列的基本操作——链队列初始化
Status InitQueue(LinkQueue& Q)
{Q.front = Q.rear = (QueuePtr)malloc(sizeof(QNode));Q.front->next = NULL;return OK;
}
  • 链队列的基本操作——链队列销毁

Status DestroyQueue(LinkQueue& Q)
{while (Q.front) {p = Q.front->next;//指针p指向头结点的下一结点free(Q.front);    //释放头结点Q.front = p;      //把指针指向的结点变为新的头结点}
}
  • 链队列的基本操作——将元素e入队
Status EnQueue(LinkQueue& Q, QElemType e) {p = (QueuePtr)malloc(sizeof(QNode));if (!p) exit(OVERFLOW);p->data = e;p->next = NULL;Q.rear->next = p;Q.rear = p;return OK;
}
  • 链队列的基本操作——将元素e出队
思路:
p=Q.front->next;  //暂存头结点的下一个,也就是第一结点
e=p->data;        //将要删除的队头的数据存下来
Q.front->next=p->next; //将头结点指向第二结点
delete p;   //释放要删除的元素的内存空间代码实现:
Status DeQueue (LinkQueue &Q,QElemType &e)
{if(Q.front==Q.rear) return ERROR;p=Q.front->next;e=p->data;Q.front->next=p->next;if(Q.rear==p) Q.rear=Q.front;delete p;return OK;
}
  • 链队列的基本操作——求链队列的队头元素
Status GetHead (LinkQueue Q QElemType &e)
{if(Q.front==Q.rear) return ERROR;e=Q.front->next->data;return OK;
}

相关文章:

数据结构——栈和队列(队列的定义、顺序队列以及链式队列的基本操作)

目录 队列(queue)的定义 顺序队——队列的顺序表示和实现 顺序队列(循环队列)的类型定义 顺序队列上溢问题的解决方法 ​编辑 循环队列的基本操作 队列的基本操作——队列的初始化 队列的基本操作——求队列的长度 队列的…...

el-table 的单元格 + 图表 + 排序

<el-table border :data"tableDataThree" height"370px" style"width: 100%"><el-table-column :key"activeName 8" width"50" type"index" label"序号" align"center"></el…...

FPGA第 9 篇,Verilog 中的关键字和基数

前言 在 Verilog 中&#xff0c;关键字&#xff08;Keywords&#xff09;和基数&#xff08;Radix&#xff09;是语言的重要组成部分&#xff0c;它们有助于描述和定义硬件设计。上期分享了 Verilog 的基本使用&#xff0c;以及数据类型、逻辑值和算数运算符的简单应用&#x…...

什么是单元测试?怎么做?

&#x1f345; 点击文末小卡片 &#xff0c;免费获取软件测试全套资料&#xff0c;资料在手&#xff0c;涨薪更快 一、什么是单元测试&#xff1f; 单元测试&#xff08;unit testing&#xff09;&#xff0c;是指对软件中的最小可测试单元进行检查和验证。至于“单元”的大小…...

论文复现--基于LeNet网络结构的数字识别

前言 一直就听说学习深度学习无非就是看论文&#xff0c;然后复现&#xff0c;不断循环&#xff0c;这段时间也看了好几篇论文(虽然都是简单的)&#xff0c;但是对于我一个人自学&#xff0c;复现成功&#xff0c;我感觉还是挺开心的 本人初学看论文的思路&#xff1a;聚焦网络…...

Vue3 响应式工具函数isRef()、unref()、isReactive()、isReadonly()、isProxy()

isRef() isRef()&#xff1a;检查某个值是否为 ref。 isRef函数接收一个参数&#xff0c;即要判断的值。如果该参数是由ref创建的响应式对象&#xff0c;则返回true&#xff1b;否则&#xff0c;返回false。 import { ref, isRef } from vue const normalValue 这是一个普通…...

数据结构之简单选择排序介绍与举例

简单选择排序 简单选择排序是一种排序算法&#xff0c;其基本思想是&#xff1a;通过n-i次关键字间的比较&#xff0c;从n-i1个记录中选出关键字最小的记录&#xff0c;并和第i个记录交换之。 举例&#xff1a; 给定数组 [64, 25, 12, 22, 11]&#xff0c;进行简单选择排序。…...

九、Redis 的实际使用与Redis的设计

一、多级缓存架构 在线上系统中&#xff0c;一定不会单纯的只部署一个Redis集群&#xff0c;而是使用Redis结合其他的多级缓存应用进行架构。 使用多级缓存架构的优点就是可以使不同类型的数据分布在不同的应用中&#xff0c;比如redis的热点key可以存储到nginx本地缓存、服务…...

乔拓云模板助力,微信小程序快速上线无需愁备案

想要快速打造并上线自己的微信小程序吗&#xff1f;乔拓云平台是您的不二之选&#xff01;无需担心复杂的备案流程&#xff0c;乔拓云提供免费服务&#xff0c;远程协助您轻松完成微信小程序的备案工作。 只需简单几步&#xff0c;您的小程序就能闪亮登场&#xff1a;首先&…...

Android命令行查看CPU频率和温度

在 Android 设备上&#xff0c;你可以通过命令行工具 adb 来查看 CPU 温度和 CPU 频率&#xff0c;并确定是否有降频情况。以下是具体步骤&#xff1a; 1. 查看 CPU 频率 你可以使用以下命令来查看 CPU 各个核心的当前频率&#xff1a; adb shell cat /sys/devices/system/c…...

力扣: 翻转字符串里的单词

文章目录 需求分析代码结尾 需求 给你一个字符串 s &#xff0c;请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意&#xff1a;输入字符…...

Wophp靶场寻找漏洞练习

1.命令执行漏洞 打开网站划到最下&#xff0c;此处的输入框存在任意命令执行漏洞 输入命令whoami 2.SQL注入 搜索框存在SQL注入&#xff0c;类型为整数型 最终结果可以找到管理员账户和密码 3.任意文件上传漏洞 在进入管理员后台后&#xff0c;上传木马文件 访问该文件&…...

国内智能运维厂商月度动态 202408

作为市场人员&#xff0c;虽然也添加了各类行业媒体、同行厂商的关注&#xff0c;但被同事问起业内动向时&#xff0c;常常也是记忆模糊、拍破脑袋也说不完整一件事。 所以找机会翻看了一下各大厂商的公号&#xff0c;先做个简单的8月汇总。 格式暂时是这样的&#xff1a; 整…...

C++ 左值与右值浅谈

左值与右值 序言概念左值和右值的划分理解右值引用常量左值引用与右值引用 移动语义引用折叠完美转发 参考资料 序言 虽然平常都算是了解左值&#xff0c;右值的用法&#xff0c;但是好记性不如烂笔头&#xff0c;记下来供大家评鉴&#xff0c;有错改错&#xff0c;有善赞善&a…...

oracle 如何查死锁

在Oracle中查看死锁通常涉及查询数据字典视图和动态性能视图。以下是一个基本的查询示例&#xff0c;用于检测和显示最近的死锁&#xff1a; SELECT dd.inst_id, dd.name, o.object_id, o.object_type, s.sid, s.serial#, s.username, p.spid, s.program,d.xidusn,d.xidslot,d…...

如何编写ChatGPT提示词

为ChatGPT编写有效的提示需要实施几个关键策略&#xff0c;以使文本到文本生成 AI 工具产生所需的输出。您可以使用 ChatGPT 提示&#xff08;也称为 ChatGPT 命令&#xff09;来增强您的工作或提高您在各个行业的表现。例如&#xff0c;营销人员可以提示 ChatGPT 为社交媒体帖…...

java项目之基于Spring Boot智能无人仓库管理源码(springboot+vue)

项目简介 智能无人仓库管理实现了以下功能&#xff1a; 基于Spring Boot智能无人仓库管理的主要使用者分为&#xff1a; 管理员的功能有&#xff1a;员工信息的查询管理&#xff0c;可以删除员工信息、修改员工信息、新增员工信息 &#x1f495;&#x1f495;作者&#xff1a…...

大厂前端常见的笔试题目

https://zhuanlan.zhihu.com/p/488383397前端面试手写题目总结-CSDN博客 大厂前端面试中常见的手写代码题目涵盖了多个方面&#xff0c;包括但不限于算法、数据结构、JavaScript 基础知识、DOM 操作、异步编程等。以下是一些常见的手写代码题目及其简要说明&#xff1a; 1. 排…...

网络插件 Cilium 更换 Calico

网络插件 Cilium 更换 Calico 集群使用 submariner &#xff0c;通过网络检测发现 Cilium 插件可能兼容性不太好 subctl diagnose allCilium 彻底卸载 helm uninstall cilium -n kube-system# 检查集群中的所有 CNI 插件&#xff08;集群的每个节点都需要删除&#xff09; s…...

SpringSecurity原理解析(二):认证流程

1、SpringSecurity认证流程包含哪几个子流程&#xff1f; 1&#xff09;账号验证 2&#xff09;密码验证 3&#xff09;记住我—>Cookie记录 4&#xff09;登录成功—>页面跳转 2、UsernamePasswordAuthenticationFilter 在SpringSecurity中处理认证逻辑是在UsernamePas…...

Leetcode 3576. Transform Array to All Equal Elements

Leetcode 3576. Transform Array to All Equal Elements 1. 解题思路2. 代码实现 题目链接&#xff1a;3576. Transform Array to All Equal Elements 1. 解题思路 这一题思路上就是分别考察一下是否能将其转化为全1或者全-1数组即可。 至于每一种情况是否可以达到&#xf…...

STM32+rt-thread判断是否联网

一、根据NETDEV_FLAG_INTERNET_UP位判断 static bool is_conncected(void) {struct netdev *dev RT_NULL;dev netdev_get_first_by_flags(NETDEV_FLAG_INTERNET_UP);if (dev RT_NULL){printf("wait netdev internet up...");return false;}else{printf("loc…...

Linux相关概念和易错知识点(42)(TCP的连接管理、可靠性、面临复杂网络的处理)

目录 1.TCP的连接管理机制&#xff08;1&#xff09;三次握手①握手过程②对握手过程的理解 &#xff08;2&#xff09;四次挥手&#xff08;3&#xff09;握手和挥手的触发&#xff08;4&#xff09;状态切换①挥手过程中状态的切换②握手过程中状态的切换 2.TCP的可靠性&…...

《通信之道——从微积分到 5G》读书总结

第1章 绪 论 1.1 这是一本什么样的书 通信技术&#xff0c;说到底就是数学。 那些最基础、最本质的部分。 1.2 什么是通信 通信 发送方 接收方 承载信息的信号 解调出其中承载的信息 信息在发送方那里被加工成信号&#xff08;调制&#xff09; 把信息从信号中抽取出来&am…...

在Ubuntu中设置开机自动运行(sudo)指令的指南

在Ubuntu系统中&#xff0c;有时需要在系统启动时自动执行某些命令&#xff0c;特别是需要 sudo权限的指令。为了实现这一功能&#xff0c;可以使用多种方法&#xff0c;包括编写Systemd服务、配置 rc.local文件或使用 cron任务计划。本文将详细介绍这些方法&#xff0c;并提供…...

AI病理诊断七剑下天山,医疗未来触手可及

一、病理诊断困局&#xff1a;刀尖上的医学艺术 1.1 金标准背后的隐痛 病理诊断被誉为"诊断的诊断"&#xff0c;医生需通过显微镜观察组织切片&#xff0c;在细胞迷宫中捕捉癌变信号。某省病理质控报告显示&#xff0c;基层医院误诊率达12%-15%&#xff0c;专家会诊…...

安宝特案例丨Vuzix AR智能眼镜集成专业软件,助力卢森堡医院药房转型,赢得辉瑞创新奖

在Vuzix M400 AR智能眼镜的助力下&#xff0c;卢森堡罗伯特舒曼医院&#xff08;the Robert Schuman Hospitals, HRS&#xff09;凭借在无菌制剂生产流程中引入增强现实技术&#xff08;AR&#xff09;创新项目&#xff0c;荣获了2024年6月7日由卢森堡医院药剂师协会&#xff0…...

LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》

这段 Python 代码是一个完整的 知识库数据库操作模块&#xff0c;用于对本地知识库系统中的知识库进行增删改查&#xff08;CRUD&#xff09;操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 &#x1f4d8; 一、整体功能概述 该模块…...

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的“no matching...“系列算法协商失败问题

【SSH疑难排查】轻松解决新版OpenSSH连接旧服务器的"no matching..."系列算法协商失败问题 摘要&#xff1a; 近期&#xff0c;在使用较新版本的OpenSSH客户端连接老旧SSH服务器时&#xff0c;会遇到 "no matching key exchange method found"​, "n…...

Web中间件--tomcat学习

Web中间件–tomcat Java虚拟机详解 什么是JAVA虚拟机 Java虚拟机是一个抽象的计算机&#xff0c;它可以执行Java字节码。Java虚拟机是Java平台的一部分&#xff0c;Java平台由Java语言、Java API和Java虚拟机组成。Java虚拟机的主要作用是将Java字节码转换为机器代码&#x…...