数据结构和算法-数组模拟队列分析|学习笔记

简介: 快速学习数据结构和算法-数组模拟队列分析

开发者学堂课程【Go 语言核心编程 - 数据结构和算法: 数据结构和算法-数组模拟队列分析】学习笔记,与课程紧密联系,让用户快速学习知识。

课程地址:https://developer.aliyun.com/learning/course/627/detail/9831


数据结构和算法-数组模拟队列分析

 

内容简介:

一、队列(queue)

二、数组模拟队列分析

 

一、队列(queue)

(1)前言

前面讲了稀疏数组的一个用法,现在来看另外一种比较常见的数据结构,也是在前面经常用到的一种数据结构,叫队列。

队列是一种经常使用到的一种数据结构,因为在现实生活中,包括在编程过程中,都会存在一种队列,就是以队列的方式来对数据进行一个处理。

(2)队列的一个使用场景

比如排队,如下图:

image.png

经常会有一个排队,比如进来有一个人在排队,先进的排在前面,做一个叫号系统,先来的人应该先被服务,后来的人后被服务,别整反了,整反了就先来的人一直等着,没人管他,后来的全部往上怼,那这个系统就出问题了,这个排队的案例就是这样的,非常经典,这是队列的一个使用场景。

那么想一想,在编程中还有哪些会用到队列这种形式的,比如大家都知道,就是留言版,留言一般是谁先留言总是排在前面是,是排序了,还有很多其他的用法了。

(3)队列介绍

那队列有这些用法的话,这个队列到底是什么?

首先,队列它是一个有序列表,注意这里说的有序,并不是说它一定是按照从大到小或从小到大的,那个叫排序,所以有序指的是它的数据是按照一定顺序来排的,就是先进去的排在前面,后进去排在后边,这个称之为有序列表,它可以用数组来实现,同样也可以用链表来实现。

准确的讲,链表实现相对简单,数组实现其实相对麻烦,尤其是对环行数组来实现队列还是比较麻烦的,这个理解起来有一定难度,那么队列还有一个最重要的特点,即它是先入先出的原则,即先存入队列的数据要先取出来,后存储的数据要后取出来。

(4)队列介绍示意图

画了一个示意图,帮助理解,如下:

image.png

就以数组的这种方式来给大家看一下队列,假设这里有一个数组,将其横着放为了看起来更清楚一点,比如这个数组,它是有一些数据在里边,假设它一共可以存放五个元素,当存放数据的时候(假设小圆圈是一个数据),数组本身它应该也是一个有顺序的,可以放到第一个空格的位置,

比如说这是它的第零个元素,放入第二个空格的是它第一个元素,放入第三个空格的是它第二个元素,以此类推这是它第三个元素、这是它第四个元素,那么在放数据时,它应该这样存放:

首先,在它的第一个位置存,这个相当于是它的队列的队首,它第一个在最前面,然后在它的后面放,如果我又存放了一个数据结构,后面再存放一个数据,又在这个后面存放,以此类推,就这样不停地存放,那么取的时候应该怎么取?

取的时候是从前面取。请思考一个问题:原先数组里面有三个元素,当取走一个元素时,那么其实这个数组的队列的队首就变成它了,即队列的第一个,那么这种形式下有一个问题,假设这个地方再取走一个队手,这时又往里面加数据,应该在哪加?

它其实是在最后面加,那么队尾是在哪里?就是它最后的元素队尾。这时有一个问题就是,当它都存完了之后,如果再放一个数据,应该放哪?怎么处理?

在某种情况下,数组来模拟一个队列,这个数组就没法用了,那么如果用数组来模拟这个队列,存在一个最大的问题,就是怎么有效的利用前面的空间,当然有同学曾经这样说过,他说老师你看,不停地往后面推就可以了,但是推到后面确实没法放了,但是前面还有空间,可能会想那把它放到前面就可以了呀,但是放到前面就涉及到好多东西在里面,因为要到后面去找前面这种算法了,怎么能够在这边的时候还找到前面,这是一种思路。

这肯定要涉及算法,那么有些动作是不能这样简单一点的,要把放的每一个元素精确好,现在假设有一个人取走一个元素,赶紧把前面挪一下,后面还有空间,如果这么做,这个效率极为低下。

假设这个队列里很大,整体往前移下去试试看,那这个就彻底的完了,不如不用数据结构,因为将来数字很大,假设有1000个数字移动一个,如果把整体99往前移动,速度会很慢,所以这样肯定是不行的,那么有一个问题就是怎么去有效利用空间,比如说到地方了,假设有三个数据,然后这个地方前面还有两个空,要怎么用?

这个叫环形,用数组来模拟一个环形队列,相当于说用数组来实现队列有两种形式,第一种比较简单,但是它不能有效的利用数据;第二种方式是比较烧脑的,是不容易很好理解的,这个东西相对来说有一点麻烦。

 

二、数组模拟队列

(1)模拟分析

看这个案例,即用数组来模拟队列,先说第一种就是,而不是环形的,那怎么来实现?

首先这里有几个思路要说清楚,第一个是队列本身是有序数列,若使用数组的结构来存储队列的数据,则队列数组的声明应该如下,应该有一个 maxSize ,就是表明队列最大的容量是多少,不管怎么样,这个队列假设最多只能存放五个数据进去,不能存六个。

即使是用环形来做,它也是一个大小的,就像在某个区域排队排到一定程度的时候,就关门,即不让进去了,容量满了;

