数据结构——栈和队列(队列的定义、顺序队列以及链式队列的基本操作)
目录
队列(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 中,关键字(Keywords)和基数(Radix)是语言的重要组成部分,它们有助于描述和定义硬件设计。上期分享了 Verilog 的基本使用,以及数据类型、逻辑值和算数运算符的简单应用&#x…...
什么是单元测试?怎么做?
🍅 点击文末小卡片 ,免费获取软件测试全套资料,资料在手,涨薪更快 一、什么是单元测试? 单元测试(unit testing),是指对软件中的最小可测试单元进行检查和验证。至于“单元”的大小…...
论文复现--基于LeNet网络结构的数字识别
前言 一直就听说学习深度学习无非就是看论文,然后复现,不断循环,这段时间也看了好几篇论文(虽然都是简单的),但是对于我一个人自学,复现成功,我感觉还是挺开心的 本人初学看论文的思路:聚焦网络…...
Vue3 响应式工具函数isRef()、unref()、isReactive()、isReadonly()、isProxy()
isRef() isRef():检查某个值是否为 ref。 isRef函数接收一个参数,即要判断的值。如果该参数是由ref创建的响应式对象,则返回true;否则,返回false。 import { ref, isRef } from vue const normalValue 这是一个普通…...
数据结构之简单选择排序介绍与举例
简单选择排序 简单选择排序是一种排序算法,其基本思想是:通过n-i次关键字间的比较,从n-i1个记录中选出关键字最小的记录,并和第i个记录交换之。 举例: 给定数组 [64, 25, 12, 22, 11],进行简单选择排序。…...
九、Redis 的实际使用与Redis的设计
一、多级缓存架构 在线上系统中,一定不会单纯的只部署一个Redis集群,而是使用Redis结合其他的多级缓存应用进行架构。 使用多级缓存架构的优点就是可以使不同类型的数据分布在不同的应用中,比如redis的热点key可以存储到nginx本地缓存、服务…...
乔拓云模板助力,微信小程序快速上线无需愁备案
想要快速打造并上线自己的微信小程序吗?乔拓云平台是您的不二之选!无需担心复杂的备案流程,乔拓云提供免费服务,远程协助您轻松完成微信小程序的备案工作。 只需简单几步,您的小程序就能闪亮登场:首先&…...
Android命令行查看CPU频率和温度
在 Android 设备上,你可以通过命令行工具 adb 来查看 CPU 温度和 CPU 频率,并确定是否有降频情况。以下是具体步骤: 1. 查看 CPU 频率 你可以使用以下命令来查看 CPU 各个核心的当前频率: adb shell cat /sys/devices/system/c…...
力扣: 翻转字符串里的单词
文章目录 需求分析代码结尾 需求 给你一个字符串 s ,请你反转字符串中 单词 的顺序。 单词 是由非空格字符组成的字符串。s 中使用至少一个空格将字符串中的 单词 分隔开。 返回 单词 顺序颠倒且 单词 之间用单个空格连接的结果字符串。 注意:输入字符…...
Wophp靶场寻找漏洞练习
1.命令执行漏洞 打开网站划到最下,此处的输入框存在任意命令执行漏洞 输入命令whoami 2.SQL注入 搜索框存在SQL注入,类型为整数型 最终结果可以找到管理员账户和密码 3.任意文件上传漏洞 在进入管理员后台后,上传木马文件 访问该文件&…...
国内智能运维厂商月度动态 202408
作为市场人员,虽然也添加了各类行业媒体、同行厂商的关注,但被同事问起业内动向时,常常也是记忆模糊、拍破脑袋也说不完整一件事。 所以找机会翻看了一下各大厂商的公号,先做个简单的8月汇总。 格式暂时是这样的: 整…...
C++ 左值与右值浅谈
左值与右值 序言概念左值和右值的划分理解右值引用常量左值引用与右值引用 移动语义引用折叠完美转发 参考资料 序言 虽然平常都算是了解左值,右值的用法,但是好记性不如烂笔头,记下来供大家评鉴,有错改错,有善赞善&a…...
oracle 如何查死锁
在Oracle中查看死锁通常涉及查询数据字典视图和动态性能视图。以下是一个基本的查询示例,用于检测和显示最近的死锁: 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编写有效的提示需要实施几个关键策略,以使文本到文本生成 AI 工具产生所需的输出。您可以使用 ChatGPT 提示(也称为 ChatGPT 命令)来增强您的工作或提高您在各个行业的表现。例如,营销人员可以提示 ChatGPT 为社交媒体帖…...
java项目之基于Spring Boot智能无人仓库管理源码(springboot+vue)
项目简介 智能无人仓库管理实现了以下功能: 基于Spring Boot智能无人仓库管理的主要使用者分为: 管理员的功能有:员工信息的查询管理,可以删除员工信息、修改员工信息、新增员工信息 💕💕作者:…...
大厂前端常见的笔试题目
https://zhuanlan.zhihu.com/p/488383397前端面试手写题目总结-CSDN博客 大厂前端面试中常见的手写代码题目涵盖了多个方面,包括但不限于算法、数据结构、JavaScript 基础知识、DOM 操作、异步编程等。以下是一些常见的手写代码题目及其简要说明: 1. 排…...
网络插件 Cilium 更换 Calico
网络插件 Cilium 更换 Calico 集群使用 submariner ,通过网络检测发现 Cilium 插件可能兼容性不太好 subctl diagnose allCilium 彻底卸载 helm uninstall cilium -n kube-system# 检查集群中的所有 CNI 插件(集群的每个节点都需要删除) s…...
SpringSecurity原理解析(二):认证流程
1、SpringSecurity认证流程包含哪几个子流程? 1)账号验证 2)密码验证 3)记住我—>Cookie记录 4)登录成功—>页面跳转 2、UsernamePasswordAuthenticationFilter 在SpringSecurity中处理认证逻辑是在UsernamePas…...
《Qt C++ 与 OpenCV:解锁视频播放程序设计的奥秘》
引言:探索视频播放程序设计之旅 在当今数字化时代,多媒体应用已渗透到我们生活的方方面面,从日常的视频娱乐到专业的视频监控、视频会议系统,视频播放程序作为多媒体应用的核心组成部分,扮演着至关重要的角色。无论是在个人电脑、移动设备还是智能电视等平台上,用户都期望…...
3.3.1_1 检错编码(奇偶校验码)
从这节课开始,我们会探讨数据链路层的差错控制功能,差错控制功能的主要目标是要发现并且解决一个帧内部的位错误,我们需要使用特殊的编码技术去发现帧内部的位错误,当我们发现位错误之后,通常来说有两种解决方案。第一…...
Debian系统简介
目录 Debian系统介绍 Debian版本介绍 Debian软件源介绍 软件包管理工具dpkg dpkg核心指令详解 安装软件包 卸载软件包 查询软件包状态 验证软件包完整性 手动处理依赖关系 dpkg vs apt Debian系统介绍 Debian 和 Ubuntu 都是基于 Debian内核 的 Linux 发行版ÿ…...
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>…...
C++ 求圆面积的程序(Program to find area of a circle)
给定半径r,求圆的面积。圆的面积应精确到小数点后5位。 例子: 输入:r 5 输出:78.53982 解释:由于面积 PI * r * r 3.14159265358979323846 * 5 * 5 78.53982,因为我们只保留小数点后 5 位数字。 输…...
JVM暂停(Stop-The-World,STW)的原因分类及对应排查方案
JVM暂停(Stop-The-World,STW)的完整原因分类及对应排查方案,结合JVM运行机制和常见故障场景整理而成: 一、GC相关暂停 1. 安全点(Safepoint)阻塞 现象:JVM暂停但无GC日志,日志显示No GCs detected。原因:JVM等待所有线程进入安全点(如…...
视觉slam十四讲实践部分记录——ch2、ch3
ch2 一、使用g++编译.cpp为可执行文件并运行(P30) g++ helloSLAM.cpp ./a.out运行 二、使用cmake编译 mkdir build cd build cmake .. makeCMakeCache.txt 文件仍然指向旧的目录。这表明在源代码目录中可能还存在旧的 CMakeCache.txt 文件,或者在构建过程中仍然引用了旧的路…...
Python Ovito统计金刚石结构数量
大家好,我是小马老师。 本文介绍python ovito方法统计金刚石结构的方法。 Ovito Identify diamond structure命令可以识别和统计金刚石结构,但是无法直接输出结构的变化情况。 本文使用python调用ovito包的方法,可以持续统计各步的金刚石结构,具体代码如下: from ovito…...
jdbc查询mysql数据库时,出现id顺序错误的情况
我在repository中的查询语句如下所示,即传入一个List<intager>的数据,返回这些id的问题列表。但是由于数据库查询时ID列表的顺序与预期不一致,会导致返回的id是从小到大排列的,但我不希望这样。 Query("SELECT NEW com…...
在golang中如何将已安装的依赖降级处理,比如:将 go-ansible/v2@v2.2.0 更换为 go-ansible/@v1.1.7
在 Go 项目中降级 go-ansible 从 v2.2.0 到 v1.1.7 具体步骤: 第一步: 修改 go.mod 文件 // 原 v2 版本声明 require github.com/apenella/go-ansible/v2 v2.2.0 替换为: // 改为 v…...

