JS数据结构&算法学习——队列

简介: 在之前的栈,是一种受限的线性结构,为先进后出,那么同为线性结构的队列,特点又是怎么样的呢?

队列

在之前的栈,是一种受限的线性结构,为先进后出,那么同为线性结构的队列,特点又是怎么样的呢?

概念

队列是一种受限的线性表,先进先出,它只允许我们在表的前端进行删除操作,在表的后端进行添加操作。

生活应用

  1. 在生活中最常看到的队列场景就是排队了,即我们在排队时,排头也就是我们的表头,它允许出去,无法进行插队也就是添加操作,而排尾,也就是我们的表尾,它允许有人进行排队,即添加操作
  2. 在火车检票的时候,我们正常的是进行排队,而军人,老人等特殊人群可以优先进行处理,这就是优先队列。

程序应用

  1. 就拿我们JS来说,事件队列是比较常见的,因为JS是一门单线程语言,即在我们触发我们的函数的时候,会有一个事件队列,其会按照事件的触发顺序来执行,即先触发先执行,这就是队列的一种体现
  2. 当然线程队列也是一种队列的体现,我们一般为了任务能够并行处理,会用到多线程,但是多个线程会占据非常多的内存,所以这个时候我们可以通过使用线程队列,按照次序来启动线程,并处理对应的任务。

队列结构

当然队列结构的实现和栈一样,可以通过数组和链表实现

首先我们先封装一下队列

function queue(){
    //队列的属性
    this.items = []
    //队列的相关操作
}
var queue = new queue()
复制代码

因为JS中的类是基于对象的所以我们封装了一个队列类,在类中我们可以定义队列的属性与方法,封装好之后我们可以去通过调用来对队列实现一些操作

常见操作及封装

  1. enqueue(element):在队列的尾部添加元素
  2. dequeue():移除队列的首个元素,并返回其值
  3. front():返回队列的第一个元素
  4. isEmpty:判断队列是否为空队列
  5. size:返回队列长度
  6. toString():转换字符串

enqueue(element):使用push方法来进行入队封装

queue.prototype.enqueue = function (element) {
      this.items.push(element)
}
复制代码

dequeue():通过JS提供的shift的方法来进行出队操作

queue.prototype.delet = function () {
      return this.items.shift()
}
复制代码

front():直接通过数组下标来返回队首元素

queue.prototype.front = function () {
      return this.items[0]
}
复制代码

isEmpty():通过数组的length来进行栈的判空

queue.prototype.isEmpty = function () {
      return this.items.length == 0
}
复制代码

size()

queue.prototype.size = function () {
      return this.items.length
}
复制代码

toString():通过声明字符串变量,对栈进行遍历,通过JS字符串的特性,来进行字符串拼接,最后返回其字符串,其实现原理和栈的toString一样。

queue.prototype.toString = function () {
      var reString = ''
      for (let i = 0; i < this.items.length; i++) {
        reString += this.items[i] + ''
      }
      return reString
    }
复制代码

使用

在封装好之后我们就可以开始进行调用

queue.enqueue(1)
queue.enqueue(19)
queue.enqueue(11)
console.log(queue)
复制代码

1.webp.jpg

queue.delet()
console.log(queue)
复制代码

1.webp.jpg

大家可以试着自己些写一下并体验队列的这几种操作

击鼓传花

相信大家都玩过击鼓传花的游戏吧,击鼓的时候传递花朵,鼓声停,花在谁手中谁就受惩罚

现在有不同的游戏规则,即同学围成一圈,按阿拉伯数字顺序进行数数,当某人数到在场人数的时候就会被淘汰

我们现在要用队列来实现这个游戏并返回来最终获胜者的姓名

  1. 算法原理:

1.webp.jpg

现在我们将所有人按次序放入一个队列中,然后从队首开始出队入队,以此当出现在场人数的时候,其正好是队首,出队,多次操作,得到结果

  1. 算法实现:
  1. 创建队列并将所有人入队
var queue = new queue
    for (let i = 0; i < list.length; i++) {
     queue.enqueue(nameList[i])
}
复制代码
  1. 开始循环入队出队直到队列的长度为1
while (queue.size() > 1) {
      //开始数num,当不是num的时候出队后重新入队,当num是在场人数时,出队。
      for (let i = 0; i < num - 1; i++) {
        queue.enqueue(queue.dequeue())
      }
      //删除目标即现在的队首
      queue.dequeue()
    }