第二个,因为队列的输入、输出是分别从前后端来处理的,因此至少需要两个变量来表示它的队尾和队首,即第一个和最后一个,那么这里用的是 front 和 rear , front 就是前端, rear 就是尾部,用这两个人分别记录队列的前后端的两个下标,那么 front 就是队首,队首会随着数据的输出而改变,做完一个取出来一个, front 就会往后面移动,那么是随着数据的输入而改变,那么当加入一个数据的时候,real 就应该往后面挪,它其实一个是输出,一个是输入,那看一下以下这个图:

image.png

可以看到一个基本的思想,关于用数组来模拟队列,思想基本上都是这个思想,但是具体实现还是略有差别,比如以前在大学学这个数据结构的时候,它是这么一种方式实现,等到参加工作后,发现它是另一种事情,但整体思想是差不多的。

首先上图最左边的是一个数组,这个数组大小是 maxSize ,因为下标肯定不能到最大的值,那么这个就代表一个 Q ,那么它这里面的 Front 和 rear ,初始化为负一,当往里面放一个数据,这个地方扔数据的时候,整个这个 front 是没有移动的,谁在不停的移动?

这个 rear 一定要非常清楚的知道,rear 是在随着数据的添加而往后移动,而且注意一个重要特点,在这个思想里面, rear 其实就是指向队列的最后,而且包含它真正地指向了对面,最后就的确使用最后一个数据;

注意观察 front ,这个 front 它初始化为负一,其实它在里面有的时候是没有动过的,所以  front  它其实相当于是指向队列的前面,而且并没有包含第一个元素,这一点如果没有搞清楚的话,看代码可能就看不懂了,一写就容易蒙圈。

(2)应用案例

有了这个东西过后,来看一下具体的实现,来把数组模拟对立的思想先说清楚,一个是它是一个有序的数组,它的变化是由这两个数据来体现的,一个是对首,一个是对尾。

我们将数据存入队列时称为addqueue”, addqueue 的处理需要两个步骤:第一个是尾指针往后移Front 等于 rear 的时候,认为是空;第二个指针rear 小于等于队列的最大下标 MaxSize-1 ,则该数组存入的这个位置满了,那么减一的时候就认为队列满了

也就是说目前这个数组模拟队列,其实它是一个飞环形状的用完就没有了,最多就搞五个,然后没有了这个方法比较简单,相对比较好理解,但是肯定不灵活。

(3)思路分析

来先完成一个飞环形的一个队列,同样是用数组来实现的,接着讲一下思路分析,如下图:

image.png

相关文章
|
16天前
|
算法 数据处理 C语言
C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合
本文深入解析了C语言中的位运算技巧,涵盖基本概念、应用场景、实用技巧及示例代码,并讨论了位运算的性能优势及其与其他数据结构和算法的结合,旨在帮助读者掌握这一高效的数据处理方法。
27 1
|
19天前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
63 4
|
17天前
|
存储 算法 搜索推荐
Python 中数据结构和算法的关系
数据结构是算法的载体,算法是对数据结构的操作和运用。它们共同构成了计算机程序的核心,对于提高程序的质量和性能具有至关重要的作用
|
17天前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
25天前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
86 23
|
25天前
|
算法
数据结构之蜜蜂算法
蜜蜂算法是一种受蜜蜂觅食行为启发的优化算法,通过模拟蜜蜂的群体智能来解决优化问题。本文介绍了蜜蜂算法的基本原理、数据结构设计、核心代码实现及算法优缺点。算法通过迭代更新蜜蜂位置,逐步优化适应度,最终找到问题的最优解。代码实现了单链表结构,用于管理蜜蜂节点,并通过适应度计算、节点移动等操作实现算法的核心功能。蜜蜂算法具有全局寻优能力强、参数设置简单等优点,但也存在对初始化参数敏感、计算复杂度高等缺点。
57 20
|
16天前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
42 1
|
25天前
|
机器学习/深度学习 算法 C++
数据结构之鲸鱼算法
鲸鱼算法(Whale Optimization Algorithm,WOA)是由伊朗研究员Seyedali Mirjalili于2016年提出的一种基于群体智能的全局优化算法,灵感源自鲸鱼捕食时的群体协作行为。该算法通过模拟鲸鱼的围捕猎物和喷出气泡网的行为,结合全局搜索和局部搜索策略,有效解决了复杂问题的优化需求。其应用广泛,涵盖函数优化、机器学习、图像处理等领域。鲸鱼算法以其简单直观的特点,成为初学者友好型的优化工具,但同时也存在参数敏感、可能陷入局部最优等问题。提供的C++代码示例展示了算法的基本实现和运行过程。
44 0
|
1月前
|
C语言
【数据结构】栈和队列(c语言实现)(附源码)
本文介绍了栈和队列两种数据结构。栈是一种只能在一端进行插入和删除操作的线性表,遵循“先进后出”原则;队列则在一端插入、另一端删除,遵循“先进先出”原则。文章详细讲解了栈和队列的结构定义、方法声明及实现,并提供了完整的代码示例。栈和队列在实际应用中非常广泛,如二叉树的层序遍历和快速排序的非递归实现等。
159 9
|
1月前
|
存储 算法
非递归实现后序遍历时,如何避免栈溢出?
后序遍历的递归实现和非递归实现各有优缺点,在实际应用中需要根据具体的问题需求、二叉树的特点以及性能和空间的限制等因素来选择合适的实现方式。
26 1

热门文章

最新文章