相关文章
|
2月前
|
机器学习/深度学习 算法 数据挖掘
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构
K-means聚类算法是机器学习中常用的一种聚类方法,通过将数据集划分为K个簇来简化数据结构。本文介绍了K-means算法的基本原理,包括初始化、数据点分配与簇中心更新等步骤,以及如何在Python中实现该算法,最后讨论了其优缺点及应用场景。
157 4
|
11天前
|
存储 监控 算法
局域网网络管控里 Node.js 红黑树算法的绝妙运用
在数字化办公中,局域网网络管控至关重要。红黑树作为一种自平衡二叉搜索树,凭借其高效的数据管理和平衡机制,在局域网设备状态管理中大放异彩。通过Node.js实现红黑树算法,可快速插入、查找和更新设备信息(如IP地址、带宽等),确保网络管理员实时监控和优化网络资源,提升局域网的稳定性和安全性。未来,随着技术融合,红黑树将在网络管控中持续进化,助力构建高效、安全的局域网络生态。
30 9
|
9天前
|
存储 算法 测试技术
【C++数据结构——树】二叉树的遍历算法(头歌教学实验平台习题) 【合集】
本任务旨在实现二叉树的遍历,包括先序、中序、后序和层次遍历。首先介绍了二叉树的基本概念与结构定义,并通过C++代码示例展示了如何定义二叉树节点及构建二叉树。接着详细讲解了四种遍历方法的递归实现逻辑,以及层次遍历中队列的应用。最后提供了测试用例和预期输出,确保代码正确性。通过这些内容,帮助读者理解并掌握二叉树遍历的核心思想与实现技巧。
31 2
|
25天前
|
存储 运维 监控
探索局域网电脑监控软件:Python算法与数据结构的巧妙结合
在数字化时代,局域网电脑监控软件成为企业管理和IT运维的重要工具,确保数据安全和网络稳定。本文探讨其背后的关键技术——Python中的算法与数据结构,如字典用于高效存储设备信息,以及数据收集、异常检测和聚合算法提升监控效率。通过Python代码示例,展示了如何实现基本监控功能,帮助读者理解其工作原理并激发技术兴趣。
56 20
|
17天前
|
监控 算法 JavaScript
基于 Node.js Socket 算法搭建局域网屏幕监控系统
在数字化办公环境中,局域网屏幕监控系统至关重要。基于Node.js的Socket算法实现高效、稳定的实时屏幕数据传输,助力企业保障信息安全、监督工作状态和远程技术支持。通过Socket建立监控端与被监控端的数据桥梁,确保实时画面呈现。实际部署需合理分配带宽并加密传输,确保信息安全。企业在使用时应权衡利弊,遵循法规,保障员工权益。
31 7
|
15天前
|
存储 监控 JavaScript
深度探秘:运用 Node.js 哈希表算法剖析员工工作时间玩游戏现象
在现代企业运营中,确保员工工作时间高效专注至关重要。为应对员工工作时间玩游戏的问题,本文聚焦Node.js环境下的哈希表算法,展示其如何通过快速查找和高效记录员工游戏行为,帮助企业精准监测与分析,遏制此类现象。哈希表以IP地址等为键,存储游戏网址、时长等信息,结合冲突处理与动态更新机制,确保数据完整性和时效性,助力企业管理层优化工作效率。
26 3
|
2月前
|
数据采集 存储 算法
Python 中的数据结构和算法优化策略
Python中的数据结构和算法如何进行优化?
|
2月前
|
算法
数据结构之路由表查找算法(深度优先搜索和宽度优先搜索)
在网络通信中,路由表用于指导数据包的传输路径。本文介绍了两种常用的路由表查找算法——深度优先算法(DFS)和宽度优先算法(BFS)。DFS使用栈实现,适合路径问题;BFS使用队列,保证找到最短路径。两者均能有效查找路由信息,但适用场景不同,需根据具体需求选择。文中还提供了这两种算法的核心代码及测试结果,验证了算法的有效性。
130 23
|
2月前
|
并行计算 算法 测试技术
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面
C语言因高效灵活被广泛应用于软件开发。本文探讨了优化C语言程序性能的策略,涵盖算法优化、代码结构优化、内存管理优化、编译器优化、数据结构优化、并行计算优化及性能测试与分析七个方面,旨在通过综合策略提升程序性能,满足实际需求。
79 1
|
2月前
|
算法 vr&ar 计算机视觉
数据结构之洪水填充算法(DFS)
洪水填充算法是一种基于深度优先搜索(DFS)的图像处理技术,主要用于区域填充和图像分割。通过递归或栈的方式探索图像中的连通区域并进行颜色替换。本文介绍了算法的基本原理、数据结构设计(如链表和栈)、核心代码实现及应用实例,展示了算法在图像编辑等领域的高效性和灵活性。同时,文中也讨论了算法的优缺点,如实现简单但可能存在堆栈溢出的风险等。
77 0